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
No comments:
Post a Comment