• Hajipur, Bihar, 844101

☰
❮
❯

Python

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

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.

Python Radix Sort Quiz

Q1: What is the key technique used in radix sort?

A. Comparison
B. Divide and conquer
C. Digit-by-digit sorting
D. Swapping

Q2: Radix sort is based on:

A. Bubble sort
B. Counting sort
C. Merge sort
D. Heap sort

Q3: Which digits does Radix Sort start sorting with?

A. Leftmost
B. Rightmost
C. Middle
D. Random

Q4: Time complexity of radix sort is:

A. O(n log n)
B. O(n²)
C. O(nk)
D. O(k²)

Q5: Radix sort is suitable for:

A. Strings only
B. Negative numbers
C. Floating points
D. Non-negative integers

Q6: What type of algorithm is Radix Sort?

A. Comparison-based
B. Non-comparison-based
C. Hybrid sort
D. Greedy sort

Q7: Which sorting algorithm is stable in radix sort?

A. Merge
B. Heap
C. Counting
D. Quick

Q8: How many passes does Radix Sort require for 3-digit numbers?

A. 1
B. 2
C. 3
D. Depends on input order

Q9: Radix Sort is better than Quick Sort when:

A. List is already sorted
B. Numbers are small and fixed-digit
C. Elements are all strings
D. Data has many duplicates

Q10: Can Radix Sort sort floating-point numbers directly?

A. Yes
B. No
C. Only if converted to strings
D. Only with a stable sort
← Previous Next →
Login
Go Back Top