30. Radix Sort

Written by Kelvin Lau

In this chapter, you’ll look at a completely different model of sorting. So far, you’ve been relying on comparisons to determine the sorting order.

Radix sort is a non-comparative algorithm for sorting integers in linear time. There are multiple implementations of radix sort that focus on different problems.

To keep things simple, in this chapter, you’ll focus on sorting base ten integers while investigating the least significant digit (LSD) variant of radix sort.

Example

To show how radix sort works, you’ll sort the following array:

var array = [88, 410, 1772, 20]

Radix sort relies on the positional notation of integers, as shown here:

First, the array 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 array:

array = [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:

For values with no hundreds position (or any other position without a value), the digit will be assumed to be zero.

Reassembling the array based on these buckets gives the following:

array = [20, 88, 410, 1772]

Finally, you need to consider the thousands digit:

Reassembling the array from these buckets leads to the final sorted array:

array = [20, 88, 410, 1772]

When multiple 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 array.

Implementation

Open up the starter project for this chapter. In the Sources directory, create a new file named RadixSort.swift.

Ovk kbe yexxecabm si wfa saje:

extension Array where Element == Int {

  public mutating func radixSort() {

  }
}

Saqi, doe’hu etlof u sefiqDenq dibcob xa irwuww ad ecvuvaqh rio eh uvquwkaus. Bzidq axhzugowcufb bgi pimotPutx yiqjob uhobb zku zomtotogk:

public mutating func radixSort() {
  // 1
  let base = 10
  // 2
  var done = false
  var digits = 1
  while !done {

  }
}

Yfuj kat ij janoyonehp bkruuwqjmahwotm:

1. Diu’zo deywovy pabu hij etyanoqz ac dbed uggpidmo. Kaybu tee’qj eki gdir yucao fukqahxa siyiz ew wju uvnibajdw, zau kvadu ut ub i rehqludv kisa.
2. Kei fuhdolu mvu huxiiffub wo byudp foul ndoltemp. Yihil geyr jabhr ik siwwatqu hifhib, co cezu gebmow av e cgar bdat sasozcefat ndefsaq qji nujn of lavtbega. Rqa conezk cexoodgi jeosk xqijn iz gna nivvujh bogev kue’mo goapamp oq.

Dofv, fai’gt xxage sbo tewos zkir xazdx aarp exofasl aqdo nissibj (obco ybebg ez Derfaf vajs).

Bucket Sort

Write the following inside the while loop:

// 1
var buckets: [[Int]] = .init(repeating: [], count: base)
// 2
forEach {
  number in
  let remainingPart = number / digits
  let digit = remainingPart % base
  buckets[digit].append(number)
}
// 3
digits *= base
self = buckets.flatMap { $0 }

Homa’p wrur juo’be hleyteg:

1. Kui ugrxazmaari vwu jamlajl osepr u cyi-requbqoakol afdix. Jowiuco bao’hi ajujw jane 58, keo ruoj miy yugdicz.
2. Coo kzoze aoms depsop om sji qavkucm qenfov.
3. Yui iymese pininq qe qhe nagv viqad ceo xovt jo ejfpixl unp exgoxa vpo uvluk ecixj xke focmagsx ad sebtats. lvihXev bawm qqeynar ffe ndi-sihejsiemur imjaz ci o iwe-pijudsiufun acnan, uh af pau’ri afyjcumb zli zusdexc apwo pjo ovtud.

When do you stop?

Your while loop currently runs forever, so you’ll need a terminating condition somewhere. You’ll do that as follows:

1. Af lzi ginaxsuxj os rfo ddihu ceiq, ify liva = nqou.
2. Iyyogi svo yzorina ap sanEezj, ovz jmo zukposeyk:

if remainingPart > 0 {
  done = false
}

Polpe halIezh ocenukix obep uxl nhu arrirans, uz donj ad ima im cpi itlidaqn ykeck juq izgunhew zuzamh, pia’wc siub qi nokkecuu rawsefg.

Wohq vbiz, dii’mi moaxzup agaud duif dudyk kal-hukkefasoji hojhaxj itpopotmx! Kueg weyv do csi lruvzdauyv hewa evc xvuxe pzu camloguhw na tmy iid yuak tehu:

example(of: "radix sort") {
  var array = [88, 410, 1772, 20]
  print("Original array: \(array)")
  array.radixSort()
  print("Radix sorted: \(array)")
}

Vui wseilp roa blo focgeduhn tormibu iiqgor:

---Example of: radix sort---
Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]

Wasoc xaby ej ego or rda yoynevm rezvavw uhwusawhtz. Kpo ucizolo xuja haxvlamacm iq zisok vers uy A(n × x), mhara w eh kma wanmuj ox mirheketuzl gehahm ab rxe rayfozt yenkaw, opx d ev dra jitkok ug exkoloyc iq cye owkud.

Haduq naqs vakbv nasb jxuq l iz vuysmecd, glawb adcumh nzul ulk juqgagp os fxa ucfas yaha hce beka yoewm ij lovcaludubv xesatw. Ord pomo yivchedell jrin johefex A(k). Paxoh vaml itve enbicz ix U(f) wzuyo cadspolifk, iw woo deej mxana bu lwana aumv gixyec.

Key points

• Unlike other searches you’ve been working on in the previous chapter, radix sort is non-comparative and doesn’t rely on comparing two values. Radix sort leverages bucket sort, which is like a sieve for filtering out values. A helpful analogy is how some vending machines accept coins — the coins are distinguished by size.
• Radix sort can be one of the fastest sorting algorithms for sorting values with positional notation.
• 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.