C program to implement LSD Radix sort algorithm

In this tutorial, we will how to implement LSD Radix sort algorithm using the C program? By Nidhi Last updated : August 03, 2023

LSD radix sorts typically use the following sorting order: short keys come before longer keys, and then keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, like the sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. LSD sorts are generally stable sorts. Read more at Radix_sort Wikipedia

Problem statement

Here, we will create an array of integers with 5 items. Then we will implement LSD Radix sort to arrange array elements in ascending order and then print sorted array.

C program to implement LSD Radix sort algorithm

The source code to implement the LSD Radix sort algorithm is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to implement
// LSD Radix sort algorithm

#include <stdio.h>

void lsdRadixSort(int arr[], int arr1[], int len)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int t = 0;

    int min = 0;
    int tmp = 0;

    for (i = 0; i < len; i++)
        arr1[i] = arr[i];

    for (k = 0; k < 3; k++) {
        for (i = 0; i < len; i++) {
            min = arr[i] % 10;
            t = i;
            for (j = i + 1; j < len; j++) {
                if (min > (arr[j] % 10)) {
                    min = arr[j] % 10;
                    t = j;
                }
            }

            tmp = arr1[t];
            arr1[t] = arr1[i];
            arr1[i] = tmp;

            tmp = arr[t];
            arr[t] = arr[i];
            arr[i] = tmp;
        }
        for (j = 0; j < len; j++)
            arr[j] = arr[j] / 10;
    }
}
int main()
{
    int arr[5] = { 53, 36, 46, 22, 19 };
    int arr1[5];

    int i = 0;

    lsdRadixSort(arr, arr1, 5);

    printf("Sorted Array: \n");
    for (i = 0; i < 5; i++)
        printf("%d ", arr1[i]);
    printf("\n");

    return 0;
}

Output

Sorted Array:
19 22 36 46 53

Explanation

In the above program, we created two functions lsdRadixSort() and main(). The lsdRadixSort() is used to arrange array items in ascending order.

In the main() function, we created an array of integers arr with 5 elements. Then we sorted the elements of the array using lsdRadixSort() and printed the sorted array.