Given an 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
http://en.wikipedia.org/wiki/Pancake_sortingUnlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible.
The goal is to sort the sequence in as few reversals as possible. 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.
1) Start from current size equal to n and reduce current size by one while it’s greater than 1. Let the current size be curr_size. Do following for every curr_size
……a) Find index of the maximum element in arr[0..curr_szie-1]. Let the index be ‘mi’
……b) Call flip(arr, mi)
……c) Call flip(arr, curr_size-1)
/* 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;}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); } }}/* 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--; }}http://rosettacode.org/wiki/Sorting_algorithms/Pancake_sort#Java
Read full article from Pancake sorting | GeeksforGeeks
