Sort Your Heart Out

  Sorting is a fundamental issue for computer scientists. Given a list of unordered objects and a way to compare them, what is the best way to sort them into a logical order? There are many different answers to this question out there, each ranging in simplicity and efficiency. The Sapientia University of Romania took a few of the most simple sorting algorithms and showed how they work in a fairly novel way, through the magic of dance. Using a local Central European folk dance team and a folk band, the team is able to show off some of the more simple sorting algorithms in a little livelier fashion that most demonstrations of sorting.
  The first and simplest of sorts is the bubble sort. Bubble sort starts at the beginning of the list and compares the first two objects. It does nothing if those two objects are in the correct order or swaps them if they are not. The algorithm then compares the second and third elements in the list, swapping when necessary and forcing the higher number up the list, "bubbling" it towards where it needs to go. This iteration continues until the sort reaches the end of the list where it goes back to the beginning, starting the sort all over again. This is repeated until an entire pass across the list has no swaps. The algorithm is complete and ceases operation.

  Insertion sort is another simple algorithm. Starting at the beginning of the list, the algorithm "separates" the first element into what is considered a sorted list, where by itself, the element is sorted. It then takes the next element in the list and places it into the correct location inside the sorted list. This continues down the list of objects until a fully sorted list is produced.

  Akin to the bubble sort and insertion sort, shell sort compares two elements half the size of the list together and swaps if needed. If the elements were swapped, then the gap is used again to compare the elements before to check for needed swaps. After comparing all elements with this gap, it once again iterates over the list using a smaller gap and continues until the list is sorted, the final iteration through the list being exactly like insertion sort.

  Selection sort takes a slightly different approach, only swapping when it knows it has the correct value for that position in the list. The algorithm iterates over the entire list to find the lowest value in the list, then swaps that value with whatever element is in the first position of the list. The algorithm then repeats the process with the next lowest value in the list, placing it in the second position in the list. The process is continued until the list is sorted.