C Exercises: Sort numbers using Pancake Sort method

C Programming Searching and Sorting Algorithm: Exercise-22 with Solution

Write a C program that sorts numbers using the Pancake sort method.

From Wikipedia,
Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.

Sample Solution:

Sample C Code:

// Source: https://bit.ly/34Po5lN
// Sorting of array list using pancake sort
# include <stdio.h>
#include <stdlib.h>

/* Reverses the array */
void flip(int arr[], int i) {
    int temp, start = 0;

    while (start < i) {
        temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        start++;
        i--;
    }
}

// Returns index of the maximum element in arr[0..n-1]
int findMax(int arr[], int n) {
    int maxElementIdx, i;

    for (maxElementIdx = 0, i = 0; i < n; ++i)
        if (arr[i] > arr[maxElementIdx])
            maxElementIdx = i;

    return maxElementIdx;
}

// Sorts the array using flip operations
void pancakeSort(int *arr, int n) {
    // Start from the complete array and one by one reduce current size by one
    for (int curr_size = n; curr_size > 1; --curr_size) {
        // Find index of the maximum element in arr[0..curr_size-1]
        int maxElementIdx = findMax(arr, curr_size);

        // Move the maximum element to end of current array if it's not already
        // at the end
        if (maxElementIdx != curr_size - 1) {
            // To move at the end, first move maximum number to the beginning
            flip(arr, maxElementIdx);

            // Now move the maximum number to end by reversing the current array
            flip(arr, curr_size - 1);
        }
    }
}

// Displays the array, passed to this method
void display(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
}

#define N 50

// Driver program to test the above function
int main() {
    int arr[N];
    // Fill the array with random numbers
    for (int i = 0; i < N; i++)
        arr[i] = rand() % (N << 1); /* random numbers from 0 to 2N */

    printf("Original array: ");
    display(arr, N);

    // Sort the array using pancakeSort
    pancakeSort(arr, N);
    printf("Sorted array: ");
    display(arr, N);

    return 0;
}

Sample Output:

Original array: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 29 2 22 58 69 67 93 56 11 42 29 73 21 19 84 37 98 24 15 70 
Sorted array: 2 11 11 15 15 19 21 21 22 23 24 26 26 27 29 29 29 30 35 35 36 37 40 42 49 56 58 59 62 62 63 67 67 67 68 69 70 72 73 77 82 83 84 86 86 90 92 93 93 98 

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using partition sort method.
Next:Write a C program that sort numbers using Multi-key quicksort method.