Radix Sort
Terakhir diperbarui
Radix sort adalah algoritma pengurutan tanpa perbandingan untuk integer. Alih-alih membandingkan nilai, algoritma ini mengurutkan bilangan digit demi digit. Versi least-significant-digit (LSD) memproses digit satuan lebih dulu, lalu puluhan, lalu ratusan, dengan counting sort yang stabil pada setiap digit. Karena setiap putaran stabil, begitu digit paling signifikan selesai diproses, seluruh array sudah terurut. Tekan Putar di atas untuk melihat setiap putaran digit menyusun ulang batang-batangnya.
Radix sort berjalan dalam waktu O(d·(n + k)), dengan d adalah jumlah digit dan k adalah basisnya (di sini 10). Untuk integer dengan lebar tetap, ini pada dasarnya linear dan bisa mengalahkan pengurutan berbasis perbandingan O(n log n), tetapi hanya bekerja pada data yang bisa dipecah menjadi digit atau key.
Kompleksitas waktu dan ruang
| Kasus | Kompleksitas | Catatan |
|---|---|---|
| Waktu | O(d·(n + k)) | d digit, basis k (linear untuk d yang tetap) |
| Ruang | O(n + k) | Array output + hitungan digit |
| Stabil | Ya | Setiap putaran digit adalah counting sort yang stabil |
| Perbandingan? | Tidak | Mengurutkan berdasarkan digit, bukan dengan membandingkan nilai |
| Bekerja pada | Integer/key | Bukan objek umum yang bisa dibandingkan |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Cari nilai maksimum untuk mengetahui berapa digit yang perlu diproses. |
| 2 | Mulai dari digit paling tidak signifikan (posisi satuan). |
| 3 | Urutkan array secara stabil berdasarkan digit itu dengan counting sort. |
| 4 | Pindah ke digit berikutnya yang lebih signifikan. |
| 5 | Ulangi sampai semua posisi digit sudah diproses. |
Contoh penerapan
Mengurutkan [170, 45, 75, 90, 2, 24, 66]:
| Putaran | Array | Aksi |
|---|---|---|
| Mulai | [170, 45, 75, 90, 2, 24, 66] | Nilai maksimumnya 170, jadi dibutuhkan tiga putaran digit. |
| Satuan | [170, 90, 2, 24, 45, 75, 66] | Urutkan secara stabil berdasarkan digit satuan: 0, 0, 2, 4, 5, 5, 6. |
| Puluhan | [2, 24, 45, 66, 170, 75, 90] | Urutkan secara stabil berdasarkan digit puluhan: 0, 2, 4, 6, 7, 7, 9 (170 tetap mendahului 75). |
| Ratusan | [2, 24, 45, 66, 75, 90, 170] | Urutkan secara stabil berdasarkan digit ratusan; hanya 170 yang punya 1, jadi bilangan itu pindah ke akhir. Terurut. |
Kapan memakai radix sort
| Pakai saat | Hindari saat |
|---|---|
| Key-nya berupa integer atau string dengan panjang tetap yang bisa dipecah menjadi digit. | Kamu harus mengurutkan objek sembarang dengan comparator khusus. |
Key-nya punya jumlah digit d yang kecil dan terbatas, sehingga O(d·(n + k)) mengalahkan O(n log n). | Key-nya sangat panjang atau tidak terbatas, sehingga d besar dan setiap putaran mahal. |
Kamu butuh pengurutan stabil dan sanggup memakai ruang tambahan O(n + k). | Memori terbatas dan buffer O(n + k) tidak bisa diterima. |
Rentang nilai atau basis k cukup kecil dibandingkan n. | k sangat besar, sehingga setiap putaran counting sort mendominasi waktu berjalannya. |
Kode Radix Sort
Implementasi Radix Sort yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Radix Sort dalam Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))Kode Radix Sort dalam JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Kode Radix Sort dalam Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}Kode Radix Sort dalam C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Kode Radix Sort dalam C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}FAQ Radix Sort
Berapa kompleksitas waktu radix sort?
O(d·(n + k)), dengan d adalah jumlah digit dan k adalah basisnya. Untuk integer dengan lebar tetap, ini pada dasarnya O(n), yang bisa lebih cepat daripada pengurutan berbasis perbandingan. Ruang tambahan yang dipakai O(n + k).Apakah radix sort stabil?
Ya. LSD radix sort mengandalkan counting sort yang stabil pada setiap digit; stabilitas inilah yang membuat pendekatan digit demi digit menghasilkan urutan yang benar.
Kapan radix sort bisa dipakai?
Radix sort bekerja pada data yang bisa diuraikan menjadi digit atau key berukuran tetap, seperti integer atau string dengan panjang tetap. Radix sort bukan pengurutan umum berbasis perbandingan, jadi tidak bisa mengurutkan objek sembarang dengan comparator khusus.
Apa bedanya radix sort dengan counting sort?
k), sehingga bisa menangani rentang nilai besar yang tidak sanggup ditangani counting sort biasa.Mengapa LSD radix sort dimulai dari digit paling tidak signifikan?
Memulai dari digit paling tidak signifikan membuat setiap putaran yang stabil mempertahankan urutan yang sudah dibentuk oleh semua digit sebelumnya yang kurang signifikan. Saat digit paling signifikan diproses, nilai yang sama pada digit itu sudah terurut dengan benar oleh digit-digit yang lebih rendah, jadi array akhirnya terurut sepenuhnya. Mengurutkan mulai dari digit paling signifikan akan merusak hal ini dan butuh pendekatan rekursif yang berbeda (MSD radix sort).
Bisakah radix sort menangani bilangan negatif?
Tidak secara langsung, karena ekstraksi digit dasar mengasumsikan integer yang tidak negatif. Solusi yang umum adalah menggeser semua nilai dengan offset sebesar nilai minimum agar semuanya tidak negatif, atau mengurutkan bilangan negatif dan tidak negatif secara terpisah lalu menggabungkannya. Mengabaikan hal ini adalah bug yang sering terjadi saat memakai radix sort pada data nyata.
Sumber terkait
Visualisasi lainnya
