## 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

#### 1 comment:

1. Amazing Article, thank you!. I am very glad to read your informative & practical blog. Kindly keep updating your blog. Java Developer is a wonderful career for IT students.To start Dream Career to become a Java developer learn from Java Training in Chennai. or learn thru Java Online Training from India .