Sorting didefinisikan sebagai pengurutan sejumlahdata berdasarkan nilai kunci tertentu. Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau sebaliknya (descending).Algoritma Sorting termasuk salah satu contoh yangkaya akan solusi. Dalam makalah ini, hanya akan dibahas tiga algoritma sorting yang populer dipakai didunia informatika. Tiga algoritma tersebut adalah:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
1. Bubble Sort
Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti“gelembung air” untuk elemen struktur data yangsemestinya berada pada posisi awal. Cara kerjanyaadalah dengan berulang-ulang melakukan traversal(proses looping) terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut,nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap). Algoritma sortingini disebut juga dengan comparison sort dikarenakanhanya mengandalkan perbandingan nilai elemen untukmengoperasikan elemennya.
Algoritma Bubble Sort
Algoritma bubble sort dapat diringkas sebagaiberikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
a.Lakukan traversal untuk membandingka dua elemen berdekatan. Traversal ini
dilakukan dari belakang.
b.Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu
dengan bagian struktur data yang telah diurutkan.
c.Ulangi langkah di atas untuk struktur datayang tersisa.
2. Selection Sort
Algoritma sorting sederhana yang lain adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksianelemen struktur data. Untuk sorting ascending(menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya,kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuksorting descending (menurun), elemen yang paling. besar yang disimpan indeksnya kemudian ditukar.
Algoritma Selection Sort
Algoritma selection sort dapat dirangkum sebagaiberikut:
a.Temukan nilai yang paling minimum (atau sesuaikeinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum
b.Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.
c.Ulangi langkah di atas untuk bagian struktur datayang tersisa.
3. Insertion Sort
Cara kerja insertion sort sebagaimana namanya.Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yangtelah di-sorting dan bagian yang belum
Algoritma Insertion Sort
Algoritma Insertion Sort dapat dirangkum sebagai berikut:
a.Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
b.Bandingkan nilainya dengan elemen sebelumnya.
c.Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1
d.Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
e.Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
f.Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
1. Bubble Sort
Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti“gelembung air” untuk elemen struktur data yangsemestinya berada pada posisi awal. Cara kerjanyaadalah dengan berulang-ulang melakukan traversal(proses looping) terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut,nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap). Algoritma sortingini disebut juga dengan comparison sort dikarenakanhanya mengandalkan perbandingan nilai elemen untukmengoperasikan elemennya.
Algoritma Bubble Sort
Algoritma bubble sort dapat diringkas sebagaiberikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
a.Lakukan traversal untuk membandingka dua elemen berdekatan. Traversal ini
dilakukan dari belakang.
b.Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu
dengan bagian struktur data yang telah diurutkan.
c.Ulangi langkah di atas untuk struktur datayang tersisa.
2. Selection Sort
Algoritma sorting sederhana yang lain adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksianelemen struktur data. Untuk sorting ascending(menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya,kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuksorting descending (menurun), elemen yang paling. besar yang disimpan indeksnya kemudian ditukar.
Algoritma Selection Sort
Algoritma selection sort dapat dirangkum sebagaiberikut:
a.Temukan nilai yang paling minimum (atau sesuaikeinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum
b.Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.
c.Ulangi langkah di atas untuk bagian struktur datayang tersisa.
3. Insertion Sort
Cara kerja insertion sort sebagaimana namanya.Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yangtelah di-sorting dan bagian yang belum
Algoritma Insertion Sort
Algoritma Insertion Sort dapat dirangkum sebagai berikut:
a.Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
b.Bandingkan nilainya dengan elemen sebelumnya.
c.Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1
d.Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
e.Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
f.Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).
