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;

}

}

Algoritma Counting Sort

   Algoritma Counting Sort

Counting Sort adalah algoritma pengurutan efektif dan efisien yang melakukan pengurutan dengan ide dasar meletakkan elemen pada posisi yang benar, dimana penghitungan posisi yang benar dilakukan dengan cara menghitung (counting) elemen-elemen dengan nilai lebih kecil atau sama dengan elemen tersebut. Contoh sederhana saja jika terdapat 12 elemen yang lebih kecil daripada x, maka x akan mendapatkan posisinya di posisi 13.

Tentu saja, sedikit modifikasi harus dilakukan agar metode ini dapat menangani kasus di mana terdapat elemen elemen lain yang nilainya sama dengan x. Dimana tentu saja kita tidak dapat menempatkan semua elemen yang nilainya sama dengan x di posisi yang sama.

Keungggulan Algoritma Counting Sort

Keunggulan dari algoritma counting sort adalah dapat mengurutkan dengan waktu yang lebih singkat, karena tidak membandingkan dengan elemen lain.

Kelemahan Algoritma Counting Sort

Kelemahan algoritma counting sort adalah menggunakan array yang terlalu banyak.

Program komputer merupakan instruksi-instruksi logis yang tertulis dalam sebuah source code yang dibaca oleh komputer dan selanjutnya dieksekusi. Salah satu masalah yang dapat diselesaikan oleh komputer adalah pengurutan data. Baik pengurutan data dari yang terbesar ke yang terkecil ataupun sebaliknya.

Di antara banyak algoritma pengurutan tersebut terdapat satu kategori algoritma pengurutan yang dalam prosesnya tidak melakukan pembandingan antar data. Yang sering disebut Non-Comparison Sorting Algorithm, atau dalam bahasa IndonesiaAlgoritma Pengurutan-Tanpa-Pembandingan.

Tulisan ini akan mencoba membahas salah satu teknik sorting yang tanpa melakukan perbandingan data. Ada dua teknik algoritma untuk melakukan sorting tanpa membandingkan data yaitu : Counting Sort dan Radix Sort. Dalam tulisan ini akan dibahas teknik Counting Sort.

Secara umum yang proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan dalam tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai dengan kebutuhan, kemudian

subkategori-subkategori tersebut digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana concatenation.

Ide dasar dari counting sort adalah menentukan, untuk setiap elemen x jumlah yang lebih kecil dari x setelah itu informasi ini digunakan untuk menentukan1 posisi x. Contoh sederhana misalkan terdapat 6 elemen yang lebih kecil dari x maka x menjadi posisi ke 7.

 algoritma counting sort :

algorithm counting_sort (A,k)

Input : A : array [1..n] of integer, k: max (A)

Output : B : array [1..n] of integer

               for i = 1 to k do

           C[i] = 0

               for j = 1 to length(A) do

                  C[A[j]] = C[A[j]] + 1

               for 2 = 1 to k do

                  C[i] = C[i] + C[i-1]

               for j = 1 to length(A) do

                  B[C[A[j]]] = A[j]

                  C[A[j]] = C[A[j]] - 1

        return B

Setelah dilakukan implementasi algoritma tersebut ke dalam program, dalam hal ini menggunakan JavaScript, berikut merupakan script programnya.

procedure CountingSortDesc(var TabI: TblInt);
var iLoop1,iLoop2,k : integer;
min,max : integer;
tbCount : array of integer;
begin
{
Inisialisasi array
}
min := TabI.Data[IndexMin(TabI)];
max := TabI.Data[IndexMax(TabI)];
setlength(tbCount, max+1 – min) ;
for iLoop1 := 0 to (max-min) do
tbCount[iLoop1] := 0;
for iLoop1 := IMin to TabI.Neff  do
tbCount[ TabI.Data[iLoop1] – min ] := tbCount[ TabI.Data[iLoop1] – min ] + 1;
iLoop2 := TabI.Neff+1;
for iLoop1 := 0 to (max+1-min) do
begin
if(tbCount[iLoop1] <> 0) then
for k := 1 to tbCount[iLoop1] do
begin
iLoop2 := iLoop2 – 1;
TabI.Data[iLoop2] := iLoop1+min;
end;
end;
end;