# What is radix sort?

###
Sai gowtham
Nov 8
*Updated on Nov 12, 2018 *

Radix sort is a non-comparison based sorting algorithm where it grouping by the number place and position.

Example : [4, 57, 7, 3, 933]

### Radix sort algorithm implementation

First, we are implementing some helper functions

- If we pass an array of numbers getMax function returns back max number length.

suppose getMax([3, 44, 533]) // output 3

```
function getMax(arr) {
let max = 0;
for (let num of arr) {
if (max < num.toString().length) {
max = num.toString().length
}
}
return max
}
```

### Second helper function

if we pass a number and place getPosition function returns back number in that place.

```
function getPosition(num, place){
return Math.floor(Math.abs(num)/Math.pow(10,place))% 10
}
```

suppose

```
getPosition( 243 , 1 ) // 4
getPosition(123, 0) // 3
```

**Main algorithm starts.**

```
function radixSort(arr){
const max = getMax(arr); // returns length of max digit
return arr
}
```

If our max length is 4 we only loop 4 times

next, we need to write two for loops

first for loop helps us to get the number of places like 1's 10's 100's

and resetting the buckets.

```
function radixSort(arr){
const max = getMax(arr);
for(let i=0;i<max;i++){
let buckets = Array.from({length:10},()=>[ ]) // creating 10 empty arrays
arr = [].concat(...buckets);
}
return arr
}
```

second for loop is used to loop over every number in the unsorted array and

push into it's desired buckets.

```
function radixSort(arr) {
const max = getMax(arr);
for (let i = 0; i < max; i++) {
let buckets = Array.from({ length: 10 }, () => [ ])
for (let j = 0; j < arr.length; j++) {
buckets[getPosition(arr[ j ], i)].push(arr[ j ]); // pushing into buckets
}
arr = [ ].concat(...buckets);
}
return arr
}
```

we successfully implemented radix sort

**Tested using Mocha**

### Time and space complexity of Radix sort

- n - number of the elements in the array
- k - Max number length or word size

Hope you enjoyed...