Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

18. Radix Sort
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now

In this chapter, you’ll look at a completely different sorting model. So far, you’ve been relying on comparisons to determine the sorting order. Radix sort is a non-comparative algorithm for sorting integers. The word radix means base, as in the base of a number system. For example, decimal is base 10, and binary is base 2. You can use any base with a radix sort, but to keep things simple, this chapter will focus on sorting base-10 integers.

Radix sort relies on the position of digits within a number. For example, there are four digits in the number 1772. The least significant digit is 2 since this is in the ones place. The most significant digit is 1 since this is the thousands-place value, greater than any other place value in this particular number. The following diagram shows the place values of a four-digit number:

1 thousands 7 hundreds 7 tens 2 ones

There are multiple implementations of radix sort that focus on different problems. One type sorts by the least significant digit (LSD) and another by the most significant digit (MSD).

You’ll learn about both LSD- and MSD-radix sorting in this chapter.

Sorting by Least Significant Digit

Before you implement a radix sort in code, go through the following example to get an intuitive idea of how the sort works.

Example

An LSD-radix sort starts by looking at the least significant digits in a list of numbers. For example, the image below shows the numbers 88, 410, 1772 and 20 vertically aligned with a box drawn around the ones place:

2 5 0 3 3 3 8 2 5 2 6

Round One

You start by making ten buckets to sort the numbers into. You can think of this like sorting fruit. You put the apples in the apple bucket, the oranges in the oranges bucket, and the pears in the pear bucket.

6 8 2 1 9 5 6 9 6 6

4 06 447 3579 29 0 3 6 2 9 6 2 2 1

7 8 8 5 0 5 4 8 3 0 6

Round Two

For round two, you look at the next significant digit, the tens-place value:

0 8 3 4 1 0 6 1 3 3 1

8 6 9 3 9 8 1 6 5 0

0 28 14 2 0 9 1 0 4 5 4 4 401 2878

8 5 3 2 6 6 0 1 6 5 7

Round Three

This time look at the hundreds place. Since 20 and 88 are less than 100, you can use 0s for the hundreds place:

0 2 4 0 6 5 8 8 4 4 7 3 8

8 9 7 9 1 7 4 6 2 2 104 66 45 3246

8 0 5 1 5 1 5 0 5 9 9 4 4

Round Four

In this radix sort algorithm, there’s one round for every significant digit. Since 1722 has four digits, this fourth round will ensure that the thousands-place value is also sorted. Pad any numbers less than one thousand with zeros in front:

1 9 3 7 2 4 8 3 6 4 1 8 7 2 6 3

5 0 4 7 8 6 9 3 2 1 1970 64 32 175

0 3 0 1 1 3 3 3 5 0 9

Implementation

To implement LSD-radix sort, you’ll use a while loop for each round as you step through the place values. Your ten buckets will be ten integer lists.

extension RadixSort on List<int> {
  void radixSort() {
    const base = 10;
    var done = false;
    // 1
    var place = 1;
    while (!done) {
      done = true;
      // 2
      final buckets = List.generate(base, (_) => <int>[]);
      forEach((number) {
        // 3
        final remainingPart = number ~/ place;
        final digit = remainingPart % base;
        // 4
        buckets[digit].add(number);
        if (remainingPart ~/ base > 0) {
          done = false;
        }
      });
      // 5
      place *= base;
      clear();
      addAll(buckets.expand((element) => element));
    }
  }
}

Testing it Out

Head back to bin/start.dart and replace the contents of the file with the following code:

import 'package:starter/radix_sort.dart';

void main() {
  final list = [88, 410, 1772, 20];
  print("Original list: $list");
  list.radixSort();
  print("Radix sorted: $list");
}

Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]

Sorting by Most Significant Digit

The MSD-radix sort uses the most significant digit to sort a list. You might think that’s a little strange when you look at a list of numbers sorted in this way:

8 4 8 6 9 7 0 1 5 0 9 4 6 2 2 0 1

j i o g k q i t o g u a h c o i a a t

Example

Start with the following unsorted list:

[46, 500, 459, 1345, 13, 999]

Beginning the Sort

As with LSD-radix sort, you first create ten buckets. However, this time you add the numbers to the buckets according to their most significant digit, that is, the first digit on their left:

0 4 7 0 4 2 9 5 5 2 28 6406 386 184 307 25

Recursively Sorting 1345 and 13

In the previous image, the ones bucket and the fours bucket both have more than one element. Start with the ones bucket, which contains 1345 and 13. Take those numbers and perform another bucket sort, this time on the second most significant digit:

5 2 0 1 5 1 8 9 3 1 29 8230

5 1 5 2 1 5 2 7 2 3 txuabafh 23 2528

Recursively Sorting 46 and 459

Now you need to do the same thing with 46 and 459. Perform a bucket sort on the second digit. That gives the following:

2 9 7 6 7 4 5 9 3 6 997 40

Combining All the Buckets

There were no other buckets with more than one number from the original round, so you’re finished. Combine all of the buckets and sorted sublists into the final sorted result of [13, 1345, 459, 46, 500, 999]:

4 4 8 1 3 1 2 1 7 1 9 5 5 9 9 4 4

Implementation

To start off, you’ll write a few helper methods.

Getting the Number of Digits

Open lib/radix_sort.dart again and add the following int extension to the file:

extension Digits on int {
  static const _base = 10;

  int digits() {
    var count = 0;
    var number = this;
    while (number != 0) {
      count += 1;
      number ~/= _base;
    }
    return count;
  }
}

print(13.digits());    // 2
print(999.digits());   // 3
print(1345.digits());  // 4

Finding the Digit at Some Position

Add the following import to lib/radix_sort.dart:

import 'dart:math';

int? digitAt(int position) {
  if (position >= digits()) {
    return null;
  }
  var number = this;
  while (number ~/ pow(_base, position + 1) != 0) {
    number ~/= _base;
  }
  return number % _base;
}

print(1345.digitAt(0)); // 1
print(1345.digitAt(1)); // 3
print(1345.digitAt(2)); // 4
print(1345.digitAt(3)); // 5
print(1345.digitAt(4)); // null
print(1345.digitAt(5)); // null

Finding the Max Digits in the List

Go back to lib/radix_sort.dart and add a new List extension with the following method:

extension MsdRadixSort on List<int> {
  int maxDigits() {
    if (isEmpty) return 0;
    return reduce(max).digits();
  }

  // more to come
}

final list = [46, 500, 459, 1345, 13, 999];
print(list.maxDigits()); // 4

Adding the Recursive Sort Methods

Go back to the MsdRadixSort extension on List in lib/radix_sort.dart. You’re going to add two more methods to this extension. One will be public and the other a private recursive helper method.

void lexicographicalSort() {
  final sorted = _msdRadixSorted(this, 0);
  clear();
  addAll(sorted);
}

// more to come

// 1
List<int> _msdRadixSorted(List<int> list, int position) {
  // 2
  if (list.length < 2 || position >= list.maxDigits()) {
    return list;
  }
  // 3
  final buckets = List.generate(10, (_) => <int>[]);
  // 4
  var priorityBucket = <int>[];

  // more to come
}

for (var number in list) {
  final digit = number.digitAt(position);
  if (digit == null) {
    priorityBucket.add(number);
    continue;
  }
  buckets[digit].add(number);
}

// more to come

// 1
final bucketOrder = buckets.reduce((result, bucket) {
  if (bucket.isEmpty) return result;
  // 2
  final sorted = _msdRadixSorted(bucket, position + 1);
  return result..addAll(sorted);
});
// 3
return priorityBucket..addAll(bucketOrder);

Testing it Out

Open bin/starter.dart again and run the following code in main:

final list = [46, 500, 459, 1345, 13, 999];
list.lexicographicalSort();
print(list);

[13, 1345, 459, 46, 500, 999]

Challenges

The challenges below will help strengthen your understanding of radix sorts. You can find the answers in the Challenge Solutions section or in the supplementary materials that accompany this book.

Challenge 1: What Are in the Buckets?

Add a print statement to your radixSort implementation to tell you what’s in the buckets after each round of sorting.

var list = [46, 500, 459, 1345, 13, 999];

Challenge 2: Unique Characters

Write a function that returns the total number of unique characters used in a list of words.

final words = ['done', 'ad', 'eel', 'zoo', 'adept', 'do'];

Challenge 3: Optimization

Given the following list:

[88, 410, 1772, 20, 123456789876543210]

Key Points

  • Unlike the other sorting algorithms you’ve implemented in previous chapters, radix sort doesn’t rely on comparing two values. It leverages bucket sort, which is a way to sort numbers by their digits.
  • The word radix means base, as in base-10 or base-2 numbering systems. The internal bucket sort will use the same number of buckets as the base.
  • Radix sort can be one of the fastest sorting algorithms for sorting values with positional notation.
  • A least-significant-digit (LSD) radix sort begins sorting with the rightmost digit.
  • Another way to implement radix sort is the most-significant-digit (MSD) form. This form sorts by prioritizing the leftmost digits over the lesser ones to the right. It’s best illustrated by the sorting behavior of the String type.
17. Merge Sort
19. Heapsort
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

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 Personal Plan.

Unlock now