Introduction to Radix Sort

Estimated Time

1 hour

Radixsort Introduction

Introduction video

Prerequisites of the Experiment

This experiment requires you to have basic knowledge about :

And above all, a curiosity to learn and explore!

Overview of the Experiment

  • The aim of this experiment is to understand the Radix Sort algorithm, its time and space complexity, and how it compares against other sorting algorithms.
  • The experiment features a series of modules with video lectures, interactive demonstrations, simulations, hands-on practice exercises and quizzes for self analysis.

Learning Objectives of the Experiment

In this experiment, you will be able to do the following:


  • Given an unsorted array of numbers, generate a sorted array of numbers by applying Radix Sort
  • Understand RadixSort, the conditions under which it is preferred over other algorithms and the associated time and space complexity through interactive animations.
  • Compare Radix Sort with other sorting algorithms and realise it as a stable, non-comparison based sorting algorithm.

Experiment Modules & their Weightage

Module Weightage Expectation
Pre-Test 20% Solve All Questions
Radix sort 50% Understand and Practice the full algorithm
Post-test 30% Solve all Questions

Pre-Test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-Test

  • Pretest includes questions on Sorting, Time and Space Complexity, Logarithms
  • If you want to revise these topics before taking the quiz, go through the Recap module first.
  • Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Quick look at Sorting, Time and Space Complexity, Logarithms

What is Sorting?

Given a list of random numbers, sorting means ordering the numbers in either ascending or descending order. By default, we sort numbers in an ascending order.

Unsorted and Sorted arrays

sort

Time and Space Complexity

Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input.
Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
Recall that suppose our input is an array of N elements, and our algorithm iterates through the array once, time complexity will be O(N). If I run two embedded loops to traverse the array N times, time complexity will be O(N2).

Logarithm

sort

A Quiz with Multiple Choice Questions

Q1. Which of these best describes an array?

(A) A data structure that shows a hierarchical behavior

(B) Container of objects of similar types

(C) Container of objects of mixed types

(D) All of the mentioned

An array is a data structure, which can store a fixed-size collection of elements of the same data type.

Q2. What is the time complexity of insertion at any point on an array?

(A) O(N)

(B) O(N^2)

(C) O(NLogN)

(D) None of these

Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements

Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

(A) X will always be a better choice for small inputs

(B) X will always be a better choice for large inputs

(C) Y will always be a better choice for small inputs

(D) X will always be a better choice for all inputs

Performance could be similar for small inputs, but definitely better for larger inputs

Q4. int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is the time and space complexity for the above code?

(A) O(N * M) time, O(1) space

(B) O(N + M) time, O(N + M) space

(C) O(N + M) time, O(1) space

(D) O(N * M) time, O(N + M) space

The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.

The Radix Sort Algorithm

Estimated Time

10 minutes

Radix Concept and Algorithm

radixsort video

Learning Objectives of this Module :

In this module, we will :


  • Learn the radix sort algorithm
  • See a demonstration of how the algorithm works
  • Practice the algorithm
  • Solve an exercise!

Radix Sort Concept

Identifying the digits

digits

The Radixsort Concept

Radix sort is an integer sorting algorithm that sorts data with integer keys.
It works by grouping the keys according to individual digits that share the same significant position and value (place value), together into a container, which we usually call a bucket.
It then sorts e numbers in the order of placement in the buckets(least to highest).
How does this work? Lets take an example of this array : 34, 123, 233, 239, 287, 319
Radix sort uses the observation that in a sorted array of numbers, the numbers are :

  • Firstly, sorted according to the most significant digit.
    034, 123,233, 239, 287, 319
    The most significant digits(in bold) are in increasing order : 0,1,2,2,2,3
  • Among the ones with the same most significant digit(or higher place value digit), they are arranged in the order of their second most significant digit(or next higher place value) and so on.
    Among 233, 239, 287 (same hundred's digit : most significant digit),
    they are arranged in increasing order of the ten's digit (second most significant digit): 3,3,8
  • Continuing till the last digit, 233 and 239 are also arranged in the order of their unit's digit(same hundred's and ten's digit):3,9

This is the basic concept that radix sort uses along with a method to sort the numbers based on particular place value (using buckets as told earlier in this section).

Digit extraction

Have a look at the image above to understand what we mean by the "least significant digit" and the "most significant digit". To extract the digit at the ith position :

  • Divide the integer by 10(i-1) and take only the integral part.
  • Take the modulus of the resulting number with 10
  • Resulting number is your ith digit.

For example:
Say 3rdrd least significant digit of 26438, that is the the hundred's position.
First divide by 103-1 = 102 = 100.
26438 / 100 = 264.
Then take modulus with 10.
264 % 10 = 4
4 is the third least significant digit.

Radix Sort Algorithm

The Radixsort Algorithm

  • In radix sort, we first sort the elements based on last digit (least significant digit/ units digit).
  • Then the resultant array is again sorted by the second last digit (tens digit).
  • This process is continued for all the digits in the same fashion until we finish doing the same for the most significant digit.
  • The resultant array obtained is a sorted array!

Radix Sort steps

RS levels

Sorting using buckets

The sorting is done using containers(which hold numbers with same place/significant digit under consideration), as explained and shown using this example:
Suppose we are sorting: 291,913,315,287,369 according to the tens digit now(already sorted according to units)
We iterate over all elements and place them in their respective buckets:


bucket[0]-> empty
bucket[1]-> 913, 315
bucket[2]-> empty
bucket[3]-> empty
bucket[4]-> empty
bucket[5]-> empty
bucket[6]-> 369
bucket[7]-> empty
bucket[8]-> 287
bucket[9]-> 291

Now we remove all the elements from the buckets( in order from 0->9 ) and put them back in the array.
Within the same bucket, the element that came in earlier, goes out first( FIFO principle: First In First Out)
Array obtained as a result will be: 913, 315, 369, 287, 291.
Refer to this image below for a better understanding.The initial array is at the top in blue and the final array in green, below the buckets.

Sorting using buckets

Sorting using buckets

Radix Sort Video

Radix Sort animation

Demonstration for Radix Sort Algorithm

Demo : Radix Sort

Representation of the whole process

Practice for Radix Sort Algorithm

Practice : Radix Sort

Practice of the whole process

Exercise for Radix Sort Algorithm

Exercise : Radix Sort

Exercise of the whole process

Analysis of Radix Sort

Estimated Time

20 minutes

Analysis of Radixsort

Time complexity is explained

Learning Objectives of this Module

In this module, we will look into :
  • Time and Space Complexity : We will learn about the running time of the sorting process.
  • Stable sort and Comparison sort : We will learn about what stable and comparison sorts are. Then we will see how radix sort is a stable, non-comparison sort.
  • Applications : We will compare radix sort with other sorting algorithms and see in which situations radix sort is the optimal approach to take.

Time and Space Complexity of Radix Sort

Running Time of Radix Sort

The running time complexity of radix sort in O(nd) where :

  • n is the number of elements
  • d is the maximum number of digits in any element of the array

Each step of the algorithm (when we are putting the elements in buckets according to say the m'th digit) requires O(n) time as we iterate over all the elements of the array.

Now there will be d steps in order to sort the whole array.

Hence the time complexity becomes O(nd)

Explaining time complexity of Radix sort

Radix time complexity

Space Complexity of Radix Sort

Space Complexity for Radix sort is O(n+b) where :

  • n is the number of elements
  • b is the base of the number representation being used which is equal to the number of buckets required

A space of O(n) is required to store the elements and O(b) is for the buckets used while sorting. Hence complexity becomes O(n+b)

Stable sort and Comparison sort

What is a Comparison Sort Algorithm?

A Comparison Sort is a sorting algorithm where the final order is determined only by comparisons between the input elements.

In Radix Sort, the values of the elements are never compared. The elements are just placed into buckets according to the digit under consideration.

Hence, Radix Sort is not a comparison based sort.

What is a Stable Sort Algorithm?

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in the sorted output as they appear in the input unsorted array. For example, look at the picture below. The unsorted array has two elements with value 23. Note the order of both these elements in the stable and unstable sorted arrays.

Stable and Unstable sort



stable sort

Is Radix Sort stable?

Yes, radix sort is a stable sorting algorithm. Look at the picture below and keep an eye out for the ordering of 75 and 75*. Note how the original order of these elements is retained throughout the sorting process. The relative positioning of 75 and 75* does not change in the sorted output.

Stability of Radixsort

Stable radixsort

Comparison with other algorithms

Comparison of algorithms

comparison

Comparison with other sorting algorithms

Algorithm Time Features
Sort Average Best Worst Space Stability
Radix sort O(nk) O(nk) O(nk) O(n+b) Stable
Bubble sort O(n2) O(n2) O(n2) Constant Stable
Modified Bubble sort O(n2) O(n) O(n2) Constant Stable
Selection Sort O(n2) O(n2) O(n2) Constant Stable
Insertion Sort O(n2) O(n) O(n2) Constant Stable
Heap Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Constant Unstable
Merge Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Depends Stable
Quicksort O(n*log(n)) O(n*log(n)) O(n2) Constant Stable

When is Radix sort actually used?

As we have seen, radix sort seems to have better time complexity than other sorting algorithms. Pertinent question is, why is it not as popular as the other algorithms? Here's why:

  • Radix sort only applies to integers, fixed size strings, floating points and to "less than", "greater than" or "lexicographic order" comparisons whereas comparison sorts can accommodate different orders.
  • k can be greater than log N, and when this happens comparison sorts become faster.
  • Popularly used comparison based sorting algorithms like quick sort can be done in place whereas radix sort is less efficient in terms of space complexity.

Revision Quiz for Analysis

Q1. What is the complexity of Radix sort?

(A) Best case O(nk)

(B) Best case O(n2)

(C) Worst case O(n2)

(D) Average case O(nk)

(E) A and D

Best case is O(nk) and average case is also O(nk). Procedure remains the same and the algorithm iterates over all elements regardless.

Q2. Given N and b, what is k ?(N is the maximum value element in the array, b is the base of the number representation, k is the number of buckets you will need)

(A) k = ceil(logbN)

(B) k = floor(logbN)

(C) Depends

(D) Can't say

Take b to be the base of your representation. Then the number of digits in the largest number(k) is equal to taking the upper bound of logbN

Q3. What kind of sorting algorithm is radix sort?

(A) Comparison based, stable)

(B) Not comparison based, unstable

(C) Not comparison based, stable

(D) None of the above

Radix sort is not a comparison based algorithm and it is stable.

Post Test of the Experiment

Estimated Time

10 minutes

Instructions for Quiz

Post Test includes questions on concepts from the entire experiment. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Quiz Time!

Q1. Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these numbers in linear time?

(A) Not possible to sort in linear time

(B) Radix Sort

(C) Bucket Sort

(D) Quick Sort

Radix Sort can be used to sort such a case in linear time as explained in the analysis section.

Q2.If we use Radix Sort to sort n integers in the range (nk/2,nk, for some k>0 which is independent of n, the time taken would be?

(A)Theta(n)

(B)Theta(k.n)

(C) Theta(n.logn)

(D) Theta(n2)

Radix sort time complexity = O(wn), for n keys of word size = w
=> w = log(n^k)
O(wn) = O(k. logn . n)
=> k.O(n.logn)

Q3.If there are n integers to sort, each integer has d digits, and each digit is in the set {1, 2, ..., k}, radix sort can sort the numbers in:

(A)O(k (n + d))

(B)O(d (n + k))

(C) O((n + k) lg d)

(D) O((n + d) lg k)

If there are n integers to sort, each integer has d digits, and each digit is in the set {1, 2, ..., k}, radix sort can sort the numbers in O(d (n + k))

Q4.Radix Sort uses which of the following as a subroutine?

(A)Merge Sort

(B)Quick Sort

(C)Counting Sort

(D)Heap Sort

The idea of putting elements into buckets/containers to (which themselves are arranged in a particular order) to sort the elements; is the idea used in countsort.

Further Readings and References of the Experiment

Explore More About Radix