Example: Pancake Sort Algorithm in C

// Pancake Sort Algorithm
#include <stdio.h>
#include <stdlib.h> // For malloc (if dynamically allocating, not strictly needed for this example)

// Function to reverse a prefix of an array
void flip(int arr[], int k) {
    int start = 0;
    while (start < k) {
        int temp = arr[start];
        arr[start] = arr[k];
        arr[k] = temp;
        start++;
        k--;
    }
}

// Function to find the index of the maximum element in a given sub-array
int findMax(int arr[], int n) {
    int max_idx = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > arr[max_idx]) {
            max_idx = i;
        }
    }
    return max_idx;
}

// The main pancake sort function
void pancakeSort(int arr[], int n) {
    // Start from the complete array and reduce the size of the current unsorted array
    for (int current_size = n; current_size > 1; current_size--) {
        // Step 1: Find the index of the maximum element in the current unsorted sub-array
        int max_idx = findMax(arr, current_size);

        // If the maximum element is not already at its correct position
        // (i.e., at the end of the current unsorted sub-array)
        if (max_idx != current_size - 1) {
            // Step 2: Move the maximum element to the beginning of the array
            // by flipping the sub-array from index 0 to max_idx
            flip(arr, max_idx);

            // Step 3: Move the maximum element from the beginning to its correct position
            // (current_size - 1) by flipping the entire current unsorted sub-array
            flip(arr, current_size - 1);
        }
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {3, 2, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    pancakeSort(arr, n);

    printf("Sorted array (Pancake Sort): ");
    printArray(arr, n);

    int arr2[] = {10, 20, 30, 40, 50, 60, 70};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("Original array 2: ");
    printArray(arr2, n2);
    pancakeSort(arr2, n2);
    printf("Sorted array 2 (Pancake Sort): ");
    printArray(arr2, n2);

    int arr3[] = {5, 4, 3, 2, 1};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("Original array 3: ");
    printArray(arr3, n3);
    pancakeSort(arr3, n3);
    printf("Sorted array 3 (Pancake Sort): ");
    printArray(arr3, n3);

    return 0;
}