Macam-macam Sorting

1. Bubble Sort
Metode bubble sort merupakan metode tersederhana untuk melakukan pengurutan data , tetapi memiliki kinerja yang terburuk untuk data yang besar. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.Penukaran baru dilakukan kalau suatu kriteria terpenuhi.
Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, asc atau desc.Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Bubble Sort adalah salah satu metode pengurutan (sorting) dengan cara membandingkan angka dalam satu waktu yang ada pada list, kemudian memperbaiki urutan angka – angka tersebut jika tidak mengikuti urutan yang ditentukan.
contoh:
input (input.txt)
5 6 8 4 8 9
1 3 6 4 8 4
1 0 6 9 5 8

input memiliki 6 kolom k dan 3 baris j

1. Baca file input.txt dan store setiap value kedalam baris dan kolom yang sesuai, misal variable: angka[j][k]
2. Gunakan for loop 2-d array untuk membaca susunan angka

01 for(int j=0;j<3;j++){//baris
02 for(int k=0;k<6;k++){//kolom
03 //bubble sorting : angka akan diswap bila angka berikutnya lebih besar dari angka sebelum
04 if(angka[j][k] < angka[j][k+1]){
05 int temp = angka[j][k];
06 angka[j][k] = angka[j][k+1];
07 angka[j][k+1] = temp;
08 }
09 cout<
10 }
11 cout<
12 }
sekarang variable angka telah diurutkan. bisa langsung tulis ke dalam file output.txt
output (output.txt):
9 8 8 6 5 4
8 6 4 4 3 1
9 8 6 5 1 0
ilustrasi pengurutan dengan bubble sortnya akan terlihat seperti pada table dibawah ini :
LANGKAH 1 :
1 2 3 4 5 6 POSISI DATA
22 10 15 3 8 2 Data Awal
22 10 15 3 2 8 tukar data 5 dengan 6
22 10 15 2 3 8 tukar data 4 dengan 3
22 10 2 15 3 8 tukar data 3 dengan 2
22 2 10 15 3 8 tukar data 2 dengan 1
2 22 10 15 3 8 LANGKAH 1 SELESAI

LANGKAH 2 :
1 2 3 4 5 6 POSISI DATA
2 22 10 15 3 8 Data Langkah 1 Akhir
2 22 10 3 15 8 tukar data 4 dengan 3
2 22 3 10 15 8 tukar data 3 dengan 2
2 3 22 10 15 8 LANGKAH 2 SELESAI

LANGKAH 3 :
1 2 3 4 5 6 POSISI DATA
2 3 22 10 15 8 Data Langkah 2 Akhir
2 3 22 10 8 15 tukar data 5 dengan 6
2 3 22 8 10 15 tukar data 4 dengan 3
2 3 8 22 10 15 LANGKAH 3 SELESAI

LANGKAH 4 :
1 2 3 4 5 6 POSISI DATA
2 3 8 22 10 15 Data Langkah 3 Akhir
2 3 8 22 10 15 tukar data 5 dengan 4
2 3 8 10 22 15 LANGKAH 4 SELESAI

LANGKAH 5 :
1 2 3 4 5 6 POSISI DATA
2 3 8 10 22 15 Tukar data 5 dengan 6
2 3 8 10 15 22 TERURUT


2.Exchange Sort
Metode Exchange Sort merupakan metode pengurutan data yang sangat mirip dengan Bubble Sort bahkan banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Namun perbedaan antara Exchange Sort dan bubble sort terletak dalam hal bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

3.Selection Sort
Metode selection sort merupakan metode pengurutan data kombinasi antara sorting dan searching. Mekanismenya seperti berikut ini : Mula – mula suatu petunjuk (diberi nama posAwal ) yang menunjuk lokasi awal pengurutan data diatur agar berisi indeks pertama dalam larik. Selanjutnya dicari bilangan terkecil yang terletak antara posisi sesudah yang ditunjuk oleh penunjuk tersebut element yang terakhir dalam larik. Lokasi bilangan ini di tunjuk oleh posMin. Lalu tukarkan nilai bilangan terkecil tersebut dengan nilai yang di tunjukkan posAwal. Proses seperti ini di ulang dari posAwal berniali 0 hingga n-2 , dengan n menyatakan jumlah element larik.

4.Insertion Sort
Metode Insertion sort merupakan metode pengurutan data yang mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya sehinggan penambahan kartu tersebut akan membuat semua kartu tetap terurutkan. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

5.Quick Sort
Metode Quick sort merupakan metode pengurutan data yang di kemukakan pertama kali oleh C. AR Hoare pada tahun 1962. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme seperti berikut : Larik L[p..r] dengan indeks terkecil adalah p dan indeks terbesar adalah r disusun ulang (dipartisi) menjadi dua buah larik A[p..p] dan A[q+1…r] sehingga setiap elemen dalam A[p..q] selalu bernilai lebih kecil daripada A[q+1…r]. Selanjutnya kedua larik tersebut di urut secara rekursif. Dengan sendirinya kombinasi kedua larik tersebut membentuk larik dengan data yang telah di urut.
Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi. Sehingga didalamnya telah terjadi proses Rekursif.

6.Merge Sort
Merge sort merupakan salah satu teknik sorting yang mengurutkan suatu data dengan cara penggabungan.Merge sort juga menggunakan proses divide and conquer pada rekursi.Berikut adalah langkah kerja merge sort :
1. Devide
Memilah elemen – elemen dari data menjadi dua bagian.
2. Conquer
Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi akan berhenti jika telah mencapai elemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian. Sebagai catatan, pengkombinasian dilakukan dengan cara pembandingan. Elemen yang nilainya lebih kecil akan masuk ke kotak terlebih dahulu dan mengisi bagian disebelah kiri terlebih dahulu.Pada merge sort, data yang akan digabungkan berada pada suatu array, sebutlah array x dan array yang digunakan untuk menampung hasil gabung adalah array yang berbeda dari array x tersebut, sebutlah array y. Penyalinan elemen data dari array x ke array y ditentukan oleh hasil perbandingan data kelompok pertama x(i) dan data kelompok setelahnya x(j). Apabila nilai x(i) lebih kecil dibanding x(j) maka x(i) disalin ke y(k) kemudian indeks I dan k masing – masing ditambah satu. Proses ini akan berulang sampai seluruh data habis diproses.

7.Shell Sort
Ditemukan oleh Donal Shell pada tahun 1959. Merupakan algoritma paling efisien dari kelas sorting O(n2). Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen – elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak mengulangi atau merusak hasil sorting sebelumnya. Adapula nilai – nilai jarak yang dianjurkan adalah sebagai berikut :
1. Shell’s increment
1, 2, 4, 8
2. Hibbard’s increment
1, 3, 7, 15, …, 2k – 1
3. Sedgewick’s increment
1, 5, 19, 41, 109
Pada proses sorting, jarak yang diambil dilakukan secara menurun, sedangkan proses sorting elemennya dilakukan seperti insertion. Pada pengurutan elemen – elemen jarak lima, pengurutan dilakukan terhadap data ke-9, ke-4, ke-8, ke-3, dan seterusnya. Dimana jumlah data yang terlibat dalam suatu rangkaian pengurutan tidak selalu dua tetapi tergantung pada banyak data. Andaikan jumlah data adalah 11 maka pada rangkaian pengurutan pertama dilakukan pengurutan terhadap data ke-10, ke-5, dank e-0.

Contoh :
Rangkaian data :
1 2 3 4 5 6 7 8 9 10
2 5 1 3 9 7 8 0 5 4
Increment : 5
Maka data yang pertama dibandingkan adalah data ke-6 dengan ke-1 kemudian ke-7 dengan ke-2 , ke-8 dengan ke-3, ke-9 dengan ke-4, ke-10 dengan ke-5. Dan hasilnya adalah :
1 2 3 4 5 6 7 8 9 10
2 5 0 3 4 7 8 5 5 9
Increment : 2
Maka data yang selanjutnya dibandingkan adalah data ke-3 dengan ke-1, ke-4 dengan ke-2, ke-5 dengan ke-3, ke-6 dengan ke-4, ke-7 dengan ke-5, ke-8 dengan ke-6, ke-9 dengan ke-7,dan ke-10 dengan ke-8. Dan hasilnya adalah sebagai berikut :
1 2 3 4 5 6 7 8 9 10
0 3 2 5 4 5 5 7 8 9
Increment : 1
Maka data yang akan diurutkan adalah data ke-2 dengan ke-1, ke-3 dengan ke-2, ke-4 dengan ke-3, dan seterusnya sampai data ke-10 dengan ke-9. Dan hasilnya adalah sebagai berikut :
1 2 3 4 5 6 7 8 9 10
0 2 3 4 5 5 5 7 8 9
Dalam proses pengurutannya shell sort dapat lima kali lebih cepat bila dibandingkan dengan bubble sort dan kurang lebih dua kali lebih cepat bila dibandingkan dengan insertion sort. Namun, jika dibandingkan dengan merge, heap, ataupun quicksort, shellsort masih tergolong lebih lambat. Tetapi algoritma sorting yang begitu sderhana membuat shellsort merupakan pilihan yang cocok untuk melakukan sorting pada data kurang dari 5000 item atau data dengan ukuran tidak terlalu besar.