CodeBlanks Logo Icon CodeBlanks
Login Register

Summary - Radix sort

Implement radix sort and print the result.

Summary - Radix sort

Radix sort: digit by digit, LSD first, with stable counting sort. Non-comparison, O(dn).

d is the digit count; for integers it is log k (k the largest value). Effective even for large numbers.

Negative numbers need an offset. Stability is required; otherwise the result is wrong.

Practice Summary: radix sort

Write radix_sort(arr). Print [1, 1, 2, 3, 4, 5, 6, 9] with print(radix_sort([3,1,4,1,5,9,2,6])).

Starter code

solution.py
def radix_sort(arr):
    # Sort digit by digit

Sample solution

solution.py
def get_digit(n, d):
    return n // (10 ** d) % 10
def counting_by_digit(arr, 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
def radix_sort(arr):
    # Sort digit by digit
    if not arr:
        return arr
    max_digits = len(str(max(arr)))
    for d in range(max_digits):
        arr = counting_by_digit(arr, d)
    return arr
print(radix_sort([3, 1, 4, 1, 5, 9, 2, 6]))

Expected output

[1, 1, 2, 3, 4, 5, 6, 9]

Questions and answers

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

1 Summary - Radix sort: match the terms

Term Meaning
Method LSD
Sub-sorter Counting sort
Cost O(dn)
Stable Required

2 Start

Question 
Least significant digit: d = ____
Answer 
Least significant digit: d = 0

Explanation: 0 is right.

3 Does radix sort compare elements?

  • No Correct answer
  • Only on small arrays
  • Only on large arrays
  • Yes

Explanation: No

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