Monday, August 8, 2011

The Beauty of Sort Algorithms



Algorithms much like Mathematical equations can be visualized to produce quite beautiful results.
The following artistic display of the various sort algorithms is simply remarkable if not genius.
Kudos to the Sapientia University in Transylvania, Romania for this beautiful production.
So if you are not yet familiar with the various sort algorithms, just follow closely each dance.

The beauty of sort algorithms starts with the fact that they take a simple action and repeat it recursively until the values are sorted.
They usually differ in the time it takes them to sort the values.

Quick Sort
This is the most amusing one.
A Hungarian style dance.
The Hungarian call that you hear in this video "Oszd meg és uralkodj" means "Divide and Conquer".
And indeed “divide and conquer” is the essence of this algorithm.
Quicksort is accomplished by the following algorithm:
1. Choose a cell in the list – the Pivot cell. In this case the first (it can be any other)

2. Compare the pivot cell to all other cells in the list and order the pivot accordingly.
So if a cell is smaller than the pivot it will be on the right side and if the cell is bigger than the pivot it will be on the left side. If their relative position does not correspond to their values then switch between them.
By comparing the selected cell (the Pivot) to each other cell you eventually divide the list into two smaller lists where the pivot cell is actually located in its final location.
The two remaining lists are of all the values that are lower than the pivot and all the values that are higher than the pivot.

3. Continue with the same process above to each of the divided lists, until your reach a list of a single cell.




Selection Sort
This is the next amusing and much colorful one.
A Gypsy style dance.

Selection Sort is accomplished by the following algorithm:
1. From the start of the list scan to find the minimal value in the list and place it at the first cell of the list.
This is done by comparing the first cell to the second cell and if that cell is smaller, switch between them and compare the new (smaller) first cell to the third cell and so on.

2. Repeat the procedure from the top where the new list starts from the next cell.

This algorithm is the slowest one this is why the video was speeded up.



Insert Sort
A Romanian style dance.

The insert algorithm simply creates a sorted list within the original one by inserting every next cell one by one in its correct location.
1. The first cell is already a sorted list.

2. We take the next cell and insert it to the sorted list to its left in the correct location (by comparing it to the existing cells)

3. We repeat step 2 until we reach the end of the list.



Merge Sort
Here the call of "Divide and Conquer" is in German: "Teile und herrsche"

The merge sort algorithm is quite clever.
The idea is simple:
1. Break the list into two equal halves (of course when there is an odd number of cells one will be a bit bigger).

2. Sort (by Merge sort) each half of the list.

3. Merge the two sorted lists into one list.
The rule of course is that when reaching a list of a single cell it is regarded as already sorted.



Bubble Sort
A Hungarian style dance.

Bubble sort is very simple. We simply scan the list by comparing every two adjacent cells and swap between them if their order does not match the expected order of the list.

The scan is repeated until no swaps are required, meaning the list is sorted.




Shell Sort
A Hungarian style dance.