C Online Compiler
Example: Postman Sort Algorithm in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS