MACAM-MACAM PENGURUTAN (SORT)

MACAM-MACA PENGURUTAN (SORT)
Tulisan ini membahas program visualisasi metode pengurutan dasar: bubble sort, selection sort dan insertion sort. Tujuannya adalah memperlihatkan perubahan posisi data dan menghitung secara tepat jumlah perbandingan dan pertukaran data selama proses pengurutan berlangsung. Di luar algoritma-algoritma yang dibahas ada puluhan algoritma lain yang pada dasarnya dari algoritma-algoritma yang akan dibahas berikut ini:
a. Bubble Sort
Ide dari algoritma ini sangat menarik. Setiap pasangan data: x[j] dengan x[j-1], untuk semua i=1,...,n-1 harus memenuhi keterurutan, yaitu x[j] > x[j-1]. Apabila tidak memenuhi maka posisi kedua data harus ditukar. Misalnya oleh bubble-sort dilakukan dari kanan ke kiri serta di dalam sejumlah iterasi.
Pada iterasi ke-i, pemeriksaan tsb. dilakukan pula dalam loop-for sbb.
for (j=n-1; j > i; j--) {
if (x[j] < x[j-1]) {
tmp = x[j];x[j] = x[j-1];x[j-1] = tmp;
}
}
Loop-for tersebut akan menggeser bilangan terkecil ke posisi i. Loop-for dilakukan hanya sampai ke i karena pada iterasi ke-i data dalam x[0], x[1], ..., x[i-1] merupakan yang paling kecil dan sudah terurut hasil pengeseran yang dilakukan setiap loop sebelumnya. Oleh sebab itu iterasi hanya dilakukan untuk harga i=0, 1, ..., n-2 atau sampai tidak terjadi penukaran dalam suatu iterasi.
void BubbleSort() {
ch = true;for (i=0; i < n-2 && ch; i++) {
ch = false;for (j=n-1; j > i; j--) {
if (x[j] < x[j-1]) {
tmp = x[j];x[j] = x[j-1];x[j-1] = tmp; ch = true;
}
}
}
}

Contoh untuk mengurutkan data 34,43,65,90
Pada iterasi i=0:j=13: tukar 56-37 menjadi 34,43,65,90
j=12: tidak ada penukaran 34,43,65,23,90 j= 3: tukar 65-23 menjadi 34,43,23,65,90
j= 2: tukar 43-23 menjadi 34,23,43,65,90j= 1: tukar 34-23 menjadi 23,34,43,65,90

Jika Bobble Sort dalam setiap iterasi melakukan loop-for penukaran ke satu arah, Shaker Sort (suatu variant dari Bubble Sort) melakukan loop-for penukaran dengan arah bolak-balik dengan batas loop-for kiri dan kanan semakin menyempit.
b. Shell Sort
Algoritma ini bisa dipandang sebagai modifikasi dari algoritma Insertion Sort, lebih tepatnya memanfaatkan kondisi-kondisi positif dari Insertion Sort. Walaupun Insertion Sort dalam kondisi normal merupakan algoritma O(n2), algoritma ini memiliki keuntungan-keuntungan sbb.:
o Insertion Sort bisa sangat efisien untuk data dalam kondisi hampir terurut.
o Karena Insertion Sort sangat sederhana, maka overhead cost untuk proses-proses tambahannya pun amat kecil sehingga untuk jumlah data n yang kecil masih bisa lebih cepat dari algoritma O(n log n).
Dengan suatu bilangan integer positif D, maka setiap X[i], X[i+D], X[i+2D, ..., dimasukkan dalam satu subset yang sama dari D subset yang ada. Pengurutan a'la Insertion Sort dilakukan pada masing-masing subset. Jika D=1 maka yang terjadi adalah Insertion Sort murni.
Sejumlah harga D: D1, D2, ..., Dh, di mana D1 > D2 > ... > Dh = 1, masing-masing diaplikasikan dengan cara di atas berturut-turut mulai dari yang terbesar hingga yang terkecil maka akhirnya terjadi hal-hal sebagai berikut:
o Saat D berharga besar maka terjadi sejumlah insertion sort pada subset-subset yang masing-masing dengan data berjumlah sedikit (n/D). Dengan demikian mendekati kondisi positif Insertion Sort kedua.
o Untuk D yang kecil ukuran subset membesar namun akibat proses pada D sebelumnya dapat menyebabkan data sebagian terurut, dan ini adalah mendekati kondisi positif Insertion Sort pertama.
Kompleksitas dari algoritma ini secara worse case adalah dengan waktu O(n2) tetapi dengan pemilihan harga-harga D yang tepat dapat menghasilkan kompleksitas waktu yang kurang dari itu. Namun sejumlah literatur berdasarkan pengukuran eksperimental mendapatkan average case dengan waktu O(n1.25).
c. Quick Sort
Ide dari algoritma ini adalah secara rekursif membagi (atau mempartisi) data set ke dalam dua sub data set; kita sebut sub data set kiri dan sub data set kanan. Partisi ini dilakukan dengan kriteria:
o digunakan salah satu data sebagai pivot value
o sub data set kiri adalah data yang berharga <= pivot value
o sub data set kanan adalah data yang berharga > pivot value
Jika data set berada dalam array X berindeks dari l sampai dengan r maka pembagian ini mempertukarkan sejumlah isi array sehingga sub data set kiri berada dalam array yang sama berindeks l sampai dengan t-1 dan sub data set kanan berada dalam array berindeks t+1 sampai dengan r. X[t] sendiri ditempati oleh pivot.
Setelah dilakukan pembagian tersebut maka algoritma Quick Sort diaplikasikan untuk masing-masing sub data set tsb dan seterusnya secara rekursif hingga terbentuk sub data set yang tidak dapat dibagi lagi yaitu jika hanya berisi satu sel (l = r).
Bagian yang paling tricky adalah pada pembagian data set, kita sebut fungsi tersebut adalah Partition(l,r) yang menghasilkan t yaitu posisi pivotnya. Maka, algoritma Quick Sort adala sebagai berikut.

void QuickSort(int l,int r) {
if (l < r) {
t = Partition(l,r);QuickSort(l,t-1);QuickSort(t+1,r);
}
}
Proses Partisi diserahkan kepada anda untuk mempelajarinya sendiri. Dalam beberapa literatur terdapat variant-varuant yang pada dasarnya terjadi karena perbedaan cara menentukan harga pivot: bisa data pertama (X[l]), data terakhir (X[r]) atau data ditengah (X[(l+r)/2]) data set).
Kompleksitas algoritma Quick Sort adalah bergantung pada hasil partisi tersebut. Kondisi best case adalah jika dalam setiap partisi tidak dilakukan operasi pertukaran tempat dan pivot tepat berada ditengah subset (O(n)). Kondisi average case adalah jika partisi menghasilkan sub data set yang balance (o(n log n)). Kondisi worse case adalah jika partisi menghasilkan sub data set kosong dan yang lain besar (o(n2). Walaupun demikian, algoritma ini cenderung untuk average case.