Example: Postman Sort Algorithm in C

// Postman Sort Algorithm
#include <stdio.h>
#include <stdlib.h> // For malloc, free
#include <string.h> // For strcpy, strlen

// Structure to represent a mail item with multiple keys
typedef struct MailItem {
    int zipCode;
    int districtID;
    int houseNumber;
    char addressLabel[50]; // For display purposes
} MailItem;

// Helper function to get the maximum value for a specific key
int getMax(MailItem arr[], int n, int keyType) {
    int max = 0;
    if (n == 0) return 0;

    switch (keyType) {
        case 0: // houseNumber
            max = arr[0].houseNumber;
            for (int i = 1; i < n; i++) {
                if (arr[i].houseNumber > max)
                    max = arr[i].houseNumber;
            }
            break;
        case 1: // districtID
            max = arr[0].districtID;
            for (int i = 1; i < n; i++) {
                if (arr[i].districtID > max)
                    max = arr[i].districtID;
            }
            break;
        case 2: // zipCode
            max = arr[0].zipCode;
            for (int i = 1; i < n; i++) {
                if (arr[i].zipCode > max)
                    max = arr[i].zipCode;
            }
            break;
    }
    return max;
}

// A utility function to do counting sort of arr[] according to
// the key represented by keyType (0 for houseNumber, 1 for districtID, 2 for zipCode)
void countingSortForKey(MailItem arr[], int n, int keyType) {
    MailItem *output = (MailItem *) malloc(n * sizeof(MailItem));
    if (output == NULL) {
        perror("Failed to allocate memory for output array");
        exit(EXIT_FAILURE);
    }

    int maxKey = getMax(arr, n, keyType);
    int *count = (int *) calloc((maxKey + 1), sizeof(int));
    if (count == NULL) {
        perror("Failed to allocate memory for count array");
        free(output);
        exit(EXIT_FAILURE);
    }

    // Store count of occurrences in count[]
    for (int i = 0; i < n; i++) {
        switch (keyType) {
            case 0: count[arr[i].houseNumber]++; break;
            case 1: count[arr[i].districtID]++; break;
            case 2: count[arr[i].zipCode]++; break;
        }
    }

    // Change count[i] so that count[i] now contains actual
    // position of this key in output array
    for (int i = 1; i <= maxKey; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array (iterate from end to maintain stability)
    for (int i = n - 1; i >= 0; i--) {
        switch (keyType) {
            case 0:
                output[count[arr[i].houseNumber] - 1] = arr[i];
                count[arr[i].houseNumber]--;
                break;
            case 1:
                output[count[arr[i].districtID] - 1] = arr[i];
                count[arr[i].districtID]--;
                break;
            case 2:
                output[count[arr[i].zipCode] - 1] = arr[i];
                count[arr[i].zipCode]--;
                break;
        }
    }

    // Copy the output array to arr[], so that arr[] now contains sorted numbers
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(output);
    free(count);
}

// The main function to perform Postman Sort
// Sorts by houseNumber, then districtID, then zipCode
void postmanSort(MailItem arr[], int n) {
    // Sort by houseNumber (LSD)
    countingSortForKey(arr, n, 0);

    // Sort by districtID
    countingSortForKey(arr, n, 1);

    // Sort by zipCode (MSD)
    countingSortForKey(arr, n, 2);
}

// Function to print an array of MailItem
void printMailItems(MailItem arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("Zip: %5d, Dist: %2d, House: %3d, Address: %s\n",
               arr[i].zipCode, arr[i].districtID, arr[i].houseNumber, arr[i].addressLabel);
    }
}

int main() {
    // Step 1: Initialize mail items
    MailItem mail[] = {
        {12345, 2, 101, "101 Elm St, Dist 2, ZC 12345"},
        {12345, 1, 203, "203 Oak Ave, Dist 1, ZC 12345"},
        {54321, 3, 50,  "50 Pine Rd, Dist 3, ZC 54321"},
        {12345, 2, 99,  "99 Elm St, Dist 2, ZC 12345"},
        {54321, 1, 15,  "15 Pine Rd, Dist 1, ZC 54321"},
        {98765, 1, 1,   "1 Maple Ln, Dist 1, ZC 98765"},
        {12345, 1, 203, "203 Main St, Dist 1, ZC 12345"}, // Duplicate houseNumber and zip with different street
        {98765, 1, 10,  "10 Maple Ln, Dist 1, ZC 98765"}
    };
    int n = sizeof(mail) / sizeof(mail[0]);

    printf("Original Mail Items:\n");
    printMailItems(mail, n);
    printf("\n");

    // Step 2: Apply Postman Sort
    postmanSort(mail, n);

    // Step 3: Print sorted mail items
    printf("Sorted Mail Items (by houseNumber, then districtID, then zipCode):\n");
    printMailItems(mail, n);

    return 0;
}