Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order. It is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. The time complexity is O(d(n+k)),where, d is the number cycle and O(n+k) is the time complexity of counting sort.
function radix(arr,div) {
let temp = [];
temp.length = 10;
for(let i = 0; i < temp.length ;i++ ){
temp[i] = 0;
}
let outputArray = new Array(arr.length);
for(let i = 0; i < arr.length; i++) {
temp[(Math.floor(arr[i] / div)) % 10]++;
}
temp[0] = temp[0]-1;
for(let i = 1; i < 10; i++) {
temp[i] += temp[i-1];
}
for(let i = arr.length-1; i >= 0; i--) {
let tempo = arr[i];
let index = temp[(Math.floor(arr[i]/div)) % 10]--;
outputArray[index] = tempo;
}
for(let i = 0; i < arr.length; i++) {
arr[i] = outputArray[i];
}
}
function radixsort(arr) {
let maximum = arr[0];
let minimum = arr[0];
for(let i = 0; i < arr.length; i++) {
if(arr[i] < minimum) {
minimum = arr[i];
}
if(arr[i] > maximum) {
maximum = arr[i];
}
}
for(let i=0;i < arr.length;i++) {
arr[i] -= minimum;
}
let maxLength = (maximum - minimum).toString().length;
for(let i = 0,div = 1; i < maxLength; i++,div *= 10) {
radix(arr,div);
}
for(let i = 0; i < arr.length; i++){
arr[i] += minimum;
}
return arr;
}
Best Case : Ω (nk)
Average Case : θ (nk)
Worst Case: O (nk)
O(n+k)
** where n is the length of the array and k is constant