Counting Sort dan Implementasi di Pascal

OK, tulisan ini aku buat karena banyak temen2 di group yang terkendala dalam mengerjakan tugas Pra Praktikum tentang sorting, khususnya algoritma Counting Sort. Tulisan ini akan sedikit membahas counting sort dan implementasi langsung pada pascal *spoiler*

Apa itu Counting Sort?

Counting Sort adalah salah satu metode mengurutkan data yang dikenal. Ide dasarnya adalah seperti kita melakukan perhitungan pemilu yaitu dengan mencatat frekuensi atau banyaknya kemunculan data. Namun metode ini hanya cocok digunakan bila data yang digunakan bertipe integer dan dibatasi pada range tertentu. Namun menurut opini pribadi saya, cara ini termasuk tidak terlalu efisien dan “menyenangkan”. Apalagi untuk bahasa Pascal. Kenapa? Untuk mennggunaan metode ini kita harus membuat larik baru dengan range antara nilai minimum dan maksimum. Ya, kalo misal nilai minimum kita adalah 0 dan maksimum kita adalah 100 maka kita harus mendeklarasikan larik / array sebanyak 100 elemen (dari nilai minimum hingga nilai maksimum). Terbayang kan betapa borosnya penggunaan memori untuk metode ini. Apalagi Pascal adalah bahasa yang “sangat ketat” dalam hal deklarasi variabel / identifier. Dan Pascal tidak menerima pendeklarasian array dengan banyak indeks yang dinamis seperti banyaknya elemen dengan nilai dari variabel.

var larik : array[ var1 .. var2 ] of integer;

Deklarasi tersebut akan ditolak mentah-mentah oleh pascal. Padahal untuk melakukan metode ini kita harus

1. Menyediakan array (sebut saja TabCount [Min..Max] ) yang diinisialisasi dengan nol (ok, pascal menolak kita)

2. Mengisikan array TabCount dengan nilai frekuensi data yang ada di larik yang diurutkan (sebut saja T). Misal, untuk T dengan nilai 50 ada 3 buah, maka kita mengisikan indeks ke-50 pada TabCount dengan nilai 3. Seperti pemilu lah, calon ke-50 dapet 3 suara.

3. Membangun kembali larik T dengan cara melakukan pencacahan dari larik TabCount. Misal untuk nilai 20 ada 2 suara maka di larik T akan ditambahkan nilai 20 sebanyak 2x

Lalu ada solusi?? Ada…

Gunakan array dinamis

Kita dapat menggunakan array dinamis untuk membangun si TabCount atau array yang banyak elemennya sesuai dengan kondisi variabel. Lho, tadi katanya nggak bisa? Iya, kalo kita langsung mengisikan indeksnya emang nggak bisa. Kita harus mengassign panjang elemen lariknya. Intinya kita menentukan, larik tersebut ada berapa banyak slot dengan prosedur setlength(). Untuk kasusnya bisa dilihat di sini:

program A;
var larik : array of integer;
begin
setlength(larik, 20);
// coba lariknya
larik [19 ] := 3;
writeln(larik[19]);
end.

Sudah terlihat? Di awal kita nggak ngasih tau pascal berapa banyak slot yang harus digunakan untuk larik. Tapi di tengah2 perjalanan kita mengatur banyak slot untuk larik adalah 20. 20 Ini bisa diatur sesuai keadaan. Dengan menggunakan variabel kita bisa mengatur secara dinamis berapa banyak slot dari suatu larik. Perlu diketahui dengan demikian penomoran indeks dimulai dari 0. Ini sebenarnya sama saja dengan kita mendeklarasikan larik seperti demikian:

var larik : array[0..20] of integer;

namun pemberitahuan slotnya dilakukan di tengah perjalanan. Lalu bagaimana caranya kita melakukan pencacahan pemilu?
Gampang, kita tahu bahwa indeks dimulai dari 0 hingga 20 untuk data misal dari range 50 hingga 70. Sebenarnya rangenya sama saja kan, 20-0 = 70-50. Yup, hanya ada 20 elemen dan itu pas dengan larik kita !
lakukan saja pengurangan untuk nilai-nilai yang ada di data pusat dengan nilai minimum untuk dimasukkan ke tabel TabCount (pencacah)

Berikut working source code. Asumsikan bahwa:

TabI adalah variabel bertipe TblInt. TblInt sendiri adalah record dengan Data berupa tabel / array dengan 100 elemen dan sebuah data bernama Neff yang menyatakan indeks efektif.

type TblInt = record

Data : array[1..100] of integer;

Neff : integer;

end;

fungsi IndexMin akan memberikan index dimana nilai terendah dari array berada. Sedangkan nilai IndexMax akan memberikan index dimana nilai tertinggi dari array berada. Misal terdapat array dengan nilai 1,5,2,3,10,2. Nilai tertinggi (10) ada di index 5 maka fungsi IndexMax akan mengembalikan nilai 5 sedangkan nilai terendah (1) ada di index 1 maka fungsi IndexMin akan mengembalikan nilai 1.

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;

Semoga berguna🙂

14 Comments

  1. Mada

    klo ga usah pake var min bisa ga sat?
    langsung tulis “IndexMin(TabInt)” ?

    • Bisa, itu nilainya aq tampung di variabel biar nggak berkali-kali jalankan prosedur

      • Mada

        ok deh sat, tapi kok larik[i] sih? bukan TabCount[i]?
        itu buat inisialisai tabel kan?

      • joko

        numpang tanya gan kalo buat program bucket sort dengan pascal gimana ya thanks

  2. Sat, memang kita bisa membuat array dinamis dengan SetLength. Tapi procedure SetLength cuma bisa dipakai buat tipe data String (alias array of char). Selain itu, keluar error 201.

    Nah, kalaupun bisa, SetLength itu menset ukuran array dengan menset titik maksimumnya. Titik minimumnya pasti 1. Gak masalah sih kalau di counting sortnya nilai minimum dan maksimum sama-sama positif ( atau > 0 ). Tapi kalau nilai minimumnya negatif, berarti akan ada nilai yang diluar batas array. Bisa keluar error 216. Berlaku juga kalau ternyata nilai maksimum yang diset itu negatif. Lebih parah lagi kalau keduanya negatif. Nah, karena disoal kita sekarang ada kemungkinan input data bernilai negatif (tipe data integer), SetLength jelas jadi tidak bisa dipakai.

    Terima kasih…. btw buat SetLength bisa dibaca di menu help FPC atau http://www.freepascal.org/docs-html/rtl/system/setlength.html

    • ralat, ternyata memang SetLength bisa dipake buat array. http://www.freepascal.org/docs-html/ref/refsu14.html#x38-440003.3.1 . Tapi tetep aja, arraynya jadi diset dari 0 sampai titik maksimum – 1 (liat di referensinya).

    • Iy, kendala utamanya emang di situ. Dan perasaan aku pernah denger kalo dosen kita pernah ngomong kalo counting sort ini emang buat integer positif. Soalnya batas index emang positif

      • yah, dosen gw gak ngomong begitu….

        ah intinya counting sort gak efektif lah! hehehe

      • Lha, bukannya dosen kita sama ya – –

      • berarti gw yg gak denger. hehehe

  3. isee

    inspiring banget sat

  4. materinya bagus gan, semoga materi counting sortnya bsa saling melengkapi
    .
    http://www.markijar.blogspot.com/2015/04/contoh-program-counting-sort-c.html

Trackbacks

  1. Algoritma Pengurutan Secara Linear « Another Satria's Project

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: