Pancake sort in java

Pancake sort:

Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it.

A pancake number is the maximum number of flips required for a given number of pancakes.

flip(array, i): Reverse array from 0 to i.

Pseudo code Pancake sort:

1) iMax = Index of Largest element in unsorted array.

Find index of the maximum element index in arr[0..unsorted_array_size -1].

2) Call flip(array, iMax)

It will flip all element of array from 0 to iMax index.

The largest element will be the first element in the array.

3) Call flip(array, unsorted_array_size -1)

Flip complete unsorted array which result to put the largest element at the end of the unsorted array.

Complexity :

Total O(n) flip operations are performed in where each flip will take O(n) time. Therefore complexity is O(n^2).

Example

19

23

6

15

45

30

14

1. Find Max element index from 0 to N-1

iMax = 4

19

23

6

15

45

30

14

2. flip(0,iMax)

45

15

6

23

19

30

14

3. flip(0,N-1)

14

30

19

23

6

15

45

Repeat Step #1 to Step #3:

1. Find Max element index from 0 to N-2

iMax = 1

14

30

19

23

6

15

45

2. flip(0,iMax)

30

14

19

23

6

15

45

3. flip(0,N-2)

15

6

23

19

14

30

45

class PancakeSort {

     /**Perform Pancake sort. */

     static intpancakeSort(int array[]) {

           int n = array.length;

           /** */

           for (intunsortASize=n; unsortASize>1;--unsortASize) {

                /**

                 * Find index of the maximum element

                 * in arr[0.. unsortArrSize-1]

                 * */

                int idxMax = findMax(array,unsortASize);

               

                /**

                 * Move the maximum element to end of current

                 * array if it's not already at the end*

                 */

                if (idxMax != unsortASize-1) {

                    

                     /**flip will put the max element to beginning.*/

                     flip(array, idxMax);

                     /**

                      * flip will put the max element in the last

                      * of unsorted array.

                      **/

                     flip(array, unsortASize-1);

                }

           }

           return 0;

     }

     /**

      * Returns index of maximum element in unsorted array.

      **/

     static intfindMax(int array[], int n) {

           int idxMax = 0;

           for (inti = 0; i < n; ++i) {

                if (array[i] > array[idxMax]) {

                     idxMax = i;

                }

           }

           return idxMax;

     }

     /**

      * Reverses array[0..idx].

      **/

     static voidflip(int array[], int idx) {

           int temp, start = 0;

           while (start < idx) {

                temp = array[start];

                array[start] = array[idx];

                array[idx] = temp;

                start++;

                idx--;

           }

     }

     /** Utility function: print array*/

     static voidprintArray(int arr[]) {

           StringBuilder sb = newStringBuilder();

           for (intelement : arr) {

                sb.append(element).append(" ");

           }

           System.out.println(sb.toString());

     }

     /** Test Pancake sort. */

     public static void main (String[] args) {

           int array[] = {23, 10, 20, 11, 12, 6, 7};

          

           System.out.println("Unsorted Array: ");

           printArray(array);

          

           PancakeSort.pancakeSort(array);

          

           System.out.println("Sorted Array: ");

           printArray(array);

     }

}

Output:

     Unsorted Array:

     23 10 20 11 12 6 7

     Sorted Array:

     6 7 10 11 12 20 23