C program to implement postman sort algorithm

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

Postman sort works by sorting the integers of an array from their most significant digits to their least significant digits. In the Postman sort the integer having most significant digits and the number of elements in that integer is determined, the length of the longest integer is stored. All the elements in the array are divided by a particular base. The elements of the array are sorted on the basis of the most significant digit to the least significant digit i.e. from leftmost to rightmost digit. Ref: Postman Sort

Problem statement

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

C program to implement postman sort algorithm

The source code to implement the postman 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 postman sort algorithm

#include <stdio.h>

void arrangeItems(int arr[], int arr1[], int k, int n)
{
    int temp = 0;
    int i = 0;
    int j = 0;

    for (i = k; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (arr1[i] > arr1[j]) {
                temp = arr1[i];
                arr1[i] = arr1[j];
                arr1[j] = temp;

                temp = (arr[i] % 10);
                arr[i] = (arr[j] % 10);
                arr[j] = temp;
            }
        }
    }
}

int main()
{
    int i = 0;
    int j = 0;
    int c = 0;
    int t = 0;
    int k = 0;
    int n = 1;

    int t1 = 0;
    int t2 = 0;
    int n1 = 0;

    int max = 0;
    int len = 0;
    int maxd = 0;
    int temp = 0;

    int arr[5] = { 53, 36, 46, 22, 19 };
    int arr1[5];

    len = sizeof(arr) / sizeof(arr[0]);

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

    for (i = 0; i < len; i++) {
        t = arr[i];
        while (t > 0) {
            c++;
            t = t / 10;
        }
        if (maxd < c)
            maxd = c;
        c = 0;
    }
    while (--maxd)
        n = n * 10;

    for (i = 0; i < len; i++) {
        max = arr[i] / n;
        t = i;

        for (j = i + 1; j < len; j++) {
            if (max > (arr[j] / n)) {
                max = arr[j] / n;
                t = j;
            }
        }

        temp = arr1[t];
        arr1[t] = arr1[i];
        arr1[i] = temp;

        temp = arr[t];
        arr[t] = arr[i];
        arr[i] = temp;
    }
    while (n >= 1) {
        for (i = 0; i < len;) {
            t1 = arr[i] / n;
            for (j = i + 1; t1 == (arr[j] / n); j++)
                ;
            arrangeItems(arr, arr1, i, j);
            i = j;
        }
        n = n / 10;
    }

    printf("Sorted Array:\n");
    for (i = 0; i < len; 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 arrangeItems() and main(). The arrangeItems() is used to arrange array items of specified arrays.

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