• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Radix Sort

← Previous Next →

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing digits one by one, starting from the least significant digit to the most significant digit.

It uses a stable sort like counting sort as a subroutine.

🔹 How Radix Sort Works

  1. Start from the rightmost digit (least significant digit)

  2. Sort the numbers based on that digit using counting sort

  3. Move to the next left digit and repeat

  4. Continue until all digits are processed

🔹 Radix Sort in Python

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # Count occurrences based on digit
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # Cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build output array
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # Copy output to original array
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10
Example
numbers = [170, 45, 75, 90, 802, 24, 2, 66]

radix_sort(numbers)
print("Sorted array:", numbers)

✅ Output:

Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

🔹 Time and Space Complexity

Case Time
Best Case O(nk)
Average O(nk)
Worst Case O(nk)
Space O(n + k)

Where:

  • n is the number of elements

  • k is the number of digits in the largest number

🔹 Use Cases of Radix Sort

  • Sorting large sets of non-negative integers

  • Efficient for fixed-length numbers like phone numbers, PIN codes, etc.

🔹 When to Use

✅ Use Radix Sort when:

  • You are sorting integers

  • The number of digits (k) is small

  • Comparison-based sorts like Quick/Merge are not optimal

Practice Questions

Q1. Write a Python program to sort the list [34, 2, 122, 98, 1] using radix sort.

Q2. Write a Python program to modify radix sort to print the array after each digit pass.

Q3. Write a Python program to generate a random list of 20 integers and sort it using radix sort.

Q4. Write a Python program to count and display the total number of digit passes required in radix sort.

Q5. Write a Python program to accept a list of integers from user input and sort it using radix sort.

Q6. Write a Python program to test radix sort on numbers up to 100000 and display the sorted output.

Q7. Write a Python program to add a check for an empty list before performing radix sort.

Q8. Write a Python program to modify radix sort to work using base-16 (hexadecimal digits).

Q9. Write a Python program to compare the output of radix sort with the built-in sorted() function.

Q10. Write a Python program to implement radix sort by treating numbers as strings of digits.

← Previous Next →

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top