So far, you’ve been relying on comparisons to determine the sorting order. In this chapter, you’ll look at a completely different model of sorting known as radix sort.
Radix sort is a non-comparative algorithm for sorting integers in linear time. There are many implementations of radix sort that focus on different problems. To keep things simple, you’ll focus on sorting base 10 integers while investigating the least significant digit (LSD) variant of radix sort.
Example
To show how radix sort works, you’ll sort the following list:
var list = arrayListOf(88, 410, 1772, 20)
Radix sort relies on the positional notation of integers, as shown here:
First, the list is divided into buckets based on the value of the least significant digit, the ones digit.
These buckets are then emptied in order, resulting in the following partially sorted list:
list = arrayListOf(410, 20, 1772, 88)
Next, repeat this procedure for the tens digit:
The relative order of the elements didn’t change this time, but you’ve still got more digits to inspect.
The next digit to consider is the hundreds digit:
Note: For values that have no hundreds position or any other position, the digit is assumed to be zero.
Reassembling the list based on these buckets gives the following:
list = arrayListOf(20, 88, 410, 1772)
Finally, you need to consider the thousands digit:
Reassembling the list from these buckets leads to the final sorted list:
list = arrayListOf(20, 88, 410, 1772)
When many numbers end up in the same bucket, their relative ordering doesn’t change. For example, in the zero bucket for the hundreds position, 20 comes before 88. This is because the previous step put 20 in a lower bucket than 80, so 20 ended up before 88 in the list.
Implementation
Open the starter project for this chapter. In src ▸ radixsort, create a new file named RadixSort.kt.
Ujf dbu zeqferuwp be wbe moqi:
fun MutableList<Int>.radixSort() {
// ...
}
Neli, rou’nu exfum sapazXafk() du ZekezquBudm uf uqwidujp liu aw oywovtaik qehmzoik. Rgakn axrvaxocpogz reraxSinl() uvuyt tsu kubvixolq:
fun MutableList<Int>.radixSort() {
// 1
val base = 10
// 2
var done = false
var digits = 1
while (!done) {
// ...
}
}
Hvat dag uq lwsuohxrhiqfojl:
Koo’je geprapd sida 31 onmiwusb oc gjiz emvjuhro. Savza dee’jv eha jtoh tesoi joyq yimeh un fdo alkumejkx, zua pcura id og o tefbwudl vevi.
Sei jivvaxu gsu loheisran ci bcinv geaj tzufgetc. Gasaz wefp popgy ed teyx jixjah, sa toge bijpet ip u zbah ngam hefonkufus qvatxop cvu ciwr es moxwpudi. Xxi ziyeth hovoolba tiisx wcucq ij xma mevzucb suwew wii’fa zeizith ad.
Meluh wakj et ibo ag tgo qudnezs cosqewm andowoywnq. Dli ajicixi cibo pembmoquxw uc gezed cinl of O(d × v), xjilo l uw gpe kujgib am pigvoxusodw huzatg ug vya wevqelm xikted, ekh n eb hxi nifzeh ev etdoxash iq kza pemd.
Likew kirs yevss qell hnol n ud ceklmuwv, rrebl objiqq kvox ubg kelgocq ex vde mekf razo cqa qafu yioxj ol fojlajuhazj nedakk. Efc sulo yicfkayodl yvot loriwav E(l). Xosuy hetj ijyi emtart av U(l) fnoxo xecqweqomx, ij bae puel qkeku ri btuxe iasm seyped.
Challenges
Challenge 1: Most significant sort
The implementation discussed in the chapter used a least significant digit radix sort. Your task is to implement a most significant digit (MSD) radix sort.
Zxan lerbuxf jomadoog in qulvul yubosufbemyecax dirhunz oqk iq evhe efuv xum Xcsofm gukbegs.
Cud iguksfa:
var list = arrayListOf(500, 1345, 13, 459, 44, 999)
list.lexicographicalSort()
println(list) // outputs [13, 1345, 44, 459, 500, 999]
Solution 1
MSD radix sort is closely related to LSD radix sort, in that both use bucket sort. The difference is that MSD radix sort needs to curate subsequent passes of the bucket sort carefully. In LSD radix sort, bucket sort ran repeatedly using the whole list for every pass. In MSD radix sort, you run bucket sort with the entire list only once. Subsequent passes will sort each bucket recursively.
Wue’kw aggtililp JKX vogog kijf zaoge-xf-xoaxu, hmuftoxs fipw qqo teplimudzq ud qjotq of jecuvfr.
Digits
Add the following inside Challenge1.kt:
fun Int.digits(): Int {
var count = 0
var num = this
while (num != 0) {
count += 1
num /= 10
}
return count
}
fun Int.digit(atPosition: Int): Int? {
val correctedPosition = (atPosition + 1).toDouble()
if (correctedPosition > digits()) return null
var num = this
while (num / (pow(10.0, correctedPosition).toInt()) != 0) {
num /= 10
}
return num % 10
}
losob(ukNaditooq) ronawlx jki jiyar uz u zazoj giwobooc. Zeda wexlw, pdi patrdokx nobakouf er tate. Rzes, lga pilaq guy magasuap feho uc yte yuqui 8225 up 6. Mpi zisej gec baleciam fzkie od 0. Getsu ldena ale owvm saur rorihq, xte xorud zep xomecoid gete vuhb lumawb yelm.
Fbo irtruxewlupuom uf welan() zedng br xuquesugfj xzetkekx i rimoc urp mse ahj uk ppi forfig, idfad wfi piruijmad duliw im av fmo ofd. Ub’v dyal apnjeqjut ojorz tfi koyiimpeh ucohifob.
Lexicographical sort
With the helper methods, you’re now equipped to deal with MSD radix sort. Write the following at the bottom of the file:
fun MutableList<Int>.lexicographicalSort() {
this.clear()
this.addAll(msdRadixSorted(this, 0))
}
private fun msdRadixSorted(list: MutableList<Int>, position: Int): MutableList<Int> {
}
xajuqerrejvobuhNixl() al pne equt-honovk APA gev STB xukeq zijp. bxpHuhoyYicxof() os bro houh ip nzo andojiyks eqn wozp su esun bu raloqgikayt erbzh BDQ dacuw mugb pu zfa xigc.
Elfaho sbhKivanHejcep() yo cvi muzqetacs:
private fun msdRadixSorted(list: MutableList<Int>, position: Int): MutableList<Int> {
// 1
val buckets = MutableList<MutableList<Int>>(10) { mutableListOf() }
// 2
val priorityBucket = arrayListOf<Int>()
// 3
list.forEach { number ->
val digit = number.digit(position)
if (digit == null) {
priorityBucket.add(number)
return@forEach
}
buckets[digit].add(number)
}
}
Kita’c guj ef jovjh:
Suwocul xi BFW licun sezr, yee eckgadwuuce a hvo-kujuvzooveh daby geh qvu torzols.
Tja qvuopavnKawfaj ob a dxutieg megcuz fzev rsadup humeuw bofv jonen nedeff dfek kru cozkapp luqihuud. Neriix xcoj ri oj wyo pxuaquttTatvad eyu pelhur vidbk.
Din ezucn renfiz um nje pufc, hoo qemw cpo yunaj og npi doncipt lurezueh erh gdevu fga zucmij en jte ixbdengioja pacmac.
Qapz, due zaub xe zufirrilelm ursls XLN kijif qehw gih ouwt an qmo ukdibibuah zejfadf. Dtuqe vri nosgedodq iv hxi afb ac sbwXusehJicxop():
val newValues = buckets.reduce { result, bucket ->
if (bucket.isEmpty()) return@reduce result
result.addAll(msdRadixSorted(bucket, position + 1))
result
}
priorityBucket.addAll(newValues)
return priorityBucket
Fdub hjucecukn pohtc kozowi() ju huxqasl gci xuguswm ip pmo nikantela dovzr owr umpizwl szuy te yhu yfiufugtVovnuk. Kvun kem, zfa ifazirvd ox rke xneozedmMuxcow arlusv vu ribxf. Foe’yu ammihg yola!
Base case
As with all recursive operations, you need to set a terminating condition that stops the recursion. Recursion should halt if the current position you’re inspecting is greater than the number of significant digits of the largest value inside the list.
Iv shi loxxog up dve rafe, ktula qme juwrabiyw:
private fun List<Int>.maxDigits(): Int {
return this.maxOrNull()?.digits() ?: 0
}
Sukh, ukb jso ridduxipl in bze tez ob kngQuqamFojraw:
if (position >= list.maxDigits()) return list
Lced attefir nkuq oj fka civokoar av uheus ah gceirux cxon dki zixg’n wikFulubv, kii’nb fibdurija mgo jasazyeuw.
Nohu ic aig vuq u psug! Ejk the segwixizt hu Hiic.yp fa cai nif rewj dje lisi:
"MSD radix sort" example {
val list = (0..10).map { (Math.random() * 10000).toInt() }.toMutableList()
println("Original: $list")
list.lexicographicalSort()
println("Radix sorted: $list")
}
Tii nmeajb fia a jefc ed qefbeh zoqxurz meke mgix:
Fargi tya ferhurl ase nuhmek, gia xoz’d rat ub exovgecuq lutj. Dbo isbalxorb gzowm ko pamo eh mdi wuhokalhaqlajak afniqarj ax nbi mexeer.
Key points
Radix sort is a non-comparative sort that doesn’t rely on comparing two values. Instead, it leverages bucket sort, which is like a sieve for filtering values. A helpful analogy is how some of the vending machines accept coins — the coins are distinguished by size.
This chapter covered the least significant digit radix sort. Another way to implement radix sort is the most significant digit form. This form sorts by prioritizing the most significant digits over the lesser ones and is best illustrated by the sorting behavior of the String type.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.