Zakkiyah Mubarak | Software Engineering | Politeknik Negeri Indramayu
Jika kalian mahasiswa informatika, ada banyak sekali metode algoritma
yang harus dipahami. Pada artikel kali ini saya akan berbagi metode
algoritma tentang sorting (pengurutan).
Berikut adalah rangkuman dari berbagai sumber tentang metode sorting yang akan kita bahas.
QUICK
SORT Quick
Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik
pemecahan data menjadi partisi-partisi (partition exchange sort). Pengurutan
ini berdasar pada prinsip devide and conquer. Devide adalah suatu langkah
memilah masalah menjadi sub – masalah dalam proses rekursi, sedangkan conquer
adalah proses menyelesaikan sub masalah tersebut, kemudian dilakukan pendekatan
terhadap masalah utama. Pada dasarnya prinsip kerjanya adalah membagi atau
memartisi sekumpulan data menjadi dua bagian sedemikian rupa sehingga elemen
ke-i berada tepat pada posisisnya, dimana semua elemen yang nilainya lebih
kecil daripada elemen ke-i akan terletak disebelah kirinya, sedangkan yang
mempunyai nilai lebih besar berada disebelah kanannya. Algoritma ini memiliki
kompleksitas O(n log n).
Algoritma Quick Sort:
- Pilih satu elemen secara acak sebagai pivot
- Pindahkan semua elemen yang lebih kecil ke sebelah
kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot
- Elemen
yang nilainya sama bisa disimpan di salah satunya.
- Lakukan sort secara rekursif terhadap sub-array
sebelah kiri dan kanan pivot.
- Algoritma
Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur
QUICKSORT.
Ilustrasi Dari Algoritma Quick Sort
Procedure
QuickSort (input/output a : array [1..n] of integer, input i , j : integer )
{Mengurutkan
tabel
a[i..j] dengan algoritma quick sort. Masukkan: Tabel a[i..j] yang sudah
terdefinisi elemen-elemennya. Keluaran: Tabel a[i..j] yang terurut
menaik.}
Deklarasi :
k : integer;
Algoritma :
if (i<j) then
Partisi(a,i,j,k) { Ukuran (a) > 1}
QuickSort(a,i,k)
QuickSort(a,k+1, j)
Endif
MERGE SORT
Merge sort merupakan salah satu teknik sorting yang
menurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan
proses divide and conquer pada rekursi.
Algoritma Merge Sort:
- Data dipecah menjadi 2 bagian, pertama bagian ini merupakan setengah
genap(jika datanya adalah genap) atau setengah minus satu (jika datanya adalah
ganjil) dari seluruh data yang ada.
- Kemudian dipecah kembali untuk masing-masing blok tadi sampai terdiri dari
satu data tiap blok.
- Kemudian digabungkan kembali dengan cara membandingkan pada bagian blok
yang sama, apakah data pertama itu lebih besar dari pada data ke-tengah+1, jika
iya maka data yang ke-tengah+1 dipindah sebagai data yang pertama, kemudian
data pertama sampai tengah digeser menjadi data kedua sampai ketengah+1.
- Demikian seterusnya sampai selesai menjadi suatu blok sedia kala.
Sehingga didalam sebuah metode merge sort itu merupakan metode yang menggunakan
fungsi rekursi untuk melakukan suatu penyelesaiannya.
Ilustrasi
Dari Algoritma Merge Sort
Algoritma mergesort(S,C)
Input: n elemen dari data S dan
comparator C
Output: data S terurut
berdasarkan C
if S.size()>1 (S1,S2) ←
partisi(S,n/2)
mergesort(S1,C)
mergesort(S2,C)
S ← merge(S1,S2)
RADIX SORT
Radix Sort merupakan metode sorting tanpa perbandingan atau
Non-Comparison Sort. Proses yang dilakukan dalam metode ini ialah
mengklasifikasikan data sesuai dengan kategori terurut yang tertentu dan dalam
tiap kategorinya dilakukan pengklasifikasian lagi dan berulang sesuai
kebutuhan. Dan kemudian subkategori-subkategori tersebut digabungkan kembali,
dilakukan hanya dengan metode sederhana concatenation.
Algoritma Radix Sort
- Ambil digit terkecil
dari setiap data.
- Kelompokkan data-data
berdasarkan digit. Untuk digit data sama, jangan ubah urutan data-data.
- Ulangi langkah pertama
untuk digit selanjutnya.
Ilustrasi Radix Sort
function pangkat(input nilai, pemangkat : integer) -->integer
{I.S. : nilai sudah terdefinisi}
{F.S. : menghasilkan fungsi pangkat}
Kamus: {Tidak ada}
Algoritma:
if (pemangkat = 0)
then
pangkat <-- 1
else
pangkat <-- nilai
* pangkat(nilai,pemangkat-1)
endif
endprocedure
procedure radix_sort_asc(input/output data : larik, digit_max : integer)
{I.S. : Data (1:N) sudah terdefinisi }
{F.S. : Menghasilkan data yang sudah terurut secara
Ascending}
