Penjelasan Algoritma Counting Sort dan Contohnya

Pada artikel ini kita akan membahas tentang algoritma counting sort. Counting Sort merupakan teknik penyortingan yang beroperasi dengan menghitung objek yang memiliki nilai kunci berbeda seprti hashing.

Kemudian melakukan beberapa operasi aritmatika untuk menghitung posisi indeks setiap objek dalam urutan keluaran.

Algoritma Counting Sort efektif apabila jangkauan tidak lebih besar dari jumlah objek yang akan disortir.

Langkah-Langkah Algoritma Counting Sort

• Langkah awal yaitu mencari nilai maksimum pada input array. Sebagai contoh kita membuat variabel “max” untuk menampung nilai maksimum
• Membuat array “count” dengan ukuran (max + 1) diinisialisasi dengan semua nol. Array ini akan digunakan untuk menyimpan jumlah setiap elemen.
• Kemudian simpan hitungan setiap elemen unik dalam array “count”, jika terdapat elemen yang berulang cukup tambah jumlahnya.
• Ubah array “count” dengan cara menambahkan pada setiap elemen sebelumnya secara kumulatif. Langkah ini memastikan bahwa setiap posisi dalam array “count” menunjukan posisi awal pada setiap elemen yang terdapat dalam array “output” yang diurutkan.
• Buat variabel sementara dengan value panjang dari inputan array.
• Langkah selanjutnya melakukan looping data dari elemen terakhir. Untuk setiap elemen, temukan hitungannya dalam array “count” dan gunakan hitungan tersebut sebagai indeks untuk menentukan posisi dalam array “output”. Kemudian kurangi dengan jumlah dalam array “count” sebesar 1.
• Array “output” sementara sekarang berisi elemen yang diurutkan berdasarkan jumlahnya.
• Langkah terakhir salin elemen dari array “output” sementara kembali ke dalam array inputan untuk mendapatkan sorting data.

Contoh Program

Berikut ini contoh program algoritma counting sort menggunakan javascript.

function sort(arr) {
  // nilai Max
  let max = Math.max(...arr);

  // array count dengan ukuran (max + 1)
  let count = new Array(max + 1).fill(0);

  /* menyimpan inputan array ke dalam array "count" 
     dan jika terdapat elemen yang berulang cukup ditambah jumlahnya. 
  */
  for (let i = 0; i < arr.length; ++i) count[arr[i]]++;

  // menambahkan setiap elemen sebelumnya
  for (let i = 1; i < count.length; ++i) count[i] += count[i - 1];

  // buat array output
  let output = new Array(arr.length);

  for (let i = arr.length - 1; i >= 0; i--) {
    let value = arr[i];
    let position = count[value] - 1;

    // kurangi hitungan dalam array
    count[value]--;

    // Tetapkan nilai ke array output pada posisi yang benar
    output[position] = value;
  }

  return output;
}

// Contoh array yang digunakan
let arr = [3, 2, 5, 8, 5, 3];
arr = sort(arr);

console.log(arr);

Kesimpulan

Kita berhasil mempelajari algoritma counting sort, kalian dapat menerapkan algoritma ini dalam mengurutkan data.

Penting untuk dicatat bahwa algoritma ini hanya berlaku ketika rentang nilai kunci relatif kecil dibandingkan dengan ukuran input, jika rentang secara signifikan lebih besar, persyaratan memori dari array penghitungan dapat menjadi tidak praktis, dan alogritma pengurutan lainnya mungkin lebih cocok.

Sekian untuk artikel ini semoga bermanfaat dan jika ada pertanyaan kalian dapat komentar di bawah ini.