package com.interview.sort;

/**
 * http://www.geeksforgeeks.org/pancake-sorting/
 */
public class PanCakeSorting {

    public void sort(int arr[]){
        for(int i=arr.length-1; i >= 0 ; i--){
            int pos = findMax(arr,i);
            flip(arr,pos);
            flip(arr,i);
        }
    }
    
    private int findMax(int arr[],int pos){
        int max = pos;
        for(int i= pos-1 ;i >= 0 ;i--){
            if(arr[i] > arr[max]){
                max = i;
            }
        }
        return max;
    }
    
    private void flip(int arr[],int pos){
        for(int i=0; i <= pos/2; i++){
            swap(arr,i,pos-i);
        }
    }
    
    private void swap(int arr[],int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String args[]){
        int arr[] = {9,2,7,11,3,6,1,10,8};
        PanCakeSorting pcs = new PanCakeSorting();
        pcs.sort(arr);
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }
}

@@ -75,16 +75,553 @@
 orting/%0A
+ * Two ways to do it%0A * 1) Start i from arr.length-1 towards 0, find max from 0 to i, move this max to top%0A * by one flip and then move this max to ith position by another flip%0A * %0A * 2) Start i from 0 towards arr.length-1, find floor of input%5Bi%5D from 0 to i-1 lets call%0A * f , flip 0 to f, then flip 0 to i-1 then flip 0 to i, then flip 0 to i-1.%0A * e.g 1 2 3 5 4. Here i is 4 and f is 2%0A * 1 2 3 5 4 flip(0,f) -%3E 3 2 1 5 4%0A * 3 2 1 5 4 flip(0,i-1) -%3E 5 1 2 3 4%0A * 5 1 2 3 4 flip(0,i) -%3E 4 3 2 1 5%0A * 4 3 2 1 5 flip(0,i-1) -%3E 1 2 3 4 5%0A
  */%0Apubl

Add more comments for pancake sorting