Radix sortRadix sort is a sorting algorithm 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.
Example :
Algorithm Radixsort [A (0..n-1)]
// Sort a given array by radix sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
radixSort(array)
d <- maximum number of digits in the largest element
create d buckets of size 0-9
for i <- 0 to d
sort the elements according to ith place digits using countingSort
countingSort(array, d)
max <- find largest element among dth place elements
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique digit in dth place of elements and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 1
#include
int get_max (int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void radix_sort (int a[], int n){
int bucket[10][10], bucket_cnt[10];
int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
lar = get_max (a, n);
while (lar > 0){
NOP++;
lar /= 10;
}
for (pass = 0; pass < NOP; pass++){
for (i = 0; i < 10; i++){
bucket_cnt[i] = 0;
}
for (i = 0; i < n; i++){
r = (a[i] / divisor) % 10;
bucket[r][bucket_cnt[r]] = a[i];
bucket_cnt[r] += 1;
}
i = 0;
for (k = 0; k < 10; k++){
for (j = 0; j < bucket_cnt[k]; j++){
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf ("After pass %d : ", pass + 1);
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}
int main (){
int i, n, a[10];
printf ("Enter the number of items to be sorted: ");
scanf ("%d", &n);
printf ("Enter items: ");
for (i = 0; i < n; i++){
scanf ("%d", &a[i]);
}
radix_sort (a, n);
printf ("Sorted items : ");
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
return 0;
}
Code
import java.util.*;
public class my_radix_sorting {
static int get_max_val(int my_arr[], int arr_len) {
int max_val = my_arr[0];
for (int i = 1; i < arr_len; i++)
if (my_arr[i] > max_val)
max_val = my_arr[i];
return max_val;
}
static void countSort(int my_arr[], int arr_len, int exp) {
int result[] = new int[arr_len];
int i;
int count[] = new int[10];
Arrays.fill(count,0);
for (i = 0; i < arr_len; i++)
count[ (my_arr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = arr_len - 1; i >= 0; i--) {
result[count[ (my_arr[i]/exp)%10 ] - 1] = my_arr[i];
count[ (my_arr[i]/exp)%10 ]--;
}
for (i = 0; i < arr_len; i++)
my_arr[i] = result[i];
}
static void radix_sort(int my_arr[], int arr_len) {
int m = get_max_val(my_arr, arr_len);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(my_arr, arr_len, exp);
}
public static void main (String[] args) {
int my_arr[] = {56, 78, 102, 345, 67, 90, 102, 45, 78};
int arr_len = my_arr.length;
System.out.println("The array after performing radix sort is ");
radix_sort(my_arr, arr_len);
for (int i=0; i< arr_len; i++)
System.out.print(my_arr[i]+" ");
}
}
Code
def counting_Sort(arr, p):
s = len(arr)
result = [0] * s
c = [0] * 10
# count of elements
for i in range(0, s):
index = arr[i] // p
c[index % 10] += 1
# cumulative count
for i in range(1, 10):
c[i] += c[i - 1]
# sorted order
i = s - 1
while i >= 0:
index = arr[i] // p
result[c[index % 10] - 1] = arr[i]
c[index % 10] -= 1
i -= 1
for i in range(0, s):
arr[i] = result[i]
# radix sort
def radix_Sort(arr):
maximum = max(arr)
p = 1
while maximum // p > 0:
counting_Sort(arr, p)
p *= 10
#driver code
array = [354, 954, 411, 9]
print("The original array is: ", array)
radix_Sort(array)
print("The sorted array is: ", array)
Code
354, 954, 411, 9
9, 354, 411, 954
best case, average case, worst case
Merge sort
Selection sort
