What is Pancake Sort
Pancake sorting is a sorting algorithm that works by flipping pancakes. Imagine you have a stack of pancakes with different sizes, and you want to sort them from smallest to largest. To do this, you can use a spatula to flip the pancakes over onto a plate, one at a time.
In pancake sorting, you start by looking at the top pancake in the stack, and you figure out where it should go in the sorted stack. Then, you use the spatula to flip the stack of pancakes over at that point, so that the top pancake is now in the correct position.
You repeat this process with the remaining pancakes, one at a time, until the whole stack is sorted.
The key to making this process efficient is to identify the largest pancake that is out of place and flip the stack at that point, so that the largest pancake ends up on the bottom of the stack. Then, you repeat the process with the remaining pancakes, but excluding the largest one, until the whole stack is sorted.
Pancake sorting can be a bit tricky to implement, but it's an interesting and fun way to think about sorting algorithms.
Who invented it?
The Pancake sorting algorithm was first proposed by American mathematician and computer scientist Bill Gates Sr. (not to be confused with his more famous son, Microsoft co-founder Bill Gates). In 1979, Gates Sr. published a paper called "Bounds for Sorting by Prefix Reversal," in which he described the Pancake sorting algorithm and proved that it has a worst-case time complexity of O(n^2), where n is the number of pancakes in the stack. Since then, Pancake sorting has become a well-known example of a sorting algorithm with an unconventional approach.
Pseudocode
pancake_sort(A):
for i from n downto 1:
# Find the index of the largest element in the unsorted portion of the array
max_index = find_max(A, i)
# If the largest element is already at the end of the unsorted portion, move on to the next iteration
if max_index == i:
continue
# Flip the unsorted portion of the array up to the largest element
flip(A, max_index)
# Flip the entire unsorted portion of the array to move the largest element to the end of the unsorted portion
flip(A, i)
return A
# Helper function to find the index of the largest element in an array up to a given index
find_max(A, end_index):
max_index = 0
for i from 0 to end_index:
if A[i] > A[max_index]:
max_index = i
return max_index
# Helper function to flip the elements in an array up to a given index
flip(A, end_index):
start_index = 0
while start_index < end_index:
A[start_index], A[end_index] = A[end_index], A[start_index]
start_index += 1
end_index -= 1
The `pancake_sort` function takes an array `A` of pancakes to be sorted and returns the sorted array. The algorithm sorts the pancakes by repeatedly flipping portions of the array using the `flip` function, until the entire array is sorted.
The outer loop of the algorithm iterates over each element in the array in reverse order, from the last element to the first. In each iteration, the algorithm uses the `find_max` function to find the index of the largest element in the unsorted portion of the array up to the current index.
If the largest element is already at the end of the unsorted portion, the algorithm skips to the next iteration. Otherwise, it uses the `flip` function twice to move the largest element to the end of the unsorted portion of the array.
The `flip` function takes two indices as input and flips the elements in the array between those indices in place. The `find_max` function takes an array and an end index as input, and returns the index of the largest element in the array up to the given index.
Overall, the Pancake sorting algorithm has a worst-case time complexity of O(n^2), where n is the number of pancakes in the input array.
The outer loop of the algorithm iterates over each element in the array in reverse order, from the last element to the first. In each iteration, the algorithm uses the `find_max` function to find the index of the largest element in the unsorted portion of the array up to the current index.
If the largest element is already at the end of the unsorted portion, the algorithm skips to the next iteration. Otherwise, it uses the `flip` function twice to move the largest element to the end of the unsorted portion of the array.
The `flip` function takes two indices as input and flips the elements in the array between those indices in place. The `find_max` function takes an array and an end index as input, and returns the index of the largest element in the array up to the given index.
Overall, the Pancake sorting algorithm has a worst-case time complexity of O(n^2), where n is the number of pancakes in the input array.
Sample Code
// C++ code snippet
// Function to flip a portion of a vector between two indices
void flip(vector& v, int end_index) {
int start_index = 0;
while (start_index < end_index) {
// Swap the elements at the start and end indices
int temp = v[start_index];
v[start_index] = v[end_index];
v[end_index] = temp;
// Move the start and end indices closer to each other
start_index++;
end_index--;
}
}
// Function to find the index of the maximum element in a vector up to a given index
int find_max_index(vector& v, int end_index) {
int max_index = 0;
for (int i = 1; i <= end_index; i++) {
if (v[i] > v[max_index]) {
max_index = i;
}
}
return max_index;
}
// Function to perform Pancake sorting on a vector
void pancake_sort(vector& v) {
int n = v.size();
// Iterate over each element in the vector in reverse order
for (int i = n - 1; i > 0; i--) {
// Find the index of the maximum element in the unsorted portion of the vector
int max_index = find_max_index(v, i);
// If the maximum element is already at the end of the unsorted portion, move on to the next iteration
if (max_index == i) {
continue;
}
// Flip the portion of the vector up to the maximum element
flip(v, max_index);
// Flip the entire unsorted portion of the vector to move the maximum element to the end of the unsorted portion
flip(v, i);
}
}
// Function to print the elements of a vector
void print_vector(vector& v) {
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
int main() {
// Create a vector of integers to be sorted
vector v = {5, 2, 3, 8, 6, 4, 1, 7};
// Print the unsorted vector
cout << "Unsorted vector: ";
print_vector(v);
// Sort the vector using Pancake sorting
pancake_sort(v);
// Print the sorted vector
cout << "Sorted vector: ";
print_vector(v);
return 0;
}
# Python code snippet
# Function to flip a portion of a list between two indices
def flip(lst, end_index):
"""
The flip function takes a list and an end index as input,
and flips the elements in the list between the start index
and the end index in place.
"""
start_index = 0
while start_index < end_index:
# Swap the elements at the start and end indices
temp = lst[start_index]
lst[start_index] = lst[end_index]
lst[end_index] = temp
# Move the start and end indices closer to each other
start_index += 1
end_index -= 1
# Function to find the index of the maximum element in a list up to a given index
def find_max_index(lst, end_index):
"""
The find_max_index function takes a list and an end index as input,
and returns the index of the maximum element in the list up to the
given index.
"""
max_index = 0
for i in range(1, end_index + 1):
if lst[i] > lst[max_index]:
max_index = i
return max_index
# Function to perform Pancake sorting on a list
def pancake_sort(lst):
"""
The pancake_sort function takes a list as input and sorts it using
the Pancake sorting algorithm, which iterates over each element in
the list in reverse order, finds the index of the maximum element
in the unsorted portion of the list up to the current index, and
flips the portion of the list up to the maximum element and the
entire unsorted portion of the list to move the maximum element to
the end of the unsorted portion.
"""
n = len(lst)
# Iterate over each element in the list in reverse order
for i in range(n - 1, 0, -1):
# Find the index of the maximum element in the unsorted portion of the list
max_index = find_max_index(lst, i)
# If the maximum element is already at the end of the unsorted portion, move on to the next iteration
if max_index == i:
continue
# Flip the portion of the list up to the maximum element
flip(lst, max_index)
# Flip the entire unsorted portion of the list to move the maximum element to the end of the unsorted portion
flip(lst, i)
# Function to print the elements of a list
def print_list(lst):
"""
The print_list function takes a list as input and prints its elements
to the console, separated by spaces.
"""
for i in range(len(lst)):
print(lst[i], end=" ")
print()
# Main function to test the Pancake sorting algorithm
def main():
# Create a list of integers to be sorted
lst = [5, 2, 3, 8, 6, 4, 1, 7]
# Print the unsorted list
print("Unsorted list: ", end="")
print_list(lst)
# Sort the list using Pancake sorting
pancake_sort(lst)
# Print the sorted list
print("Sorted list: ", end="")
print_list(lst)
if __name__ == "__main__":
main()
import java.util.Arrays;
public class PancakeSorting {
// Function to flip a portion of an array between two indices
public static void flip(int[] arr, int endIndex) {
/*
* The flip function takes an array and an end index as input, and flips the
* elements in the array between the start index and the end index in place.
*/
int startIndex = 0;
while (startIndex < endIndex) {
// Swap the elements at the start and end indices
int temp = arr[startIndex];
arr[startIndex] = arr[endIndex];
arr[endIndex] = temp;
// Move the start and end indices closer to each other
startIndex++;
endIndex--;
}
}
// Function to find the index of the maximum element in an array up to a given index
public static int findMaxIndex(int[] arr, int endIndex) {
/*
* The findMaxIndex function takes an array and an end index as input, and returns
* the index of the maximum element in the array up to the given index.
*/
int maxIndex = 0;
for (int i = 1; i <= endIndex; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
// Function to perform Pancake sorting on an array
public static void pancakeSort(int[] arr) {
/*
* The pancakeSort function takes an array as input and sorts it using the Pancake
* sorting algorithm, which iterates over each element in the array in reverse order,
* finds the index of the maximum element in the unsorted portion of the array up to
* the current index, and flips the portion of the array up to the maximum element
* and the entire unsorted portion of the array to move the maximum element to the
* end of the unsorted portion.
*/
int n = arr.length;
// Iterate over each element in the array in reverse order
for (int i = n - 1; i > 0; i--) {
// Find the index of the maximum element in the unsorted portion of the array
int maxIndex = findMaxIndex(arr, i);
// If the maximum element is already at the end of the unsorted portion, move on to the next iteration
if (maxIndex == i) {
continue;
}
// Flip the portion of the array up to the maximum element
flip(arr, maxIndex);
// Flip the entire unsorted portion of the array to move the maximum element to the end of the unsorted portion
flip(arr, i);
}
}
// Function to print the elements of an array
public static void printArray(int[] arr) {
/*
* The printArray function takes an array as input and prints its elements to the console,
* separated by spaces.
*/
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// Main function to test the Pancake sorting algorithm
public static void main(String[] args) {
// Create an array of integers to be sorted
int[] arr = { 5, 2, 3, 8, 6, 4, 1, 7 };
// Print the unsorted array
System.out.print("Unsorted array: ");
System.out.println(Arrays.toString(arr));
// Sort the array using Pancake sorting
pancakeSort(arr);
// Print the sorted array
System.out.print("Sorted array: ");
System.out.println(Arrays.toString(arr));
}