Mengapa Radix Sort ?

Dalam radix sort, pertama-tama kita urutkan berdasarkan digit paling tidak signifikan, lalu kita urutkan berdasarkan digit paling sedikit kedua dan seterusnya dan berakhir dengan daftar yang diurutkan.

Sekarang jika kita memiliki daftar nomor kita perlu bit untuk membedakan antara angka-angka itu. Jadi jumlah lintasan sortir radix yang kita buat adalah . Setiap pass membutuhkan waktu dan karenanya waktu berjalan dari jenis radix adalahlog n log n O ( n ) O ( n log n $n$$\log n$$\log n$$O(n)$$O(n \log n)$

Tetapi diketahui bahwa itu adalah algoritma waktu linier. Mengapa?

jika kita memiliki daftar nomor kita perlu bitlog $n$$\log n$

Tidak: jika kita memiliki daftar angka antara dan , kita perlu bit. Tidak ada hubungan antara dan secara umum.2 k - 1 k k log $0$$2^k - 1$$k$$k$$\log n$

Jika angkanya berbeda, maka , dan radix sort pada angka yang berbeda karena itu memiliki kompleksitas waktu . Secara umum, kompleksitas sortir radix adalah mana adalah jumlah elemen untuk disortir dan adalah jumlah bit dalam setiap elemen.Ω ( n log n ) Θ ( $\log n \ge k$$\Omega(n \log n)$n $\Theta(n \, k)$$n$$k$

Mengatakan bahwa kompleksitas jenis radix adalah berarti mengambil ukuran bit yang tetap untuk angka-angkanya. Ini menyiratkan bahwa untuk cukup besar , akan ada banyak nilai duplikat.$O(n)$$n$

Ada teorema umum bahwa metode pengurutan larik atau daftar yang berfungsi dengan membandingkan dua elemen sekaligus tidak dapat berjalan lebih cepat dari dalam kasus terburuk. Urutan Radix tidak bekerja dengan membandingkan elemen, tetapi metode bukti yang sama berfungsi. Sortir radix adalah proses pengambilan keputusan untuk menentukan permutasi yang diterapkan pada array; adapermutasi array, dan radix sort mengambil keputusan biner, yaitu memutuskan apakah akan menukar dua elemen atau tidak pada setiap tahap. Setelah keputusan biner, radix sort dapat memutuskan antara permutasi. Untuk mencapaikemungkinan permutasi, perlu bahwa .n ! m 2 m n ! m ≥ log ( n ! ) = Θ ( n log n $\Theta(n \log n)$$n!$$m$$2^m$$n!$$m \ge \log (n!) = \Theta(n \log n)$

Asumsi dalam bukti bahwa saya tidak menulis di atas adalah bahwa algoritma harus bekerja dalam kasus ketika elemen berbeda. Jika diketahui apriori bahwa unsur-unsurnya tidak semuanya berbeda, maka jumlah permutasi potensial kurang dari penuh. Saat mengurutkan angka -bit, hanya mungkin untuk memiliki elemen yang berbeda ketika ; dalam hal ini, kompleksitas jenis radix memang . Untuk nilai lebih besar , harus ada tabrakan, yang menjelaskan bagaimana radix sort dapat memiliki kompleksitas yang kurang dari ketika .k n n ≤ 2 k Ω ( n log n ) n Θ ( n log n ) n > 2 $n!$$k$$n$$n \le 2^k$$\Omega(n \log n)$$n$$\Theta(n \log n)$$n \gt 2^k$

Berhati-hatilah dengan analisis Anda: apa yang Anda asumsikan untuk membuat penyortiran berjalan dalam waktu ? Ini karena setiap digit Anda berada dalam kisaran dari hingga , yang berarti digit Anda dapat mengambil nilai mungkin. Anda memerlukan algoritme penyortiran yang stabil, jadi Anda dapat misalnya memilih penghitungan sortir. Menghitung sorting berjalan dalam waktu . Jika k = O ( n ) , penghitungan sort berjalan dalam waktu linier.$O(n)$$0$$k-1$$k$$\Theta(n+k)$$k=O(n)$

Setiap string atau angka Anda memiliki digit. Seperti yang Anda katakan, Anda membuat d melewati mereka. Karenanya, jenis radix jelas berjalan dalam waktu Θ ( d ( n + k ) ) . Tetapi jika kita menganggap sebagai konstan dan , kita melihat bahwa radix sort berjalan dalam waktu linier.$d$$d$$\Theta(d(n+k))$$d$$k=O(n)$

Saya pikir anggapan salah. Anda dapat melakukan radix sort dengan angka di, misalnya, hex. Jadi, pada setiap langkah Anda membagi array angka menjadi 16 ember.$k = \log_2(n)$$16$