Radix Sort Assignment 2022

Running head: RADIX SORT 1
Assignment
Student
Course
Instructor
Date

RADIX SORT 2
Radix Sort
A data structure is a systematic way of organizing and storing any data on a computer
system so that it can be stored and retrieved efficiently. There are various ways of storing data in
a program and the data can be stored in sequential or non-sequential manner. Algorithm is the
process of solving a particular problem by a sequence of steps. A procedure is carried out in a
step by step manner to get the required result from the provided data. ("What is algorithm? -
Definition from WhatIs.com", 2019)
Sorting in Data is any process of rearranging all the items in a systematic manner. All the
items are ordered by particular criteria. A Sorting algorithm specifies the sequence of steps to
follow in order to arrange the provided data in a particular order. It is very important to choose a
good sorting algorithm as the run time of a program and the space utilized by it is entirely
dependent on the sorting algorithm.("Sorting Techniques in Data Structures", 2019)
Radix sort is a small method that is used widely for sorting very large data inputs. Radix
sort works by sorting the inputs digit by digit. In the first pass, the data is sorted by the least
significant digit and then it is combined in an array. ("Radix Sort - GeeksforGeeks", 2019)
In the subsequent passes, the data is sorted again with the next significant digit and the process
continues till the data is sorted by the most significant digit. ("DAA - Radix Sort", 2019)

RADIX SORT 3
Radix Sort.java Program
import java.util.Arrays;
public class RadixSort {
private int[] array;
public RadixSort(int[] array) {
super();
this.array = array;
}
private int maxNumber()
{
int max = array[0];
for (int i = 0; i < array.length; i++)
{
if (array[i] > max)

RADIX SORT 4
max = array[i];
}
return max;
}
public void sort()
{
int passNumber=1;
int max=maxNumber();
int exponent=1;
// go through each decimal place
while(max/exponent>0)
{
/**
* We will use count Sort to sort
*/

RADIX SORT 5
int[] countArray=new int[10];// as this is base
10
int[] outputArray=new int[array.length]; //
output Array
// initialize array to 0
Arrays.fill(outputArray,0);
for(int i=0;i<array.length;i++)
{
int placeValue=(array[i]/exponent)%10; //
value at this decimal place
countArray[placeValue]++;
}
for(int i=1;i<10;i++)
{

RADIX SORT 6
countArray[i] = countArray[i]+ countArray[i
-1];
}
// we will make the final output array here
int index = array.length-1;
while(index>=0)
{
int placeValue=(array[index]/exponent)%10;
// value at this decimal place
outputArray[countArray[ placeValue ] - 1] =
array[index];
int coutArrayValue=countArray[placeValue] -
1 ;
outputArray[coutArrayValue] = array[index];
countArray[placeValue]--;
index--;

RADIX SORT 7
}
// copy the values from
System.arraycopy(outputArray,0,array,0,array.length);
System.out.println("\nArray after pass Number
"+passNumber++);
System.out.println(Arrays.toString(array));
exponent = exponent * 10;
}
}
public int[] getArray() {
return array;
}
}

RADIX SORT 8
Description
private int maxNumber()
{
int max = array[0];
for (int i = 0; i < array.length; i++)
{
if (array[i] > max)
max = array[i];
}
return max;
}
This method is being used to find the largest number in the past list of numbers. This method
takes the list of numbers as argument and returns the largest number from this list.
public void sort()

RADIX SORT 9
{
int passNumber=1;
int max=maxNumber();
int exponent=1;
// go through each decimal place
while(max/exponent>0)
{
/**
* We will use count Sort to sort
*/
int[] countArray=new int[10];// as this is base
10
int[] outputArray=new int[array.length]; //
output Array
// initialize array to 0

RADIX SORT 10
Arrays.fill(outputArray,0);
for(int i=0;i<array.length;i++)
{
int placeValue=(array[i]/exponent)%10; //
value at this decimal place
countArray[placeValue]++;
}
for(int i=1;i<10;i++)
{
countArray[i] = countArray[i]+ countArray[i
-1];
}
// we will make the final output array here
int index = array.length-1;
while(index>=0)
{

RADIX SORT 11
int placeValue=(array[index]/exponent)%10;
// value at this decimal place
outputArray[countArray[ placeValue ] - 1] =
array[index];
int coutArrayValue=countArray[placeValue] -
1 ;
outputArray[coutArrayValue] = array[index];
countArray[placeValue]--;
index--;
}
// copy the values from
System.arraycopy(outputArray,0,array,0,array.length);

RADIX SORT 12
System.out.println("\nArray after pass Number
"+passNumber++);
System.out.println(Arrays.toString(array));
exponent = exponent * 10;
}
This method starts from the least significant digit until most significant digit of the maximum
number pass by pass. In each pass, it will use count sort to sort the input array by that particular
digit place. So, in the end we will get the sorted array as result.
Screenshot of Sample Run

RADIX SORT 13
Step By Step Process
Array Before Sorting:
[783, 99, 472, 182, 264, 543, 356, 295, 692, 491, 94]
Array after pass Number 1
[491, 472, 182, 692, 783, 543, 264, 94, 295, 356, 99]

RADIX SORT 14
Array after pass Number 2
[543, 356, 264, 472, 182, 783, 491, 692, 94, 295, 99]
Array after pass Number 3
[94, 99, 182, 264, 295, 356, 472, 491, 543, 692, 783]
Final Array After Sorting:
[94, 99, 182, 264, 295, 356, 472, 491, 543, 692, 783]
Big-Oh Notation
Let the number of digits in the maximum integer in the input = d
Let the total numbers = n
Here, the program will contain a loop from 1 to n to sort the number digit by digit.
So Time Comlexity = O(nd)
Conclusion

RADIX SORT 15
It can be concluded that an algorithm is the most important aspect to solve any problem. The
choice of an algorithm is very crucial for the run time and memory management of a program
irrespective of the programming language used. Also, it is observed that the data is hard-coded in
the python program and this data is being sorted by using the radix sort algorithm inside this
program itself. Furthermore, python provides the capability to implement various algorithms
using its vast libraries.

RADIX SORT 16
References
Tutorials Point. (2019) DAA - Radix Sort. Retrieved 25 August 2019, from
https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis
_of_algorithms_radix_sort.htm
GeeksforGeeks. (2019) Radix Sort. Retrieved 25 August 2019, from
https://www.geeksforgeeks.org/radix-sort/
w3schools. (2019) Sorting Techniques in Data Structures. Retrieved 25 August 2019, from
https://www.w3schools.in/data-structures-tutorial/sorting-techniques/
WhatIs.com. (2019) What is algorithm? – Definition. Retrieved 25 August 2019, from
https://whatis.techtarget.com/definition/algorithm