Algoritma Sorting
Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.
Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data.
Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna.
Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :
1. Memahami dan menjelaskan algoritma dari insertion sort, selection sort, merge sort dan quick sort.
2. Membuat implementasi pribadi menggunakan algoritma yang ada
Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan
dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Contoh :
data
|
1st Pass
|
2nd Pass
|
3rd Pass
|
4th Pass
|
Mango
|
Mango
|
Apple
|
Apple
|
Apple
|
Apple
|
Apple
|
Mango
|
Mango
|
Banana
|
Peach
|
Peach
|
Peach
|
Orange
|
Mango
|
Orange
|
Orange
|
Orange
|
Peach
|
Orange
|
Banana
|
Banana
|
Banana
|
Banana
|
Peach
|
Gambar 1.1.2: Contoh insertion sort
Pada akhir modul ini, anda akan diminta untuk membuat implementasi bermacam algoritma sorting yang akan dibahas pada bagian ini.
