Pancake Sorting Algorithm

We are given a stack of n pancakes, each of different size. The goal is to sort this stack from smallest to largest (largest being on the bottom of the stack). The only thing we are allowed to do is to insert the spatula in between two pancakes (or between the bottom pancake and the plate), and flip over all the pancakes that are on top of the spatula.

Intuitive Algorithm

Given arr = unsorted array with the size of n.

1. Find the hn = highest number out of order pancake that is not yet sorted.
2. Flip up the starting index (arr[0]) up to the index of the largest number (indexOf[hn]) found.
3. Flip down the array with the size of the unsorted array or arr.
4. Decrease the size of the unsorted array to 1, n = n - 1 (since we already placed the highest number to the last, it is already sorted).
5. Repeat the process until the stack is ordered.

Implementation Visualization

Click the visualizer below to start

Complexity

Time Complexity - O(n²) - time increases proportion to the number of items.
Space Complexity - O(1) - an extra list is not needed to hold the result of the function.

Strength

• Algorithm is Straight forward - easy to implement and understand.
• Does not need extra memory, sorts in place.

Weakness

The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small. It does not deal well with a list containing a huge number of items.

Cocktail Sorting Algorithm

Cocktail Sort is a variation of Bubble sort. The Bubble sort algorithm always traverses elements from left and moves the largest element to its correct position in first iteration and second largest in second iteration and so on. Cocktail Sort traverses through a given array in both directions alternatively.

Algorithm

Each iteration of the algorithm is broken up into 2 steps:

1. First Pass
1. Loop through the array starting from beginning of the unsorted array until the end of the unsorted array.
2. Use Bubble Sort - compare adjacent items from left to right
   • If the value on the right is lower than the left, swap.
   • Else - Do nothing.
   • Continue to next items, until the largest value is at the end of the array.
2. Second Pass
1. Loop through the array starting from the index before the last sorted value.
2. Compare adjacent items from right to left
• If the value on the left is greater than the right, swap.
• Else - Do nothing.
• Continue to next items, until the smallest value is at the end of the array.

• Repeat until there is no available items to swap. This indicates that the array is already sorted.

Implementation Visualization

Click the visualizer below to start

Complexity

Time Complexity

• Worst and Average Case Time Complexity: O(2n*n) or -> O(n²). - O(2n*n) because it contains two consecutive loops, for first pass and second pass, removed the constant, thus O(n²).
• Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

Space Complexity - O(1) - an extra list is not needed to hold the result of the function.

Strength

• The algorithm has the same complexity class of Bubble Sort: O(n^2), but it tends to be faster by a factor of 2.
• As the cocktail sort goes bidirectionally, the range of possible swaps, which is the range to be tested, will reduce per pass, thus reducing the overall running time slightly.
• Elements are swapped in place without using additional temporary storage.

Weakness

The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small. It does not deal well with a list containing a huge number of items.

Flash Sorting Algorithm

Flashsort is an efficient in-place implementation of historgram sort, itself a type of bucket sort. It assigns each of the n input elements to one of m buckets, efficiently rearranges the input to place the buckets in the correct order, then sorts each bucket.

Algorithm

1. Find the minimum and maximum value in the array.
2. Linearly divide the range [min, max] into m buckets.
3. Start with the first element, move it into its correct position, takes the element that used to be at that place and move it into its correct position and so on.
4. The elements are now near-sorted however since the distribution of the elements is not always perfectly even our estimates of where the elements go may be off by a bit. To solve this we finish up the algorithm with a classical insertion sort in order to correct the minor mistakes.

Implementation Visualization

Click the visualizer below to start

Complexity

Time Complexity - O(4 * n) or O(n), each step takes O(n), insertion sort performs on best case scenario O(n) because the elements are near-sorted.
Space Complexity - O(~~(0.45 * n)) or O(n) - for the buffer or "buckets" used to store temporary values.

Strength

• Flash sorting algorithm is very effective in large arrays with uniformly distributed data.
• It becomes twice as fast as quicksort with relatively large amount of data.

Weakness

Requires little additional memory requirement for the buckets.

---

References

• http://www.cs.cmu.edu/~arielpro/15251f17/notes/pancakes-notes.pdf
• https://leetcode.com/problems/pancake-sorting/
• https://www.geeksforgeeks.org/cocktail-sort/
• https://steemit.com/popularscience/@krishtopa/the-fastest-sort-method-flashsort