Sorting Algorithm

Share

In this sorting algorithm we sort the unsorted elements digit wise starting from the least significant digit to the most significant digit.

For example: If we are dealing with unsorted numbers then we know that there are 10 digits from 0 to 9 that are used to form any number.

So, we will need 10 buckets labeled 0 to 9 to sort the unsorted numbers.

## Sort the numbers

10, 15, 1, 60, 5, 100, 25, 50

We have some unsorted numbers and our task is to sort them in ascending order. We know that there are 10 digits from 0 to 9. So, we will need 10 buckets labeled 0 to 9 in order to sort the given unsorted numbers.

## C Code

``````#include <stdio.h>

//const
#define MAX 10

//function declaration
void display(int arr[], int size);
int getMax(int arr[], int size);

int main() {
//unsorted elements
int arr[] = {10,15,1,60,5,100,25,50};

//size of the array
int n = sizeof(arr)/sizeof(arr);

//output unsorted elements
display(arr, n);

//sort the elements

//display sorted elements
display(arr, n);

return 0;
}

void display(int arr[], int size) {
int i;
for(i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int getMax(int arr[], int size) {
int i, max = arr;
for(i = 1; i < size; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
return max;
}

void radixSort(int arr[], int size) {
int i, max, bucket[MAX], count, expo = 1;

//get the max value element in the unsorted array
max = getMax(arr, size);

while(max / expo > 0) {
//reset count
for(i = 0; i < 10; i++) {
count[i] = 0;
}

//save count of the occurrence
for(i = 0; i < size; i++) {
count[ (arr[i] / expo) % 10 ]++;
}

//set count to contain the actual position of the digits
for(i = 1; i < size; i++) {
count[i] += count [i - 1];
}

//build the bucket
for(i = size - 1; i >= 0; i--) {
bucket[ count[ (arr[i]/expo) % 10 ]  - 1] = arr[i];
count[ (arr[i]/expo) % 10 ]--;
}

//copy the result to arr
for(i = 0; i < size; i++) {
arr[i] = bucket[i];
}

//increase expo, 10^x
expo *= 10;
}
}
``````
Share