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