Pengurutan Data

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<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(data[i]<data[j])
tukar(&data[i],&data[j]);
}
}
}

http://allaboutalgoritma.blogspot.com/2009/06/metode-pemograman-algoritma-exchange.html

Selection Sort

Pada pembahasan kali ini admin penunjang belajar akan menjelaskan tentang Algoritma Selection Sort. Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut :

1. Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
2. Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.
3. Ulangi langkah 1 dan 2 dengan j = j + i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.

Bila diketahui data awal berupa: 44 55 12 42 94 18 6 67, maka langkah per langkah pengurutan dengan metode selection sort adalah sebagai berikut:

Tabel 2. Langkah demi langkah pengurutan dengan metode Selection Sort.

Berikut contoh program dari metode selection sort dengan menggunakan bahasa C :

void selectionsort(int arr[ ]) {
   int i,j;
   for (i = 0; i < N; i++) {
      int min = arr[i];
      int pos = i;
      for (j = i; j < N; j++) {
 

           /* Cari nilai yang terkecil */
           if (arr[j] < min) {
           min = arr[j];
           pos = j;
        }
      }
      

      /* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */
      if(i!=pos) {
         int temp = arr[i];

         arr[i] = arr[pos];
         arr[pos] = temp;
       }
    }

http://penunjangbelajar.blogspot.com/2012/04/algoritma-selection-sort.html

Heap Sort

Heapsort adalah metode mengurutkan dengan memanfaatkan sifat yang dimiliki oleh struktur data heap. Heap sendiri adalah sebuah “binary search tree” dengan sifat parent memiliki nilai >= nilai yang ada di anaknya. Meski dikatakan ia adalah sebuah binary search tree, namun heap lebih diarahkan ke konsepsi / menganggap suatu array memiliki sifat heap.

Ambil suatu indeks dari array, misal i. Jika dianggap elemen di i sebagai node, ia akan disebut parent jika ia memiliki anak dengan indeks 2i+1 dan 2i+2. Contoh: indeks 0 akan memiliki anak di indeks 1 dan 2.

Heapsort dimulai dengan membentuk array memenuhi sifat heap untuk seluruh indeks. Setelah melakukan penataan, dipastikan elemen terbesar akan berada di root / node paling atas heap (indeks 0). Nah, selanjutnya adalah kita pindahkan elemen terbesar itu ke belakang barisan. Untuk node dari 0 hingga n-2, lakukan penataan lagi dan pemindahan elemen terbesar ke belakang. Hasilnya adalah elemen akan terurut secara ascending setelah proses ini.

Source code dalam C++ dapat teman-teman temukan di sini:

void siftDown(int arr[], int start, int end) {
/** start dan end berada dalam jangkauan array yang terdefinisi dengan start < end **/
/** Menata array dalam jangkauan sesuai kriteria sifat heap **/
/** deklarasi **/
int root=start;        // pencarian dimulai dari root
int child;            // menyimpan indeks anak yang diperiksa
int inswap;            // indeks untuk swap
int temp;
/** sift ketika root masih memiliki anak **/
/** indeks anak ada di 2*root+1 dan 2*root+2 **/
while(2*root+1 <= end) {
child     = 2*root+1;    // dapatkan data anak
inswap     = root;
/** Ambil elemen terbesar dan letakkan di root **/
if(arr[inswap] < arr[child])
inswap = child;
if(child+1 <= end)
if(arr[inswap] < arr[child+1])
inswap = child+1;
if(root!=inswap) {
// pertukarkan
temp         = arr[root];
arr[root]     = arr[inswap];
arr[inswap]    = temp;
// track down, buat agar struktur heap di bawah konsisten
root = inswap;
} else return;
}
}

//————————————————————————————

void heapify(int arr[], int n) {
/** n = jumlah elemen di array **/
    /** heapidy membentuk heap dengan bantuan siftdown. Hasil akhirnya adalah array yang tertata sesuai sifat heap **/
/** mulai heapify dari tengah dan terus naik hingga indeks 0 **/
int start=(n-2)/2;
for(int i=start; i>=0; i–)
siftDown(arr,i,n-1);
}

//————————————————————————————

void heapsort(int arr[], int n) {
/** n = jumlah elemen di array **/
/** lakukan heapify untuk menciptakan heap semu **/
heapify(arr,n);
/** tercipta heap, elemen terbesar ada di root (indeks 0)
*  lakukan iterasi untuk setiap langkah, pindahkan root ke akhir,
*  decrement indeks dan lakukan penataan ulang lagi
*/
int end=n-1;
int temp;
while(end>0) {
// pindahkan root ke akhir
temp     = arr[0];
arr[0]     = arr[end];
arr[end]= temp;
// majukan end
end -= 1;
// lakukan penataan ulang dengan siftDown
siftDown(arr,0,end);
}
}

Referensi:

http://allaboutalgoritma.blogspot.com/2009/06/metode-pemograman-algoritma-exchange.html

http://penunjangbelajar.blogspot.com/2012/04/algoritma-selection-sort.html

http://id.wikipedia.org/wiki/Quicksort

http://id.wikipedia.org/wiki/Urut_gabung 

http://nanaleni.blogspot.com/2015/04/pengurutan-data.html