Interview Questions

Pancake Sorting

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

Unlike 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.

package com.test;

public class PancakeTest{
       
        public static void main(String[] args){
               
                int[]  arr = {102, 77,5,4,1,2,3,8,9};
               
                // 1 2 3 5 4 7 6
                // 4 5 3 2 1 7 6
                // 5 4 3 2 1 7 6
                // 1 2 3 4 5 7 6
                // 6 7 5 4 3 2 1
                // 7 6 5 4 3 2 1
                // 1 2 3 4 5 6 7
               
                // 4 1 3 5 2
                // 1 4 3 5 2
                // 3 4 1 5 2
                // 4 3 1 5 2
                // 1 3 4 5 2
                // 2 5 4 3 1
                // 5 2 4 3 1
                // 1 3 4 2 5
                // 2 4 3 1 5
                // 4 2 3 1 5
                // 1 3 2 4 5
                // 2 3 1 4 5
                // 3 2 1 4 5
                // 1 2 3 4 5
                //arr = flip(arr,3);
                boolean pass = true;
                while(true){
                pass=true;
                for(int i=0;i<arr.length;i++){
                       
                                if(i+1<arr.length && arr[i]>arr[i+1]){
                                        arr = flip(arr,i+2);
                                        if(i+2>2){
                                                arr = flip(arr,2);
                                                arr = flip(arr,i+2);
                                        }
                                        pass=false;
                                        break;
                                }
                        }
                if(pass==true)
                        break;
                }
               
                for(int i=0;i<arr.length;i++){
                        System.out.println(arr[i]);
                }
               
        }

       
        public static int[] flip(int[] arr,int k){
               
                int[] temp = new int[arr.length];
               
                for(int i=k-1,j=0;i>=0;i--,j++)
                        temp[j]=arr[i];
               
                for(int m=k;m<arr.length;m++)
                        temp[m]=arr[m];
               
                return temp;
        }
}