Radix Sort Golang

Graphicaldot

This sorting algorithm is based on the values of the digits in the positional representation of numbers to be sorted.

If we want to find which number is greater between two such numbers, it may be done in the following way: Starting with the least significant digit, we check which number has larger digit. The number with the larger most significant digit is the greater number. If all digits match, the numbers are equal.

Algorithm

This technique is implemented in radix sort algorithm.

The elements are populated in an array. The radix sort algorithm implements an array of length 10 beginning with 0 and ends with element 9. Lets call it count array. The count array is maintained corresponding to the elements in the decimal number system. count[0] i.e index 0 in count array, is for holding count of numbers whose digits ends with 0. Similarly count[1] to count[9] are for holding count of numbers ending in digits 1–9.

Let us consider the following example: Considering the following numbers and lets call them “initial” array:

170  45  75  90  802  998  1234  24  2  66 121 223

Iteration 1:

starts with number 170, 0 is the least significant digit. We will increment count[0] by 1.

similarly 5 is the least significant digit of 45, so we will increment count[5] by 1. Continuing with the process, We will have the following structure of count Array based on the least significant digit.

count [0] : 2
count [1] : 1
count [2] : 2
count [3] : 1
count [4] : 2
count [5] : 2
count [6] : 1
count [7] : 0
count [8] : 1
count [9] : 0

Count array transformation:

We will add consecutive indexes of count array, so that “initial” array elements can find their position.

[1 2 4 5 7 9 10 10 11 11]for i := 1; i <len(*count); i ++{
(*count)[i] = (*count)[i] + (*count)[i-1]
}

Its time to build an intermediate Aux array. We will begin from the end of “initial”array. The number 223 has 3 as its least significant digit. we will look at the count array at index 3, which has a value 5.

So in “Aux” array we will put 223 at position 5. So aux array state is

0 0 0 0 0 123 0 0 0 0 0 0

and decrement count[3] by 1. New state of count array is

[1 2 4 4 7 9 10 10 11 11]

Lets look at another number 121, its least significant digit is 1.

lookup in count array at index 1 reveals new position for 121 in aux array which is 2. The “Aux” state becomes

0 0 121 0 0 123 0 0 0 0 0 0

decrement count array at index 1 will give us new state for count array i.e

[1 2 3 4 7 9 10 10 11 11]

We will continue till we reach the beginning of “initial” array. The final “Aux” array is :

170 90 121 802 2 223 1234 24 45 75 66 998

This marks the end of iteration 1 for least significant digit of numbers present in the “initial” array.

Since the greatest number present in “initial” array is 4 digits long, we will have four iterations. Iteration 2 will involve 2nd significant digit and so on.

package mainimport (
"fmt"
"strconv"
"math"
"strings"
)
//BigNumPlaceCount to find the biggest number in an array
//and find the length of this biggest number, for example if
//the largest element in a target array is 4 digits long
//this function will return 4
func BigNumPlaceCount(arr []int) int {
for i := 1; i < len(arr); i++{
if arr[i] < arr[i-1]{
rplc := arr[i-1]
arr[i-1] = arr[i]
arr[i] = rplc
}
}
biggest := arr[len(arr)-1]
return len(strconv.Itoa(biggest))
}func Loop(divisor int, intArr []int, count *[10]int){for _, value := range intArr {
rem := (value/divisor)%10
(*count)[rem] += 1
}
(*count)[0] = (*count)[0] -1

for i := 1; i <len(*count); i ++{
(*count)[i] = (*count)[i] + (*count)[i-1]
}
}
//AuxArray generate a new array for a place value divisor
// The new array will be sorted according to the place value in
//numbers
func AuxArray(divisor int, intArr []int, count *[10]int) []int {
//Start from the end
aux := make([]int, len(intArr))
for i := len(intArr) - 1; i >= 0; i-- {
//find the target significant digit, if divisor is 10,
//find the 10th place digit in the number.
k := (intArr[i] / divisor) % 10
//find the value corrsponding to this index in the count array
index := (*count)[k]
//Now in aux array, put this number at the index
aux[index] = intArr[i]
//Decrement the count array at the kth index.
(*count)[k]--
//fmt.Printf("Count %v -- Aux %v --- IntArr %v\n", *count, intArr, aux)
}
return aux
}
func RadixSort(intArr []int) []int{
tmp := make([]int, len(intArr))
copy(tmp, intArr)
places := BigNumPlaceCount(tmp)


for index, _ := range make([]int, places){

place := int(math.Pow(float64(10), float64(index)))

count := [10]int{}

Loop(place, intArr, &count)
intArr = AuxArray(place, intArr, &count)
printString(intArr)
}


return intArr
}func printString(arr []int){
z := []string{}

for _, value := range arr{

z = append(z, strconv.Itoa(value))
}
fmt.Println(strings.Join(z, " "))
}
func main() {
a := []int{170, 45, 75, 90, 802, 998, 1234, 24, 2, 66, 121, 223}
RadixSort(a)

}

Analysis

Each key is looked at once for each digit (or letter if the keys are alphabetic) of the longest key. Hence, if the longest key has m digits and there are n keys, radix sort has order O(m.n).

However, if we look at these two values, the size of the keys will be relatively small when compared to the number of keys. For example, if we have six-digit keys, we could have a million different records.

Here, we see that the size of the keys is not significant, and this algorithm is of linear complexity O(n).

Feel free to email me at graphicaldot@zoho.com

Graphicaldot

Written by

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade