Sorting Algorithms

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.

• Category

  Science & Technology

[April Park]

What's the music at the end, btw?

[mrtheta]

It's the rag "The Entertainer", by Scott Joplin.

[barrikid]

You better apologize for bubble sort! =D

[MORIARTY PARK]

Very impressive presentation!!

[mrinal saha]

no one explain better than this

[rockskaterdudeperson]

was that Obama talkin about the bubble sort()?

[pallearn]

thank u

[marcelo coelho]

Cool, thanks for the demo.

[sev548]

This is very good

[xXsnakeMASTER420Xx]

What about bogosort?

[bastiaan08]

Bubble sort doesn't need to walk the entire array over an over. The last item is always highest or lowest value depending on your sort. So every time you start to walk over the array you can stop 1 item earlier. Then you can look how many items aren't swapped before you reached the end, you can even stop before these items the next walk. When no item is swapped at all everything is sorted. Now it would only take 5 years because now the list went from 225 iterations back to 75 this way :D

[Nader Gerges]

This is a VERY well done description of all the types of sorting algorithms!!! Well done!!