CodeBlanks Logo Icon CodeBlanks
Login Register

Digit pass

Sort by each digit, starting from the least significant.

Digit pass

At each digit pass, we sort all elements by that digit. This is done with counting sort.

Since a digit ranges from 0 to 9, the range is k=10; counting sort is very fast. Each pass is O(n + 10) = O(n).

For d digits we do d passes; total O(dn).

Stable sub-sort

Radix sort works only if the sub-sorter is stable. If not, the order from previous passes is broken and the result is wrong.

Counting sort is stable by placing back to front. This makes it the natural choice for radix sort.

If the sub-sorter is not stable, radix sort cannot be used; each pass would destroy the previous sort.

Practice Counting sort by digit

Write counting_by_digit(arr, d). Stably sort the array by digit d. Print [170, 90, 45, 75] with print(counting_by_digit([170, 45, 75, 90], 0)).

Starter code

solution.py
def counting_by_digit(arr, d):
    # Sort by digit d

Sample solution

solution.py
def get_digit(n, d):
    return n // (10 ** d) % 10
def counting_by_digit(arr, d):
    # Sort by digit d
    count = [0] * 10
    for x in arr:
        count[get_digit(x, d)] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        digit = get_digit(arr[i], d)
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    return output
print(counting_by_digit([170, 45, 75, 90], 0))

Expected output

[170, 90, 45, 75]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Digit range

Question 
k = ____  # range 0-9
Answer 
k = 10  # range 0-9

Explanation: 10 is right.

2 Digit pass: match the terms

Term Meaning
Digit 0-9
Sub-sorter Counting sort
Stable Required
Pass O(n)

3 Why does radix sort use counting sort?

  • Less memory
  • Easier
  • Stable and fast Correct answer
  • Random

Explanation: Stable and fast

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4