C Exercises: Sort numbers using Permutation Sort method

Last update on March 20 2025 12:39:00 (UTC/GMT +8 hours)

16. Permutation Sort Variants

Write a C program that sorts numbers using the Permutation Sort method.

Permutation sort, proceeds by generating the possible permutations of the input array/list until discovering the sorted one.

Sample Solution:

Sample C Code:

// Permutation Sort Implementation
// Source: https://bit.ly/2rcvXK5
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Type definition for the comparison function
typedef int (*cmp_func)(const void *, const void *);

// Function to perform permutation sort on an array
void perm_sort(void *a, int n, size_t msize, cmp_func _cmp);

// String comparison function used for sorting strings
int scmp(const void *a, const void *b);

// Main function
int main() {
    int i;
    const char *strs[] = { "spqr", "abc", "giant squid", "stuff", "def" };

    // Display original array
    printf("Original Array:\n");
    int n = 5;
    for (i = 0; i < n; i++)
        printf("%s   ", strs[i], i == n - 1 ? "\n" : " ");

    // Perform permutation sort on the array
    perm_sort(strs, 5, sizeof(*strs), scmp);

    // Display sorted array
    printf("\nSorted Array:\n");
    for (i = 0; i < 5; i++)
        printf("%s   ", strs[i]);

    return 0;
}

// Function to perform permutation sort on an array
void perm_sort(void *a, int n, size_t msize, cmp_func _cmp) {
    char *p, *q, *tmp = malloc(msize);

    // Define macros for array indexing and swapping
    #define A(i) ((char *)a + msize * (i))
    #define swap(a, b) {\
        memcpy(tmp, a, msize);\
        memcpy(a, b, msize);\
        memcpy(b, tmp, msize); }

    while (1) {
        // Find largest k such that a[k - 1] < a[k]
        for (p = A(n - 1); (void *)p > a; p = q)
            if (_cmp(q = p - msize, p) > 0)
                break;

        if ((void *)p <= a) break;

        // Find largest l such that a[l] > a[k - 1]
        for (p = A(n - 1); p > q; p -= msize)
            if (_cmp(q, p) > 0) break;

        // Swap a[k - 1], a[l]
        swap(p, q);

        // Flip a[k] through a[end]
        for (q += msize, p = A(n - 1); q < p; q += msize, p -= msize)
            swap(p, q);
    }

    free(tmp);
}

// String comparison function used for sorting strings
int scmp(const void *a, const void *b) {
    return strcmp(*(const char *const *)a, *(const char *const *)b);
}

Sample Output:

Original Array:
spqr   abc   giant squid   stuff   def   
Sorted Array:
abc   def   giant squid   spqr   stuff

Flowchart:

For more Practice: Solve these Related Problems:

Write a C program to implement permutation sort on a small array and count the number of generated permutations.
Write a C program to sort an array using permutation sort and then verify the sorted order via binary search.
Write a C program to implement permutation sort on an array of characters and print the lexicographically smallest permutation.
Write a C program to analyze the time complexity of permutation sort by tracking the number of permutations generated.

C Programming Code Editor:

Previous: Write a C program that sort numbers using Cycle Sort method.
Next:Write a C program to sort a list of elements using the insertionsort algorithm.