Pancake Sorting (Which Uses Only Reverse Function to sort the Array)

There is an array in an external system (i.e. u cannot access the array elements directly). The system exposes 3 functions of O(1) :

length() - returns the length of the array.
get(i) - returns the element at index i.
reverse(i,j) - reverses the elements in the array from index i to index j (both indexes inclusive).

Can you sort the array in the best possible way using only these 3 operations?


Pancake sort has a direct implementation complexity of O(N2) as locating the max element in the unsorted section of the array is an O(N) operation. Besides this, it is obvious that one cannot use standard quicksort or heapsort directly since a swap operation
isn't supplied. However, we can simulate a swap operation using the reverse operator. It's easy to do:


swap(i, j) = reverse(i + 1, j) reverse(i, i+1), reverse(i+1, j) where i, j are indices to the array.


Given this swap operation, we can then implement any O(n log n) sort that we desire since we already have random access via the get(i) function.

However, we can do better:

Let us define a run as a sequence of consecutive values in the array.

1. Go through the array and reverse descending runs - O(n) as reverse(i, j) is supplied. Now you have an array with many runs in ascending order. It looks something like a0, a1 ... ak, b0, b1, ... bl, c0, c1, ... cm ...
2. Perform a merge procedure pairwise for consecutive runs in the array. The merge is performed as follows:
If a0, a1, a2 ...ak b0, b1, b2... bl are consecutive runs, then:
a) Compare a0, b0 (using get() operation to get the values).
--- Else If b0 < a0 then perform step (b). --- Else a0 is in its correct place, increment pointer to the 'a' array and repeat step 2 for a1... ak, b0 ... bl b) reverse(a0 ... b0) and then reverse (ak ... a0) - giving b0, a0, a1 ... ak, b1, b2 .. bl. Repeat step 2 for the run a0, a1 ... ak, b1, b2 ... bl Basic Approach I used Insertion Sort to Solve it First #include

/* Function to reverse arr[] from start to end*/
void rvereseArray(int arr[], int start, int end)
{

int temp;
while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } /* Utility that prints out an array on a line */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int get(int ar[],int i) { return ar[i]; } int length(int ar[]) { return (sizeof(ar)/sizeof(int)); } void sort(int arr[]) {int i,j; for( i = 1; i < 6; i++ ) { int index = i; for( j = i-1; j >= 0; j-- )
{
if( arr[j] > arr[index] )
{
rvereseArray(arr, j, index);
index = j;
}
}
}
}

/* Driver function to test above functions */
int main()
{
int arr[] = {3,1, 2, 5,4, 6};
printArray(arr, 6);

sort(arr);

printArray(arr,6);

return 0;
}

TC O(n^2)
SC O(1)
Run Here https://ideone.com/A3UUj

MOre professional Code

int pancake_sort(int *list, unsigned int length)
{
//If it's less than 2 long, just return it as sorting isn't really needed...
if(length<2) return 0; int i,a,max_num_pos,moves; moves=0; for(i=length;i>1;i--)
{
//Find position of the max number in pos(0) to pos(i)
max_num_pos=0;
for(a=0;alist[max_num_pos])
max_num_pos=a;
}

if(max_num_pos==i-1)
//It's where it need to be, skip
continue;


//Get the found max number to the beginning of the list (unless it already is)
if(max_num_pos)
{
moves++;
do_flip(list, length, max_num_pos+1);
}


//And then move it to the end of the range we're working with (pos(0) to pos(i))
moves++;
do_flip(list, length, i);

//Then everything above list[i-1] is sorted and don't need to be touched

}

return moves;
}

void do_flip(int *list, int length, int num)
{
int swap;
int i=0;
for(i;i<--num;i++) { swap=list[i]; list[i]=list[num]; list[num]=swap; } } int main(int argc, char **argv) { //Just need some random numbers. I chose <100 int list[9]; int i; srand(time(NULL)); for(i=0;i<9;i++) list[i]=rand()%100; //Print list, run code and print it again displaying number of moves printf("\nOriginal: "); print_array(list, 9); int moves = pancake_sort(list, 9, 1); printf("\nSorted: "); print_array(list, 9); printf(" - with a total of %d moves\n", moves); } //Java Working Code class PancakeSort { int[] heap; public String toString() { String info = ""; for (int x: heap) info += x + " "; return info; } public void flip(int n) { for (int i = 0; i < (n+1) / 2; ++i) { int tmp = heap[i]; heap[i] = heap[n-i]; heap[n-i] = tmp; } System.out.println("flip(0.." + n + "): " + toString()); } public int[] minmax(int n) { int xm, xM; xm = xM = heap[0]; int posm = 0, posM = 0; for (int i = 1; i < n; ++i) { if (heap[i] < xm) { xm = heap[i]; posm = i; } else if (heap[i] > xM) {
xM = heap[i];
posM = i;
}
}
return new int[] {posm, posM};
}

public void sort(int n, int dir)
{
if (n == 0) return;

int[] mM = minmax(n);
int bestXPos = mM[dir];
int altXPos = mM[1-dir];

boolean flipped = false;

if (bestXPos == n-1)
{
--n;
}
else if (bestXPos == 0)
{
flip(n-1);
--n;
}
else if (altXPos == n-1)
{
dir = 1-dir;
--n;
flipped = true;

}
else
{
flip(bestXPos);
}
sort(n, dir);

if (flipped)
{
flip(n);
}

}

PancakeSort(int[] numbers)
{
heap = numbers;
sort(numbers.length, 1);
}

public static void main(String[] args) {
int[] numbers = new int[]{5,2,3,1,4,7,6};


PancakeSort pancakes = new PancakeSort(numbers);
System.out.println(pancakes);
}
}

TC O(nlogn) See Analysis Below
SC O(1)
Run Here https://ideone.com/CoQfM



Complexity analysis:
Step 1 can be done in O(n) time. Using 2 indices to locate boundaries of runs and an O(1) reverse call, this is easy to achieve.
Step 2 The merge procedure requires 2 get() operations (one of which may be optimized away with careful coding) and (in the worst case) 2 reverse(i,j) operations. Therefore, the cost of putting 1 element in its correct position is O(1). Hence 2 sequences of lengths n and m can be merged in O(min{n, m}) swaps and O(max{n, m}) time.

Overall complexity:
Let us assume that we end up with K runs of lengths L1 - Lk from step 1. Cost of this step O(N)
Cost of merging adjacent runs = O(min{Li, Li+1}) (in terms of swaps), O(max{Li, Lj}) in terms of comparisons.
Total number of merges that will take place = K

The worst case for the problem will occur when all the arguments to min{ Li, Lj } are the same. This happens when the runs are of size N/K.
Therefore, cost of merge = O( N/K ) swaps (rather reverse(i,j) calls) and total number of merges = K. Hence overall swaps complexity is O( K * N/K ) = O( N ). However, overall comparison complexity remains O(N log N). So using the reverse operation, we've be able to optimize the number of swaps. However, we cannot breach the lower bound of Omega(n log n) for the number of comparisons required for sorting as this is a comparison based sort.

More Info http://mypages.valdosta.edu/dgibson/courses/cs3410/notes/ch08.pdf