In this blog post, we are going to show you how to implement the Pancake Sorting algorithm, which is Bill Gates’ favorite one.
Wikipedia: “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 minimum number of flips required for a given number of pancakes.
In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on the bottom.
All sorting methods require pairs of elements to be compared. For the traditional sorting problem, the usual problem studied is to minimize the number of comparisons required to sort a list. The number of actual operations, such as swapping two elements, is then irrelevant.
For pancake sorting problems, in contrast, the aim is to minimize the number of operations, where the only allowed operations are reversals of the elements of some prefix of the sequence. Now, the number of comparisons is irrelevant.”
This problem is notable as the topic of the only well-known mathematics paper by Microsoft founder Bill Gates, entitled “Bounds for Sorting by Prefix Reversal”.
This is not a traditional theme for our articles, but since many of you liked our article about Top 16 Books That Made Elon Musk a Genius, we’ve decided to write one about Bill Gates.
The founder of Microsoft is very popular in the IT community as well as the general life since his company has one of the most used operating systems (Windows) and many other products.
Bill Gates is a hero for many of us, so we’ve decided to show you how to implement his favorite sorting problem using Python programming language.
The Pancake Sorting algorithm
GeeksForGeeks: “Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible.
The idea is to do something similar to Selection Sort. We one by one place maximum element at the end and reduce the size of the current array by one.”
Let given array be array and size of the array be n.
Start from current size equal to n and reduce the current size by one while it’s greater than 1. Let the current size be curr_size.
Do following for every curr_size:
- Find index of the maximum element in array[0..curr_size-1]. Let the index be ‘max_index’
- Call flip(array, max_index)
- Call flip(array, curr_size-1)
Following this logic, we are going to implement the code for the Pancake Sorting algorithm.
If this is not enough explanatory, we will suggest you take a look at these YouTube videos:
Pancake sort algorithm, visualization with VTK:
Pancake sorting algorithm:
Google Coding Question – Pancake Sorting (Leetcode 969):
As we’ve said, this article is not our traditional type of article, but we thought that you might find it helpful and interesting since it is a sorting problem. Also, if you are new to algorithms, it will be an interesting type of challenge and maybe a school or university project for you.
If you are new to Machine Learning, Deep Learning, Computer Vision, Data Science or just Artificial Intelligence, in general, we will suggest you some of our other articles that you might find helpful, like:
- FREE Computer Science Curriculum From The Best Universities and Companies In The World
- How To Become a Certified Data Scientist at Harvard University for FREE
- How to Gain a Computer Science Education from MIT University for FREE
- Top 10 Best FREE Artificial Intelligence Courses from Harvard, MIT, and Stanford
- Top 10 Best Artificial Intelligence YouTube Channels in 2020
The materials for this article are available at:
If you want to check out the history of how Bill Gates wrote his paper where he was working on the Pancake sorting problem then click on this National Public Radio: Before Microsoft, Gates Solved A Pancake Problem link.
Like with every post we do, we encourage you to continue learning, trying, and creating.