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

Tags:

• sorting
• algorithms
• algorithmic
• thinking
• knight
• school
• menlo
• insertion
• selection
• sort
• mergesort
• bubblesort

[barrikid]

You better apologize for bubble sort! =D

[MORIARTY2]

Very impressive presentation!!

[Chethan256]

@rsatheesh4utube No, Insertion sort is an inplace sort, it doesn't create a new list. I just keeps given array as two sections, 1) sorted section 2) Unsorted section. As the insertion sort proceeds Section-1 keeps growing and section-2 gradually disappears.

[pyrophobia133]

awww no quicksort or heapsort?

[Hardy123Zhao]

why didn't you do bogosort?

[Babelfish112]

bonus marks for the ragtime music :D

[coderodion]

Further development suggestion: add TimSort presentation to the video. :D

[enoszhang]

1:27

[rsatheesh4utube]

Good one i liked it. But a small clarification , as per my knowledge, insertion sort creates new list by inserting element in sorted order, it does not do swapping but selection sort does swapping. Here its shown in in opposite manner...

[59thbridge]

While I do appreciate your effort, the music, and your hat, I would suggest that for this type of this you do a test run to see what the footage you shoot is going to look like. Can't see anyone's numbers! This is mostly made up for with the numbers edited in after though.

[aaggdd405]

gud one

[omcvideophotography]

Great effort, great coordination, great video.