Sorting Secret - Computerphile

The missing technical term: This construction is a sorting network, just drawn in an unusual way. The basic point of the video is that sorting networks can't express the difference between insertion sort and selection sort.

Indeed; Number two pops out the bottom.....

I know some basic definition about all 4 algorithm named insertion sort: find correct place for the element selection sort : find correct element for the place & merge and quick sort uses divide and conquer merge sort doesn't divide it merges properly and quick sort doesn't need to merge it divide properly

It's an interesting exercise that I'm sure will help people visualise these sorting algorithms and understand how they are similar. However to say they are "the same" is pushing it when you're expressly showing that one is operating 'column-wise' and one 'row-wise' in your diagram. The next step here would surely be to get students to dig into this difference and analyse the data structures and operations involved in each approach and the complexity and practical performance implications.

This is a great illustration. I've always thought about how programming is almost like a stream of liquid flowing, and in this you can really visualize that concept.

This is correct on half of a fundamental position....but not on the programming position. Selection sort specifically finds the lowest in the muck, removes it and tags it onto a list; while insertion sort picks a number from the muck and finds the place it needs to be put in the list. This means that selection sort works with any list type, while insertion sort can only effectively work on double-linked lists (otherwise you are constantly moving blocks of memory as the list expands). The other half of the fundamental position that proves that it is NOT the same is simple.....what if halfway through the sort, the program stops? Selection sort would leave some of the data sorted and a leftover muck to deal with, while insertion sort might as well look like 2 mucks. This becomes somewhat important in file systems and indexing....if the power goes out during a sort, Selection is better than Insertion for recovery of "where you left off." It's also important to note that Selection sort gets faster as the muck reduces over time....while Insertion is fastest at the beginning and gets slower over time. Absolutely none of this was mentioned in the video, nor did it seem like Hutton was even going to hint toward it (he stated he was going to write a paper on it being the same, when it obviously isn't when taking as a full context). Sidenote: Any relation to Tim J. Hutton?

This guy is an amazing teacher. I wish I could find his lectures online. We don't have much of that in Brazil.

This video made my day. I was totally burnt, and now I'm in the mood to study on my whiteboard again. Thanks Professor.

One of the best thing I have watched after a long time related to Computer Science. Nice Perspective.

The first one is really bubblesort (the simplest, unoptimized variant). See how beside picking 1 in the first column it also swaps 2 with 3. Selection sort, unlike this bubblesort and insertion sort (also unoptimized because it keeps comparing in the tail after having found the right place for an element), isn't oblivious (which means performing a sequence of comparisons at some pairs of positions depending only on the length of the input, not the results of previous comparisons) and thus cannot be expressed with a sorting network.

The strongest selling point of insertion sort is that it is adaptive. Once the insertion point is determined, the pass can be aborted, while selection sort must look for a min/max across the entire unsorted region. In the vid, he implements an insertion sort that is gimped in its adaptability, and then says its the same as an algorithm that is notoriously not adaptive. Really hammering this point, his machine would take n^2 time to sort a sorted list, just as selection sort would; but insertion sort implemented properly only takes n time. I cant take the engine out of a car, and then comment on how similar it is to a bicycle.

Your videos are excellent. You explain computer science concepts so well. Great job!

Now implement the sort with logic gates.

How did this not make the trending list??? Thank you so much this is what I needed!!!!!

Wait, is he the one who wrote "Programming in Haskell"? Edit: I checked and he is, indeed! Great job, awesome language!

I love the Prof Hutton analogies !!

I didn't care for the point he makes but I really like the "boxes in a triangle" explanation

This video disregards the implementation. Bu the implementation is important. For example, the algorithms have different best case complexity.

i love this channel! i feel lucky i found it xD a lot of interesting stuff put in simple words and explanations.

This is absolutely brilliant.