CodeBlanks Logo Icon CodeBlanks
Login Register

Radix idea

Sort numbers digit by digit.

Radix idea

Radix sort sorts numbers digit by digit. First by the units digit, then tens, then hundreds... Each pass uses a stable sub-sorter (usually counting sort).

We start from the least significant digit (LSD) and move toward the most significant. Stability ensures the order from earlier passes is preserved.

With d digits and base k, the cost is O(d(n + k)). Effective even for large numbers.

LSD and MSD

LSD radix sort starts from the least significant digit. It re-sorts the whole array at each digit. Because it is stable, the final order is correct.

MSD radix sort starts from the most significant digit and splits each group recursively. It is more complex but may do fewer passes in some cases.

LSD is easier to implement and usually preferred.

Practice Get digit

Write get_digit(n, d). Return digit d (0=units) of n. Print 3 with print(get_digit(738, 1)).

Starter code

solution.py
def get_digit(n, d):
    # Return digit d

Sample solution

solution.py
def get_digit(n, d):
    # Return digit d
    return n // (10 ** d) % 10
print(get_digit(738, 1))

Expected output

3

Questions and answers

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

1 Which sub-sorter does radix sort use?

  • Quick sort
  • Stable counting sort Correct answer
  • Heap sort
  • Selection sort

Explanation: Stable counting sort

2 Digit count

Question 
d = len(str(____))
Answer 
d = len(str(max(arr)))

Explanation: max(arr) is right.

3 Radix idea: match the terms

Term Meaning
LSD Units first
MSD Hundreds first
Sub-sorter Counting sort
Cost O(d(n+k))

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