Pancake sort algorithm, visualization with VTK

Pancake sorting ( http://en.wikipedia.org/wiki/Pancake_sort ) is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the least comparisons possible, the goal is to sort the sequence in as few reversals as possible. This operation can be visualized by thinking of a stack of pancakes in which one is allowed to take the top k pancakes and flip them.

Here we perform the visualization of a simple pancake sorting algorithm with VTK. The algorithm starts by flipping the top pancakes from the largest one to the top, so that the largest pancake goes to the top. Then, sorting the whole pancake stack we bring the largest pancake to the bottom. The subsequent move brings the second largest to the second position, and so on, recursively.

The VTK Python script is available here: http://www.cimec.org.ar/twiki/bin/view/Cimec/SomeVTKExamples

Category:

Science & Technology

Tags:

• vtk
• python
• pancake
• sorting
• algorithm

[yugpud]

Good illustration of the technique, but moves 9 and 10 were unnecessary, and at move 14, the stack is sorted. I guess your algorithm here simply repeats a sequence 2n times (for n pancakes) without checking for completion or redundancy. Tsk tsk!

[mariostorti]

Yes, you are right. In fact I programmed this with the simplest algorithm I found, as an example of programming with VTK-Python, rather than looking for the better algorithm.

[hydroslf]

epic background music!! :D