programming : PERBANDINGAN ALGORITMA SORTING

Tulisan ini sebenarnya hanya teori, dan tulisan ini merupakan tugas yang diberikan kampus jadi ketimbang dibiarkan di komputer lebih baik ditaruh disini sebagai sarana buat belajar. Tulisan ini dibuat dari beberapa sumber bacaan(lupa lagi...)...!

Tulisan ini sebenarnya hanya teori, dan tulisan ini merupakan tugas yang diberikan kampus jadi ketimbang dibiarkan di komputer lebih baik ditaruh disini sebagai sarana buat belajar. Tulisan ini dibuat dari beberapa sumber bacaan(lupa lagi...)...!
1 Pengurutan data dengan menggunakan metode 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. Untuk pemrograman konvensional maka pemeriksaan-pemeriksaan pasangan tersebut harus dilakukan satu demi satu, 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,48,82,93,86,26,76,49,23,56,37.
Pada iterasi i=0:
j=13: tukar 56-37 menjadi 34,43,65,90,49,82,93,86,26,76,49,23,37,56
j=12: tidak ada penukaran
j=11: tukar 49-23 menjadi 34,43,65,90,48,82,93,86,26,76,23,49,37,56
j=10: tukar 76-23 menjadi 34,43,65,90,48,82,93,86,26,23,76,49,37,56
j= 9: tukar 26-23 menjadi 34,43,65,90,48,82,93,86,23,26,76,49,37,56
j= 8: tukar 86-23 menjadi 34,43,65,90,48,82,93,23,86,26,76,49,37,56
j= 7: tukar 93-23 menjadi 34,43,65,90,48,82,23,93,86,26,76,49,37,56
j= 6: tukar 82-23 menjadi 34,43,65,90,48,23,82,93,86,26,76,49,37,56
j= 5: tukar 49-23 menjadi 34,43,65,90,23,48,82,93,86,26,76,49,37,56
j= 4: tukar 90-23 menjadi 34,43,65,23,90,48,82,93,86,26,76,49,37,56
j= 3: tukar 65-23 menjadi 34,43,23,65,90,48,82,93,86,26,76,49,37,56
j= 2: tukar 43-23 menjadi 34,23,43,65,90,48,82,93,86,26,76,49,37,56
j= 1: tukar 34-23 menjadi 23,34,43,65,90,48,82,93,86,26,76,49,37,56

Pada iterasi i=1:
j=13: tidak ada penukaran
j=12: tukar 49-37 menjadi 23,34,43,65,90,48,82,93,86,26,76,37,49,56
j=11: tukar 76-37 menjadi 23,34,43,65,90,48,82,93,86,26,37,76,49,56
j=10: tidak ada penukaran
j= 9: tukar 86-26 menjadi 23,34,43,65,90,48,82,93,26,86,37,76,49,56
j= 8: tukar 93-26 menjadi 23,34,43,65,90,48,82,26,93,86,37,76,49,56
j= 7: tukar 82-26 menjadi 23,34,43,65,90,48,26,82,93,86,37,76,49,56
...
j= 2: tukar 34-26 menjadi 23,26,34,43,65,90,48,82,93,86,37,76,49,56
Dan seterusnya. Hingga, pada setiap akhir iterasi berikutnya berturut-turut menjadi:
i=2: 23,26,34,37,43,65,90,48,82,93,86,49,76,56
i=3: 23,26,34,37,43,48,65,90,49,82,93,86,56,76
i=4: 23,26,34,37,43,48,49,65,90,56,82,93,86,76
i=5: 23,26,34,37,43,48,49,56,65,90,76,82,93,86
i=6: 23,26,34,37,43,48,49,56,65,76,90,82,86,93
i=7: 23,26,34,37,43,48,49,56,65,76,82,90,86,93
i=8: 23,26,34,37,43,48,49,56,65,76,82,86,90,93
i=9: 23,26,34,37,43,48,49,56,65,76,82,86,90,93
Dari kedua iterasi dengan increment linear demikian dapat mudah dilihat bahwa algoritma ini memiliki kompleksitas O(n2) dan proses akan menjadi amat cepat kalau data sudah sebagian besar terurut. Masalah yang dihadapi algoritma ini adalah banyaknya penukaran yang dilakukan selama proses dalam kondisi normal. Efisiensi dapat ditingkatkan dengan mengurangi proses penukaran dengan penggeseran dan penyisipan seperti halnya insertion sort. Untuk lingkungan pemrograman paralel dengan array processor pengurutan ini menjadi amat menarik untuk dikaji.
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.

2 Pengurutan data dengan menggunakan metode 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.

CAPIL