Sorting

Sorting Algorithms

• Report rights infringement
• published: 04 Apr 2009
• views: 112310

This video illustrates how several simple sorting algorithms operate, using people as the objects to be sorted. Produced by the Algorithmic Thinking class as part of Knight School 2009 at Menlo School. For people who know nothing about computer science but want to know what the heck is going on, here are brief descriptions of each sorting algorithm. Insertion Sort: Select each element in the list, and move it left until you hit somebody less than it. For example, when the element '2' is selected in the video, it moves left (shifting everybody right out of the way) until it encounters '1', when it is inserted back into the list. Selection Sort: Pass through the entire list, keeping track of the minimum element so far seen. When the pass is finished, select the global minimum and (in this simplified version of the algorithm) add it to a list of sorted elements. Repeat this, selecting the minimum element each time. Mergesort: Sorting a big list is too hard, so instead sort the first and last halves of the list, and then merge the sorted sublists. Of course, to sort each half-list we sort each quarter-list, and so forth. Eventually we get down to sorting a list with only two elements, which is easy! The merge can also be done very easily, by simply taking the smaller of the top elements of each sublist and repeating until the sublists are empty. In the video, the splitting of the original list into halves, quarters, etc. is not shown - for simplicity we start by immediately sorting all sublists of length two (bottom-up mergesort). Bubblesort: Begin at the end of the list, comparing the last two elements. If they are out of order, swap them. Repeat moving up the list, swapping elements if necessary. When the beginning of the list is reached, start again from the end. When no swaps are made during an entire pass, the list is sorted. Note that this is the simplest version of bubblesort - it can be improved somewhat, becoming more like insertion sort (it is still a terrible way to sort). As a final note, the O(n^2) and O(n log n) written underneath the name of each algorithm is a way of saying how fast they are. O(n^2) means that if you feed the algorithm twice as much stuff to sort, it takes four times as long to do it - the time is proportional to the square of the input size. O(n log n) means the time is proportional to the size multiplied by the logarithm (any base) of the size. All the algorithms in the video except mergesort are O(n^2) in the worst case, meaning they are not practical algorithms except in special (but very important) circumstances. Mergesort, on the other hand, is a very widely used, dependable algorithm.