Heap Sort

Heap Sort adalah sebuah algoritma pengurutan yang paling lambat dari algoritma yang memiliki kompleksitas O(n log n). Tetapi tidak seperti algoritma Merge Sort dan Quick Sort, algoritma Heap Sort tidak memerlukan rekursif yang besar atau menggunakan banyak tabel (array). Oleh karena itu, Heap Sort adalah pilihan yang baik untuk sebuah kumpulan data yang besar.

Algoritma ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari kumpulan data, lalu memindahkan data terbesar ke bagian belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang sampai array heap habis.

Jadi secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada data yang berukuran besar.

 Algoritma Heap Sort

function heapSort(a, count) {

var int start := count ÷ 2 - 1,

end := count - 1

while start ≥ 0

sift(a, start, count)

start := start - 1

while end > 0

swap(a[end], a[0])

sift(a, 0, end)

end := end - 1

}

function sift(a, start, count) {

var int root := start, child

while root * 2 + 1 < count {

child := root * 2 + 1

if child < count - 1 and

a[child] < a[child + 1]

child := child + 1

if a[root] < a[child]

swap(a[root], a[child])

root := child

else

return

}

}

Keterangan :

swap : prosedur yang telah didefiniskan, untuk menukar isi dari argumen 1 dengan argumen 2 Contoh implementasi

void heapSort(int numbers[], int array_size)

{

int i, temp;

for (i = (array_size / 2)-1; i >= 0; i--)

siftDown(numbers, i, array_size);

for (i = array_size-1; i >= 1; i--)

{

temp = numbers[0];

numbers[0] = numbers[i];

numbers[i] = temp;

siftDown(numbers, 0, i-1);

}

}

void siftDown(int numbers[], int root, int bottom)

{

int done, maxChild, temp;

done = 0;

while ((root*2 <= bottom) && (!done))

{

if (root*2 == bottom)

maxChild = root * 2;

else if (numbers[root * 2] > numbers[root * 2 + 1])

maxChild = root * 2;

else

maxChild = root * 2 + 1;

if (numbers[root] < numbers[maxChild])

{

temp = numbers[root];

numbers[root] = numbers[maxChild];

numbers[maxChild] = temp;

root = maxChild;

}

else

done = 1;

}

}