Macam macam Sorting pada Java (Radix Sort, Exchange Sort, Pigeonhole Sort)

Sorting

Salah satu bagian penting dari struktur data adalah proses pengurutan data-data  itu sendiri. Data akan terkadang akan berada dalam bentuk yang tidak berpola ataupun dengan pola tertentu yang tidak kita inginkan, namun dalam penggunaanya, kita akan selalu ingin menggunakan data-data tersebut dalam bentuk yang rapi atau berpola sesuai dengan yang kita inginkan. Maka dari itu proses sorting adalah proses yang sangat penting dalam struktur data, terlebih untuk pengurutan data yang bertipe numerik ataupun karakter.

Sorting adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu ataupun secara acak, sehingga menjadi tersusun secara teratur menurut aturan tertentu.

Pada umumnya ada 2 macam pengurutan, yaitu:

• Pengurutan secara ascending (urut naik).
• Pengurutan secara descending (urut turun).

Contoh Contoh : Data  :  Array [1..6] of Byte = (22, 10, 15, 3, 8, 2); 

Data Acak : 22 10 15 3 8 2 

Terurut Ascending : 2 3 8 10 15 22 

Terurut Descending : 22 15 10 8 3 2

Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.

Disini saya akan menjelaskan tentang Radix Sort, Exchange Sort, dan Pigeonhole Sort.

Radix sort

Ide dasar dari metode Radix sort ini adalah

mengkategorikan data-data menjadi sub kumpulan

subkumpulan data sesuai dengan nilai radix-nya,

mengkonkatenasinya, kemudian

mengkategorikannya kembali berdasar nilai radix

            contoh: 

Exchange Sort

Sekarang kita akan mempelajari tentang metode pengurutan exchange sort. Metode pengurutan excahange sort mirip dengan metode pengurutan Buble Sort *bisa di katakan bersaudara hehehe. Tapi dalam cara membandingan antar elemennya memiliki tentu memiliki perbedaan.

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

cara pengurutan exchange sort

Prosedur Exchange Sort

void exchange_sort(int data[])
{
for(int i=0;i{
for(int j=i+1;j{
if(data[i]tukar(&data[i],&data[j]);
}
}
}

Pigeonhole Sort

Semua contoh saat ini tampaknya mengimplementasi menghitung, mengurutkan. Dan Pigeonhole Sort, ketika menyortir data yang kompleks dengan struktur sebuah kunci, terus melacak dari semua elemen pada kunci tertentu (karena unsur-unsur yang sama masih berbeda); Alih-alih hanya menyimpan hitungan seperti menghitung semacam (yang hanya berlaku untuk jenis nilai sederhana).

Contoh Aplikasinya :

public static void pigeonhole_sort(int[] a)
{
    // size of range of values in the list (ie, number of pigeonholes we need)
    int min = a[0], max = a[0];
    for (int x : a) {
        min = Math.min(x, min);
        max = Math.max(x, max);
    }
    final int size = max - min + 1;
 
    // our array of pigeonholes
    int[] holes = new int[size];  
 
    // Populate the pigeonholes.
    for (int x : a)
        holes[x - min]++;
 
    // Put the elements back into the array in order.
    int i = 0;
    for (int count = 0; count < size; count++)
        while (holes[count]-- > 0)
            a[i++] = count + min;
}