Kita bahas Radix Sort dari awal secara perlahan, mulai dari dataset, proses pengurutan setiap tahap, sampai program Python-nya. Kuncinya adalah Radix Sort mengurutkan angka berdasarkan digit satuan, kemudian puluhan, lalu ratusan.
1. Dataset yang akan diurutkan
Misalnya, kita mempunyai 8 bilangan berikut.
Data awal (belum terurut)
170, 45, 75, 90, 802, 24, 2, 66
Target kita adalah mengurutkan bilangan dari yang terkecil ke yang terbesar.
Hasil akhirnya nanti:
2, 24, 45, 66, 75, 90, 170, 802
Tetapi, Radix Sort tidak langsung menghasilkan urutan tersebut. Kita harus melewati tiga tahap pengurutan.
2. Memahami digit satuan, puluhan, dan ratusan
Sebelum mulai, perhatikan tabel berikut.
| Bilangan | Ratusan | Puluhan | Satuan |
|---|---|---|---|
| 170 | 1 | 7 | 0 |
| 45 | 0 | 4 | 5 |
| 75 | 0 | 7 | 5 |
| 90 | 0 | 9 | 0 |
| 802 | 8 | 0 | 2 |
| 24 | 0 | 2 | 4 |
| 2 | 0 | 0 | 2 |
| 66 | 0 | 6 | 6 |
Contoh cara membacanya:
- Angka 170 memiliki satuan 0, puluhan 7, dan ratusan 1.
- Angka 45 memiliki satuan 5 dan puluhan 4.
- Angka 802 memiliki satuan 2, puluhan 0, dan ratusan 8.
- Angka 2 dianggap memiliki satuan 2, puluhan 0, dan ratusan 0.
Penting: Kita tidak mengurutkan berdasarkan nilai keseluruhan terlebih dahulu. Kita mengurutkan berdasarkan posisi digit, dimulai dari paling kanan.
3. Tahap pertama — Mengurutkan digit satuan
Pada tahap pertama, kita hanya melihat angka paling kanan dari setiap bilangan.
Data awal:
170, 45, 75, 90, 802, 24, 2, 66
Sekarang kita masukkan setiap bilangan ke kelompok digit satuan dari 0 sampai 9.
Pengelompokan digit satuan
0
170, 90
1
—
2
802, 2
3
—
4
24
5
45, 75
6
66
7
—
8
—
9
—
Perhatikan contoh berikut:
- 170 masuk kelompok 0 karena digit satuannya 0.
- 90 masuk kelompok 0 karena digit satuannya 0.
- 802 masuk kelompok 2 karena digit satuannya 2.
- 2 juga masuk kelompok 2 karena digit satuannya 2.
- 45 dan 75 masuk kelompok 5 karena digit satuannya 5.
Setelah itu, gabungkan kelompok dari digit 0 sampai digit 9 secara berurutan.
Hasil tahap pertama:
170, 90, 802, 2, 24, 45, 75, 66
Mengapa 170 tetap sebelum 90? Karena keduanya masuk kelompok 0 dan urutan relatif data harus dipertahankan. Prinsip ini disebut stable sorting.
Ingat: Pada tahap pertama, kita belum peduli apakah 170 lebih besar daripada 90. Kita hanya melihat digit satuannya.
4. Tahap kedua — Mengurutkan digit puluhan
Sekarang gunakan hasil tahap pertama, bukan dataset awal.
Data saat ini:
170, 90, 802, 2, 24, 45, 75, 66
Kali ini kita melihat digit puluhan.
| Bilangan | Digit puluhan |
|---|---|
| 170 | 7 |
| 90 | 9 |
| 802 | 0 |
| 2 | 0 |
| 24 | 2 |
| 45 | 4 |
| 75 | 7 |
| 66 | 6 |
Bilangan yang hanya memiliki satu digit, seperti 2, dianggap memiliki digit puluhan 0.
Sekarang masukkan ke kelompok digit puluhan:
0
802, 2
1
—
2
24
3
—
4
45
5
—
6
66
7
170, 75
8
—
9
90
Gabungkan kelompok mulai dari digit 0 sampai 9.
Hasil tahap kedua:
802, 2, 24, 45, 66, 170, 75, 90
Mungkin terlihat aneh karena 802 berada di depan 2. Namun, ini benar untuk sementara karena digit puluhan 802 adalah 0, sedangkan digit puluhan 2 juga 0. Urutan kedua bilangan itu dipertahankan dari tahap sebelumnya.
Ingat: Pada tahap kedua, kita hanya mengurutkan digit puluhan. Digit satuan yang sudah diproses tidak diurutkan ulang secara terpisah.
5. Tahap ketiga — Mengurutkan digit ratusan
Sekarang gunakan hasil tahap kedua:
802, 2, 24, 45, 66, 170, 75, 90
Kita melihat digit ratusan setiap bilangan.
| Bilangan | Digit ratusan |
|---|---|
| 802 | 8 |
| 2 | 0 |
| 24 | 0 |
| 45 | 0 |
| 66 | 0 |
| 170 | 1 |
| 75 | 0 |
| 90 | 0 |
Bilangan yang tidak mempunyai digit ratusan dianggap memiliki digit ratusan 0.
Sekarang kelompokkan berdasarkan digit ratusan:
0
2, 24, 45, 66, 75, 90
1
170
8
802
Gabungkan kembali kelompok dari digit 0 sampai digit 9.
Hasil akhir:
Data setelah Radix Sort
2, 24, 45, 66, 75, 90, 170, 802
Semua bilangan sekarang sudah terurut dari yang terkecil ke terbesar.
Mengapa hasilnya sudah benar? Karena semua bilangan memiliki paling banyak tiga digit. Setelah digit satuan, puluhan, dan ratusan diproses secara berurutan dan stabil, urutan bilangan menjadi benar.
6. Program Python Radix Sort lengkap
Sekarang kita buat program yang menampilkan proses setiap tahap agar mudah dipelajari.
# PROGRAM PENGURUTAN RADIX SORTdef radix_sort(data): # Mencari nilai terbesar nilai_maksimum = max(data) # Memulai dari digit satuan posisi = 1 tahap = 1 # Mengulang selama masih ada digit yang perlu diurutkan while nilai_maksimum // posisi > 0: # Menyiapkan 10 kelompok digit: 0 sampai 9 bucket = [[] for i in range(10)] print("\nTahap", tahap) # Memasukkan setiap angka ke kelompok digit for angka in data: digit = (angka // posisi) % 10 bucket[digit].append(angka) # Menampilkan isi setiap kelompok for digit in range(10): if bucket[digit]: print("Digit", digit, ":", bucket[digit]) # Menggabungkan kelompok sesuai urutan digit data_baru = [] for kelompok in bucket: data_baru.extend(kelompok) # Memperbarui data untuk tahap berikutnya data = data_baru print("Hasil tahap", tahap, ":", data) # Berpindah ke posisi digit berikutnya posisi *= 10 tahap += 1 return data# DATA AWALangka = [170, 45, 75, 90, 802, 24, 2, 66]print("Data sebelum diurutkan:")print(angka)# Menjalankan Radix Sorthasil = radix_sort(angka)print("\nData setelah diurutkan:")print(hasil)7. Memahami bagian penting kode
Bagian ini yang perlu benar-benar dipahami.
A. Menyiapkan kelompok digit
bucket = [[] for i in range(10)]Kode tersebut membuat 10 kelompok kosong, mulai dari kelompok 0 sampai kelompok 9.
Secara sederhana, bentuknya seperti ini:
bucket = [ [], [], [], [], [], [], [], [], [], []]Setiap kelompok akan menampung angka yang memiliki digit tertentu pada posisi yang sedang diproses.
B. Mengambil digit yang akan diurutkan
digit = (angka // posisi) % 10Contoh untuk angka 170:
| Proses | Perhitungan | Hasil |
|---|---|---|
| Satuan | (170 // 1) % 10 | 0 |
| Puluhan | (170 // 10) % 10 | 7 |
| Ratusan | (170 // 100) % 10 | 1 |
Operator // adalah pembagian bulat, sedangkan % adalah operator sisa bagi.
C. Memasukkan angka ke kelompok
bucket[digit].append(angka)Jika nilai digit adalah 5, angka akan dimasukkan ke kelompok nomor 5.
Misalnya, angka 45 memiliki digit satuan 5, sehingga masuk ke bucket[5].
D. Menggabungkan kelompok
data_baru = []for kelompok in bucket: data_baru.extend(kelompok)Program membaca kelompok mulai dari 0 sampai 9. Semua angka digabungkan kembali dengan tetap mempertahankan urutan angka di dalam setiap kelompok.
E. Berpindah posisi digit
posisi *= 10Nilai posisi berubah seperti berikut:
1untuk digit satuan.10untuk digit puluhan.100untuk digit ratusan.1000untuk digit ribuan, jika diperlukan.
Pengulangan berhenti ketika digit terbesar sudah selesai diproses.
8. Ringkasan proses Radix Sort
| Tahap | Digit yang diurutkan | Hasil |
|---|---|---|
| Data awal | Belum diurutkan | 170, 45, 75, 90, 802, 24, 2, 66 |
| 1 | Satuan | 170, 90, 802, 2, 24, 45, 75, 66 |
| 2 | Puluhan | 802, 2, 24, 45, 66, 170, 75, 90 |
| 3 | Ratusan | 2, 24, 45, 66, 75, 90, 170, 802 |
Kesimpulan pembelajaran: Radix Sort tidak membandingkan dua angka secara langsung seperti Bubble Sort. Algoritma ini mengelompokkan angka berdasarkan digit tertentu, kemudian menggabungkan kelompok secara berurutan. Urutan dari tahap sebelumnya harus tetap dipertahankan di dalam kelompok yang sama agar hasil akhirnya benar.
