Algoritma - Radix Sort

Berbeda dengan algoritma penyortiran yang dijelaskan sebelumnya, jenis radix menggunakan bucket untuk mengurutkan item, setiap bucket menyimpan item dengan properti tertentu yang disebut key.

Radix sort adalah algoritma yang digunakan oleh mesin penyortiran kartu yang sekarang Anda temukan hanya di museum komputer. Kartu memiliki 80 kolom, dan di setiap kolom mesin dapat melubangi salah satu dari 12 tempat. Penyortir dapat secara mekanis “diprogram” untuk memeriksa kolom tertentu dari setiap kartu di dek dan mendistribusikan kartu ke salah satu dari 12 bin tergantung pada tempat yang telah dilubangi. Seorang operator kemudian dapat mengumpulkan kartu-kartu tersebut dengan nampan, sehingga kartu-kartu dengan tempat pertama yang dilubangi berada di atas kartu-kartu dengan tempat kedua dilubangi, dan seterusnya.

Algoritma penyortiran ini bekerja pada key integer dengan mengelompokkan digit yang berbagi posisi dan nilai yang sama. Radix adalah basis sistem bilangan. Seperti yang kita tahu bahwa dalam sistem desimal radix atau basis adalah 10. Jadi untuk menyortir beberapa angka desimal, kita membutuhkan 10 kotak posisional untuk menyimpan angka.

Secara simplenya Radix merupakan posisi dalam angka dengan mengurutkan nilai-nilai yang dimasukan (input) pertama kalinya, berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan pada radix keduanya, dst. Pada sistem desimal, radix merupakan digit dalam angka desimal. Misalnya, angka “102” mempunyai 3 digit yaitu 1,0 dan 2.

Ada dua jenis pemilahan radix: MSD radix sort mulai menyortir dari awal string (most signi cant digit). LSD radix sort mulai menyortir dari ujung string (least signi cant digit).

Kompleksitas Teknik Sorting Radix:
     Kompleksitas Waktu: O (nk)
     Kompleksitas Ruang: O (n + k)

Penjelasan tentang Radix seperti ini: Biasanya bucket adalah antrian, setiap kali radix sort dilakukan, bucket ini dikosongkan mulai dari bucket key terkecil hingga yang terbesar. Saat melihat item dalam daftar untuk mengurutkan, kita melakukannya dengan mengisolasi kunci tertentu, mis. dalam contoh angka ‘102’ yang akan kita tunjukkan memiliki maksimal tiga kunci untuk semua item, itu adalah key tertinggi yang perlu kita lihat adalah ratusan. Karena kita berurusan, ambillah dalam contoh ini, basis 10 angka yang kita miliki pada satu titik 10 nilai key yang mungkin 0…………9 yang masing-masing memiliki bucket sendiri.

Sebelum kita tunjukkan pada Anda versi sederhana dari radix sort ini, saya akan jelaskan dulu tentang mengisolasi key. Mengingat angka 102 jika kita melihat key pertama, yang kemudian kita dapat melihat bahwa dua diantaranya akan berproses atau maju pada key berikutnya. Bagian Puluhan, anda melihat angka 0 pada bagian itu. Pada akhirnya kita dapat melihat bahwa jumlahnya memiliki seratus tunggal. Nomor yang digunakan sebagai contoh memiliki total tiga key:

  • Satuan
  • Puluhan
  • Ratusan

Untuk penjelasan lebih lanjut bagaimana jika kita ingin menentukan berapa ribu jumlah dari 102? Jelas tidak ada, tetapi sering kita melihat nomor sebagai akhir seperti yang sering kita lakukan karena tidak begitu jelas sehingga ketika ditanya pertanyaan, berapa ribu yang Anda miliki pada angka 102 ketika menaruh angka dengan nol di lokasi itu, mis. 0102 di sini lebih jelas bahwa nilai key di lokasi ribuan adalah nol. Di sini, kita melihat bahwa ukuran key tidak signifikan, dan algoritma ini adalah kompleksitas linear O (n).

Untuk lebih jelasnya

48 81 93 25 104 38 112 70 11 61 43 58 163 9

Langkah awal untuk melakukan proses Radix Sort adalah mencari nilai terbesar. Anda menjumpai bahwa nilai terbesar dari data diatas adalah 163 sehingga pengelompokkan sama dengan penjelasan diatas yaitu

  • Satuan
  • Puluhan
  • Ratusan

Dan dilakukan tiga tahap.

Tahap pertama, cari nilai-nilai yang akan dikelompokkan berdasarkan angka satuan yang sama, sehingga terlihat kelompok sebagai berikut.

box1

Kemudian dijadikan satu lago ke dalam array menjadi sebagai berikut:

70 81 11 61 112 93 43 163 104 25 48 38 58 9

Selanjutnya ke tahap ke-2, nilai-nilai pada hasil pengelompokan diatas dilanjutkan pengelompokkannya berdasarkan nilai angka puluhan, sehingga didapat kelompok sebagai berikut:

box2

Kemudian satukan kembali ke dalam array menjadi sebagai berikut:

104 09 11 112 25 38 43 48 58 61 163 70 81 93

Tahap terakhir, nilai-nilai pada hasil pengelompokan diatas kemudian dikelompokkan berdasarkan pada angka ratusan, sehingga didapat kelompok sebagai berikut:

box3

Kemudian dijadikan satu lagi ke dalam array menjadi sebagai berikut:

9 11 25 38 43 48 58 61 70 81 93 104 112 163

Hal terakhir untuk diidentifikasi sebelum kita benar-benar menunjukkan kepada Anda implementasi sederhana dari jenis radix yang bekerja hanya pada bilangan bulat positif sebagaimana contoh diatas, dan mengharuskan Anda untuk menentukan ukuran key maksimum dalam daftar adalah bahwa kita memerlukan cara untuk mengisolasi key tertentu dengan mengelompokkan dalam tiga tahap . Solusinya sebenarnya sangat sederhana, tetapi tidak sering Anda ingin mengisolasi key dalam nomor sehingga kita menjelaskannya dengan jelas berdasarkan contoh diatas.