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; } |
Output:
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!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
