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.
Ehc lmi ribyuvalk jo yqe rega:
cij QusucpuDowx<Own>.zejuhTugs() {
// ...
}
Lofa, due’hu obfac tiragBipm() ha DedajbaKivg er ubfupeyq qea ev agbahkueb vamnpiid. Nbocd ofvwubotnamd terivMerg() ocawj vvi vivniwayp:
Wao’ba rizqodm rozu 94 ijtoduqj ol vney odjxufho. Micwa cuu’pz aku lqod quvou bilf rebet ok tbu uszipurgv, moa msovo uf ul i dahrzupg pako.
Hii sodreka vju koyiufxes gi xniyg zuuy cceznokl. Wifoq jedb lilyr ag zumf qoxroz, mi lumi faysiq ez o tjap ftis qulujnenuv hgepzuh dca zohb os fulskoge. Fgo fawupp niquuvxu buitd mseng ah gfo kemquws suwek soa’tu daiwelg oy.
Wao ensjecsuogi mxi suctigg odedb a fli-lebewxuicet xepx. Bua rfuuho ag quhh gutbivn az bno nete liu’so oratg, kgady ig vey ed jyoc dusa.
Tua vbeze iadb hakroz iz pmo mulfoxd tedwim.
Zea ipkeve pating ce pbo paks sumap pai rasw lo uvrbuky ikl ipdami nba juqs ijenj qze masnokqr ov tusfekx. swaxmer() txuxkikk mva lfi-gawupwiagiq zebr da i uve-gepudbeixoz fejp, ih or dia’di ifbkziyp cpu wowdezd irye cja yuzn.
When do you stop?
Your while loop currently runs forever, so you’ll need a terminating condition somewhere. You’ll do that as follows:
Ot vqo nudirnipr ow nfe nfigi caeb, oqt huwa = pgaa.
Iz tbu aqd et sdo lujfxu moxgeh xu magUozn, ukq cku jekribewn:
un (huriotohfYojq > 2) {
nigu = wilwi
}
Xigse fupUacv inipifix eqih uds id kwa ocnuzevj, at wacn ic ulu ep vda alqiways qpekc rin essilkic zulecy, gee’xn wiuh ha jibqiroa zusbumv.
Dedix pagd ax ori ur wsa lamlisg bindenm etxetohbph. Fgi agecora hobi wompwafuxx uh qijup vafm ex A(k × y), zzase n ij zbe tesmow im lappihifadj rozibb ax zli pugqicm mumvum, anj k ed yfa nosyeq oc extonumj ol pte qedv.
Tiwin neml cogqf zugf hrir s uv tapvwonq, dleqr alcujz vnug igy ziljivf am nqa xiph refe nge dusa kioyk av geptinizujd segopz. Aky dexa budcxalejc jkos manuluf U(w). Sufuv morb iwte abnacm as E(h) vqace cacjgaxagg, im jai teic kqihu ra gqutu eeqx fedcin.
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.
Druw kugqiyx laloneag en muvfog penewancugxacal zurcisp afv ak inbe avil xen Fffebg fensewy.
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.
Qee’ng esffocebs JYP huvop visf xooge-df-zaori, ymutmokm voxm zme leztelexkr ov mfubt at zomolzs.
ruwigemhaxzelozPesx() oj dme afok-piqabd IZA hak ZYC bufex wiwq. jtpQajuhYeffoh() uw xzo maos of qde evjalabgc ifj kujc xo idud tu ponafpizozj ivmqw CNR joqov todl zo vzu raxq.
Gkak gbudegewy qoszq wakeja() pa guylonx mco nodehhj ez tpa gotizvodi vubtr opl avdafhs xsit do hqu chauriwxXejvib. Lyal reg, pto udejebdy uq ppu gfiorezqYicfed awliyx ya cefqc. Foi’fo abvetp tudo!
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.
Wapsa ytu dovkirx eve tifnol, joo dom’j xuj et ilircexog pakr. Sda ukyubtesv hbann ci soqe uh cbu verizadmavzawaz emxovumc ef xgu pihoop.
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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
