Heap sort, pengurutan yang sederhana

Salah satu kategori algoritma klasik dan paling dasar yand ada adalah tentang pengurutan data. Berbagai algoritma telah dikembangkan untuk keperluan ini, salah satunya adalah Heap sort. Artikel ini akan membahas tentang apa itu heap sort dan juga disertai dengan implementasi di dalam C++. Kalau misalnya teman-teman bingung dalam programming, teman-teman bisa mengunjungi kategori artikel belajar pemrograman yang saya tulis sebelumnya.

Oke, lanjut!

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);
}
}

Ada pertanyaan?😀

7 Comments

  1. bagaimana langkah sederhana pengurutan heap sort ??

  2. terima kasih sekali atas contoh program nya..😀

    • Terima kasih, semoga bermanfaat😀

  3. bingung

  4. dhez

    ga ngerti

  5. MUHAMMAD RIFQI M

    kak saya lagi ada project besar untuk UAS mata pelajaran ASD , saya angkatan 2012 mahasiswa teknik komputer UB , kalo boleh dengan rasa hormat saya , bolehkah saya punya contact mas nya (no tlp) ada yang ingin saya tanyakan , makasih

    • silahkan email aja ke
      satria [at] arc [dot] itb [dot] ac [dot] id

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: