Tuesday 17 November 2015

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 int pancakeSort(int array[]) {

           int n = array.length;
           /** */
           for (int unsortASize=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 int findMax(int array[], int n) {
           int idxMax = 0;
           for (int i = 0; i < n; ++i) {
                if (array[i] > array[idxMax]) {
                     idxMax = i;
                }
           }
           return idxMax;
     }

     /**
      * Reverses array[0..idx].
      **/
     static void flip(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 void printArray(int arr[]) {
           StringBuilder sb = new StringBuilder();
           for (int element : 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

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...