1 hour
Introduction video
This experiment requires you to have basic knowledge about :
And above all, a curiosity to learn and explore!
In this experiment, you will be able to do the following:
Module | Weightage | Expectation |
---|---|---|
Pre-Test | 20% | Solve All Questions |
Radix sort | 50% | Understand and Practice the full algorithm |
Post-test | 30% | Solve all Questions |
10 minutes
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.
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(N^{2}).
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.
10 minutes
radixsort video
In this module, we will :
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 :
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).
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 i^{th} position :
For example:
Say 3^{rd}rd least significant digit of 26438, that is the the
hundred's position.
First divide by 10^{3-1} = 10^{2} = 100.
26438 / 100 = 264.
Then take modulus with 10.
264 % 10 = 4
4 is the third least significant digit.
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.
Radix Sort animation
Representation of the whole process
Practice of the whole process
Exercise of the whole process
20 minutes
Time complexity is explained
The running time complexity of radix sort in O(nd) where :
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)
Space Complexity for Radix sort is O(n+b) where :
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)
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.
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.
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.
Algorithm | Time | Features | |||
---|---|---|---|---|---|
Sort | Average | Best | Worst | Space | Stability |
Radix sort | O(nk) | O(nk) | O(nk) | O(n+b) | Stable |
Bubble sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | Constant | Stable |
Modified Bubble sort | O(n^{2}) | O(n) | O(n^{2}) | Constant | Stable |
Selection Sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | Constant | Stable |
Insertion Sort | O(n^{2}) | O(n) | O(n^{2}) | 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(n^{2}) | Constant | Stable |
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:
Q1. What is the complexity of Radix sort?
(A) Best case O(nk)
(B) Best case O(n^{2})
(C) Worst case O(n^{2})
(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(log_{b}N)
(B) k = floor(log_{b}N)
(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 log_{b}N
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.
10 minutes
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.
Q1. Given an array where numbers are in range from 1 to n^{6}, 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 (n^{k/2},n^{k}, 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(n^{2})
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.
You can explore more about Radix Experiment through following resources: