What is Radix Sort:
Radix sort is the linear sorting algorithm that is used for integers. In Radix
sort, there is digit by digit sorting is performed that is started from the
least significant digit to the most significant digit.
Working of Radix sort Algorithm:
Suppose we have given a unsorted array say [31, 27, 28, 42,28, 13,412] call
it "arr".
Step 1 Find Maximuim number of digits in array elemnts:
w.r.t. given array all elements are 2 digited except last which is 3 digited
so max number of digits in array element is 3.So three interation are
required to sort out array.
Step 2:
As max number of digits are 3 we will loop thrice.First we start at 0th
index then 1st and then 2 nd in all 3 iterations.
Iteration 1:
In this iteration we will look into 0th place of each digit in
array. Lets create an array of 10 empty array call it bucket.
bucket=[
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
In this bucket
1) first array element i.e. bucket[0] will correspond with digit 0
2) second array element i.e. bucket[1] will correspond with digit 1.
we will go on like this till last digit i.e. 9
...
10) 10th array element i.e. bucket[9] will corresponds with digit 9
we will start iterating over our array [31, 27, 28, 42,28, 13,412] from
0th index till end say counter is j.for each element we will find a digit
in that number at 0th place as we are in "iteration 1".if that digit is
say k where k will be between 0 to 9.we will push that element into
bucket's kth array element.e.g. if k is 3 then bucket[3].push(arr[j])
after completing this loop bucket array will be like
bucket=[
[],
[ 31 ],
[ 42, 412 ],
[ 13 ],
[],
[],
[],
[ 27 ],
[ 28, 28 ],
[]
]
Here we observe that an element of array "arr" goes to kth array element
of bucket if its 0th digit is k where k lies between 0 to 9.
Now we flatten the bucket into an array which will replace our "arr".
After flattening "arr" is like below
arr=[
31, 42, 412, 13,
27, 28, 28
]
Iteration 2:
In this iteration we will look into 1st place of each digit in array.
Lets again create an array of 10 empty array call it bucket.
bucket=[
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
In this bucket
1) first array element i.e. bucket[0] will correspond with digit 0
2) second array element i.e. bucket[1] will correspond with digit 1.
we will go on like this till last digit i.e. 9
...
10) 10th array element i.e. bucket[9] will corresponds with digit 9
we will start iterating over our array that we got as result of last
iteration i.e. arr =[31, 42, 412, 13,27, 28, 28] from 0th index till
end say counter is j.for each element we will find a digit in that number
at 1st place as we are in "iteration 2".If that digit is say k where k
will be between 0 to 9.we will push that element into bucket's kth array
element.e.g. if k is 3 then bucket[3].push(arr[j])
After completing this loop bucket array will be like
bucket =[
[],
[ 412, 13 ],
[ 27, 28, 28 ],
[ 31 ],
[ 42 ],
[],
[],
[],
[],
[]
]
Here we observe that an element of array "arr" goes to kth array element
of bucket if its 1st digit is k where k lies between 0 to 9.Now we flatten
the bucket into an array which will replace our "arr".
After flattening "arr" is like below
arr=[
412, 13, 27, 28,
28, 31, 42
]
Iteration 3:
In this iteration we will look into 2nd place of each digit in array.
Lets again create an array of 10 empty array call it bucket.
bucket=[
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
In this bucket
1) first array element i.e. bucket[0] will correspond with digit 0
2) second array element i.e. bucket[1] will correspond with digit 1.we
will go on like this till last digit i.e. 9
...
10) 10th array element i.e. bucket[9] will corresponds with digit 9
we will start iterating over our array that we got as result of last
iteration i.e. arr =[412, 13, 27, 28,28, 31, 42] from 0th index till end
say counter is j.for each element we will find a digit in that number at
2nd place as we are in "iteration 3".If that digit is say k where k will
be between 0 to 9.we will push that element into bucket's kth array
element.e.g. if k is 3 then bucket[3].push(arr[j])
After completing this loop bucket array will be like
bucket =[
[ 13, 27, 28, 28, 31, 42 ],
[],
[],
[],
[ 412 ],
[],
[],
[],
[],
[]
]
Here we observe that an element of array "arr" goes to kth array element
of bucket if its 2nd digit is k where k lies between 0 to 9.
Now we flatten the bucket into an array which will replace our "arr".
After flattening "arr" is like below
arr=[13, 27, 28, 28,31, 42, 412].Our Iterations ended here.
As promised its third iteration so our end result array
arr=[13, 27, 28, 28,31, 42, 412] is sorted now.
Javascript Implementation of Radix Algorithm:
Code:
//for given number num find digit at nth place where place start at 0 from
//right to left
const getNum = (num, n) => {
const strNum = String(num);
let end = strNum.length - 1;
const foundNum = strNum[end - n];
if (foundNum === undefined) return 0;
else return foundNum;
};
//find maximuim number of digits in array element
const largestNum = arr => {
let largest = "0";
arr.forEach(num => {
const strNum = String(num);
if (strNum.length > largest.length) largest = strNum;
});
return largest.length;
};
const radixSort = arr => {
let maxLength = largestNum(arr);
for (let i = 0; i < maxLength; i++) {
//create an array of array,outer array contain 10 empty array
let buckets = Array.from({ length: 10 }, () => []);
for (let j = 0; j < arr.length; j++) {
let num = getNum(arr[j], i);
//if num is k where k between 0 to 9 ,arr[j] is inserted into
// kth bucket,total 10 buckets for 0-9 digits
if (num !== undefined) {
buckets[num].push(arr[j]);
}
};
//flatten bucket array which is an array containing 10 array inside
//into single array
arr = buckets.flat();
};
return arr;
};
const unsortedArr = [31, 27, 28, 42,28, 13,412];
console.log(radixSort(unsortedArr));
Output:
[
13, 27, 28, 28,
31, 42, 412
]
No comments:
Post a Comment