Kali ini saya akan membahas berbagai macam teknik pengurutan atau lebih dikenal dengan algoritma "sorting". Berikut adalah beberapa algoritma sorting beserta definisi dan prosedurnya.
1. Bubble Sort
Pengertian :
Bubble sort (metode gelembung) adalah metode / algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
Prosedur :
void bubble_sort () {
for (int i=1;i<n;i++) {
if (data[j]<data[j-1]) tukar (j,j-1); // ascending
}
}
2. Selection Sort
Pengertian :
Algoritma selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.
Prosedur :
void selection_sort(){
for (int i=0;i<n-1;i++){
pos = i;
for (int j=i+1;j<n;j++){
if (data[j]<data[pos]) pos = j; //ascending
}
If (pos != i ) tukar (pos,i);
}
}
3. Insertion Sort
Pengertian :
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Prosedur :
void insertion_sort() {
int temp;
for (int i=1;i<n;i++) {
temp = data[i];
j=i-1;
while (data[j]>temp && j>=0) {
data[j+1] = data[j];
j--;
}
data [j+1] = temp;
}
}
4. Heap Sort
Pengertian :
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap. Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.
Prosedur :
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1
5. Shell Sort
Pengertian :
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 menulangi atau merusak hasil sorting sebelumnya.
Prosedur :
void shellsort (int *r, int lo, int hi)
{
int d, i, j, temp;
for (d = hi – lo + 1; d>1; )
{
if (d>5) d = 1;else d=(5*d – 1)/11;
for (i=hi – d; i>=lo; i–)
{
temp = r[i];
for (j=i+d; (j<=hi) && (temp>r[j]); j+=d)
r[j-d] = r[j];
r[j-d] = temp;
}
}
}
6. Quick Sort
Pengertian :
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).
Prosedur :
void quicksort (int *arr, int kr, int kn)
{
int i, j, k;
if (kr<kn)
{
j=kr;
k=kn+;
do
{
do j++; while (j <= kn && arr[j] < arr[kr]);
do k–; while (arr[k] > arr[kr]);
if (j<k) tukar (&arr[j], &arr[k]);
}
while (j <= k);
tukar (&arr[kr], &arr[k]);
quicksort (arr, kr, k-1);
quicksort (arr, k+1, kn);
} }
7. Merge Sort
Pengertian :
Merge sort merupakan salah satu teknik sorting yang menurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan proses divide and conquer pada rekursi. Berikut adalah langkah kerja merge sort :
Devide : Memilah elemen – elemen dari data menjadi dua bagian.
Conquer : Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.
Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi akan berhenti jika telah mencapai lemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian.
Prosedur :
void mergesort (int *x, int n)
{
int *r, i, j, k, l1, l2, u1, u2, size;
r = (int *) malloc (n * sizeof (int));
size = 1;
while (size < n)
{
l1 = 0; k = 0;
while (l1+size < n)
{
l2 = l1+size;
u1 = l2 – 1;
u2 = (l2 + size – 1 < n) ? l2 + size – 1 : n-1;
for (i=l1; j=l2; i<=u1 && j<=u2; k++)
r[k] = (x[i] <= x[j]) ? x[i++] : x[j++];
while (i<=u1) r[k++] = x[i++];
while (j<=u2) r[k++] = x[j++];
l1 = u2+1;
}
for(i=l1; k<n; i++) r[k++] = x[i];
for(i=0; i<n; i++) x[i] = r[i];
size *= 2;
}
free(r); }
8. Radix Sort
Pengertian :
Radix sort adalah salah satu algoritma sorting yang dilakukan tanpa melakukan perbandingan antardata yang dijadikan sebagai input. Makna harfiah Radix dapat diartikan sebagai posisi dalam angka. Dalam system decimal, radix adalah digit dalam angka decimal. Misalkan angka 37 mempunyai nilai radix 3 dan 7. Berdasarkan urutan pemrosesan radix-nya, ada 2 macam Radix sort. Pertama adalah LSD (Least Significant Digit) yaitu proses dimulai dari radix yang paling tidak signifikan(digit yang paling kanan). Kedua adalah MSD (Most Significant Digit), yaitu proses dimulai dari radix yang paling signifikan (digit yang paling kiri).
Sekian tentang teknik pengurutan atau sorting. Jika ingin mengambil referensi ini mohon ijin dengan menuliskan komentar anda. Indahnya berbagi ilmu :D
