C program for Radix Sort Algorithm

C program for Radix Sort Algorithm

517
2
SHARE

C program for Radix Sort Algorithm : Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.  Radix sort starts processing the keys from the most significant digit, leftmost digit, to the least significant digit, rightmost digit.  Radix sort stops rearranging the position of a key when the processing reaches a unique prefix of the key. Some MSD radix sorts use one level of buckets in which to group the keys.

Let us see how the Radix sort algorithm works :

  1. Take the most significant digit of each key(leftmost digit) and least significant digit, rightmost digit.
  2. Sort the list of elements based on that digit, grouping elements with the same digit into one bucket.
  3. Recursively sort each bucket, starting with the next digit to the right.
  4. Concatenate the buckets together in order.

Let us see how to write an efficient which accepts both signed and unsigned as input of the list and displays the sorted list obtained by Radix sort.

C program for Radix Sort Algorithm :

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <conio.h>

typedef unsigned uint;

/* sorting unsigned numbers */
static void rad_sort_u(uint *from, uint *to, uint bit)
{
	if (!bit || to < from + 1) return;

	uint *ll = from, *rr = to - 1, tmp;
	while (1) {
		/* find left most and right most, then swap */
		while (ll < rr && !(*ll & bit)) ll++;
		while (ll < rr &&  (*rr & bit)) rr--;
		if (ll >= rr) break;
		{ 
                  tmp = *ll;
                  *ll = *rr; 
                  *rr = tmp; 
                  }
	}

	if (!(bit & *ll) && ll < to) ll++;
	bit >>= 1;

	rad_sort_u(from, ll, bit);
	rad_sort_u(ll, to, bit);
}

/* sorting signed numbers */
static void radix_sort(int *a, const size_t len)
{
	size_t i;
	uint *x = (uint*) a;

	for (i = 0; i < len; i++)
    {
         x[i] ^= INT_MIN;
                         }
	rad_sort_u(x, x + len, INT_MIN);

	for (i = 0; i < len; i++)
    {
         x[i] ^= INT_MIN;
         }
}

static inline void radix_sort_unsigned(uint *a, const size_t len)
{
	rad_sort_u(a, a + len, (uint)INT_MIN);
}

int main(void)
{
	int len, x[20], i;
    printf("-----------------------------------------------------------\n");
    printf("----------------------Made by C code champ-----------------\n");
    printf("-----------------------------------------------------------\n\n");
    printf("\t\tRADIX SORT ALGORITHM\n\n\n\n");
    printf("Enter total elements : ");
    scanf("%d", &len);
    printf("\nEnter %d Elements : ", len);
    for (i = 0; i < len; i++)
    scanf("%d", &x[i]);

	radix_sort(x, len);
	printf("\n\n\nSorted list by Radix sort :\n ");
    for (i = 0; i < len; i++)
	printf("%d%c\t", x[i], i + 1 < len ? ' ' : '\n');
    getch();
	return 0;
}

We hope you all have enjoyed the for Radix Sort Algorithm. If you face any issues with the code or logic, ask us in form of comments.

2 COMMENTS

LEAVE A REPLY