Sign in to YouTube
Sign in to YouTube
Sign in to YouTube
Uploaded on Apr 3, 2009
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.
Standard YouTube License
- 1:04 The Algorithm Scene HD - The Social Network - Eduardo Saverin Facemashby ViralFutureFeatured 173,219
- 1:20:36 Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005by MIT 436,052 views
- 1:16:50 Lec 5 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005by MIT 49,291 views
- 53:30 Lec 1 | MIT 6.00 Introduction to Computer Science and Programming, Fall 2008by MIT 1,411,547 views
- 1:08:33 Lec 3 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005by MIT 72,545 views
- 52 videos Play all Sorting algorithms visualised with dance and soundby kjwieringa67
- 0:27 Animation of a binary tree in Javaby 2k1ppp 30,268 views
- 53:31 Lecture - 1 Introduction to Data Structures and Algorithmsby nptelhrd 492,461 views
- 4:06 Sorting: Ep 02 - Selection Sortby lcc0612 21,644 views
- 3:51 Algorithms Lesson 8: Selection Sortby xoaxdotnet 48,139 views
- 0:35 The Sound of Quicksortby account1011011 45,235 views
- 15:23 Kevin Slavin: How algorithms shape our worldby TEDtalksDirector 347,315 views
- 0:30 Comparison of bubble sort and quicksort algorithms. VTK Python programming exampleby Mario Storti 24,586 views
- 2:56 Heap Sortby Shishberg 65,250 views
- 1:28 Merge sort visualization (2500 elements)by account1011011 29,841 views
- EducatorVids3 736 videos11K
- 48:13 Lecture 1: Introduction to Data Structures and Algorithms - Richard Bucklandby UNSWelearning 124,179 views
- 6:48 Algorithms Lesson 6: Big O, Big Omega, and Big Theta Notationby xoaxdotnet 127,061 views
- 0:56 insertion sort - english subtitlesby Eduardo Corazzin 24,859 views
- 4:17 Merge-sort with Transylvanian-saxon (German) folk danceby AlgoRythmics 122,032 views
- 3:15 Algorithms #2 - Insertion Sortby Alister Christie 59,314 views
- 4:04 Insert-sort with Romanian folk danceby AlgoRythmics 207,837 views
- Loading more suggestions...