Given an unsorted array, sort the given array. You are allowed to do only following operation on array.
flip(arr, i): Reverse array from 0 to i
C
/* C program for Pancake Sorting */ #include <stdio.h> #include <stdlib.h> /* Reverses arr[0..i] */ 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 mi, i; for (mi = 0, i = 0; i < n; ++i) if (arr[i] > arr[mi]) mi = i; return mi; } // The main function that sorts given array using flip // operations int 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 mi = findMax(arr, curr_size); // Move the maximum element to end of current array // if it's not already at the end if (mi != curr_size - 1) { // To move at the end, first move maximum number // to beginning flip(arr, mi); // Now move the maximum number to end by reversing // current array flip(arr, curr_size - 1); } } } /* A utility function to print an array of size n */ void printArray( int arr[], int n) { for ( int i = 0; i < n; ++i) printf ( "%d " , arr[i]); } // Driver program to test above function int main() { int arr[] = { 23, 10, 20, 11, 12, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); pancakeSort(arr, n); puts ( "Sorted Array " ); printArray(arr, n); return 0; } |
Sorted Array 6 7 10 11 12 20 23
Time Complexity: O(n2)
Auxiliary Space: O(1)
Please refer complete article on Pancake sorting for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!