Pancake sorting is 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.

Unlike traditional sorting algorithms, which attempt to sort with the fewest comparisons, pancake sort tries to sort the sequence in as few reversals as possible.

The idea behind pancake sort is similar to Selection Sort. In every iteration, we find the maximum element in the sequence and place it at the end, and reduce the size of the sequence by one.

Given an array of integers Arr:

• Write a function flip(Arr, i) that reverses the order of the first i elements in the array arr.
• Write a function pancakeSort(Arr) that sorts and returns the input array. You are allowed to use only the function flip in order to make changes in the array.

Algorithm :

Let the given array be Arr[] and size of the array be n

• Start from the current size n and reduce the current size by one while it is greater than one. Let the current size be c. Do the following for every c.
  1. Find the index i of the maximum element in Arr[0....c-1].
  2. Call flip(Arr,i)
  3. Call flip(Arr,c-1)

Array representation of the above diagram :

initial pancake order : [3, 5, 2, 1, 7, 6, 4]

First flip : [3, 5, 2, 1, 7, 6, 4]
after first flip : [7, 1, 2, 5, 3, 6, 4]

Second flip : [7, 1, 2, 5, 3, 6, 4]
after second flip : [4, 6, 3, 5, 2, 1, 7]

Third flip : [4, 6, 3, 5, 2, 1, 7]
after third flip : [6, 4, 3, 5, 2, 1, 7]

Fourth flip : [6, 4, 3, 5, 2, 1, 7]
after fourth flip : [1, 2, 5, 3, 4, 6, 7]

Fifth flip : [1, 2, 5, 3, 4, 6, 7]
after fifth flip : [5, 2, 1, 3, 4, 6, 7]

Sixth flip : [5, 2, 1, 3, 4, 6, 7]
after sixth flip : [4, 3, 1, 2, 5, 6, 7]

Seventh flip : [4, 3, 1, 2, 5, 6, 7]
after seventh flip : [2, 1, 3, 4, 5, 6, 7]

Eight flip : [2, 1, 3, 4, 5, 6, 7]
after eighth flip : [1, 2, 3, 4, 5, 6, 7]

Below, the Python code that implements the algorithm explained:

…and the output:

Each pancake therefore requires two flips, which would give a total of \(2n\) flips required. But the last two pancakes require at most one flip; if they are already in order, no flips are needed, and if they are out of order, only one flip is needed. So this algorithm requires at most \(2(n – 2) + 1 = 2n – 3\) flips in the worst case, which means that \(P_n \leq 2n – 3\).

Mi sono chiesto come mai mi piacciano i libri che mi fanno star male, “Non sarò un po’ masochista?”, mi son chiesto, e mi sono risposto con una cosa che mi è successa mentre scrivevo questo romanzo, nel gennaio del 2020. Ho partecipato alla riunione di una rivista che si chiama “Qualcosa”. L’argomento del numero di “Qualcosa” che stavamo preparando era: le storie sentimentali finite male; i disastri sentimentali, praticamente. Noi, quella sera lì, le venti persone che erano lì, di quei momenti che abbiamo passato tutti, che siam stati male per amore, se così si può dire, di quei giorni così dolorosi che eravamo messi così male che ci sembrava di non esser mai stati tanto male nella nostra vita, e non ci sembrava possibile stare peggio, a ripensarci dopo degli anni, ci veniva da pensare “Ma come son stato male bene, quel giorno lì. Ma che bello, essere così vivi”. Ecco. L’effetto che mi fa leggere (e rileggere) Delitto e castigo, Memorie del sottosuolo, L’idiota, I demoni, Il giocatore, I fratelli Karamazov è quello: mi accorgo di essere vivo, di avere un corpo, di avere il sangue che mi scorre nelle vene. Questo.

— Paolo Nori, Come mai mi piacciono. Novembre 2021

Here the LaTeX code:

and this is the output:

Histogram

Histograms are one of the heavily used plots across functions as it gives a very good view of the distribution of data.

Line

Single line:

Several Lines

How do we add multiple lines in the same chart? Let us take it a bit further to plot multiple lines in the same chart.

Bar Plot

Bar plots are one of the most popular charts used in any type of visualization as it shows the relative data points in an emphasized manner like a line chart.

Scatter Plot