Algoritma Sorting

Definisi Algoritma

Algoritma adalah kumpulan langkah sistematis untukmemperoleh hasil yang diinginkan1. Sebelum sebuahalgoritma dijalankan, biasanya ada suatu kondisi awal(initial state)yang harus dipenuhi. Kemudian, langkah-langkah ini diproses hingga mencapai suatukondisi akhir (final state).Salah satu contoh dari algoritma adalah Sorting(pengurutan).

Definisi Sorting


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 akandibahas lima algoritma sorting yang populer dipakai didunia informatika. Lima algoritma tersebut adalah:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort, dan
5. Quick Sort.

Bubble Sort

Bubble Sort merupakan cara pengurutan yangsederhana. 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. Jikaternyata 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:

1. Lakukan traversal untuk membandingkan
dua elemen berdekatan. Traversal ini
dilakukan dari belakang.
2. 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.
3. Ulangi langkah di atas untuk struktur data
yang tersisa.

Selection Sort

Algoritma sorting sederhana yang lain adalahSelection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksianelemen struktur data. Untuk sorting ascending(menaik), elemen yang paling kecil di antara elemenelemenyang belum urut, disimpan indeksnya,kemudian dilakukan pertukaran nilai elemen denganindeks yang disimpan tersebut dengan elemen yangpaling 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:
1 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.
2 Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.
3. Ulangi langkah di atas untuk bagian struktur datayang tersisa.

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. Dariproses iterasi, seperti biasa, terbentuklah bagian yangtelah di-sorting dan bagian yang belum

Algoritma Insertion Sort

Algoritma Insertion Sort dapat dirangkum sebagai berikut:
1. Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
2. Bandingkan nilainya dengan elemen sebelumnya.
3. 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).
4. Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
5. Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
6. Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).

Merge Sort

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebihberarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelumkemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,
1. Sebuah list yang kecil membutuhkan langkahyang lebih sedikit untuk pengurutan daripadasebuah list yang besar.
2. Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yanglebih sedikit daripada membentuk sebuah listterurut dari dua buah list tak terurut. Contoh:hanya diperlukan satu kali traversal untukmasing-masing list jika keduanya sudahterurut.


Algoritma Merge Sort

Algoritma Merge Sort sederhananya, dapat ditulis berikut:
1. Bagi list yang tak terurut menjadi dua samapanjang atau salah satunya lebih panjang satu elemen.
2. Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
3. Gabung 2 sublist kembali menjadi satu list terurut.

Quick Sort

Quick Sort adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.

Algoritma Quick Sort

Algoritma ini terdiri dari 4 langkah utama:
1. Jika struktur data terdiri dari 1 atau 0 elemenyang harus diurutkan, kembalikan strukturdata itu apa adanya.
2. Ambil sebuah elemen yang akan digunakansebagai pivot point (poin poros). (Biasanyaelemen yang paling kiri.)
3. Bagi struktur data menjadi dua bagian – satudengan elemen-elemen yang lebih besar
daripada pivot point, dan yang lainnya denganelemen-elemen yang lebih kecil dari pada pivot point.
4. Ulangi algoritma secara rekursif terhadapkedua paruh struktur data.

KESIMPULAN

Algoritma yang mudah dalam hal implementasi adalahBubble Sort, Selection Sort, dan Insertion Sort.Ketiganya memiliki kompleksitas O(n2). Di antaraalgoritma ini, yang paling effisien adalah InsertionSort. Algoritma yang lebih mangkus adalah MergeSort dan Quick Sort dengan kompleksitasnya adalah O(n log n). Adapun yang paling mangkus dari limaalgoritma ini adalah Quick Sort.