Sorting Secret - Computerphile
Вставка
- Опубліковано 26 чер 2024
- Two different sorting algorithms are actually the same. Professor Graham Hutton explains.
Note from Professor Hutton: It's great to see all the discussions here! To clarify a point raised in some of the comments, the video shows that if you consider the essential underlying idea of selection sort and insertion sort, in terms of how they decompose the problem of sorting, then they perform the same operations but in different orders. Using the picture in the video, selection sort proceeds column at a time and insertion sort proceeds row at a time, but they both perform the same 'triangle' of operations in the end. A particular implementation of these sorting methods may optimise the process in some way, e.g. in a sequential implementation each row can stop comparing numbers once the point of insertion is found. But this is an implementation detail that is dependent on the computational model used, such as sequential versus parallel, or imperative versus functional, rather than part of the essential means by which the sorting methods work.
Slow Loris Attack: • Slow Loris Attack - Co...
Cracking Windows by Atom Bombing: • Cracking Windows by At...
Quantum Computing: • Quantum Computing 'Mag...
Babbage's Analytical Engine: • Babbage's Analytical E...
Quicksort: • Quick Sort - Computerp...
Getting Sorted: • Getting Sorted & Big O...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
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.
Exactly. I tried to point out an example of difference at best-case time. but what you said captures the whole deal.
Ari Rahikkala this is probably the best comment I've seen that clarifies what's in the video. It seems a decent way to visualize and intuitively see how sorting algorithms work, but I don't think it's accurate to draw conclusions of "sameness" based on these diagrams.
Sorry for necro - but I was nearly exploding with frustration at saying that insertion sort is the same thing as selection sort. Sure - they're both sorting stuff. But at that level of abstraction one might as well resign to saying it's "doing computery stuffies".
Not missing: "Sorting network" is introduced at 3:06.
Ivan the space biker ! The right man in the wrong place can make all the difference... in the world.
Indeed; Number two pops out the bottom.....
you went there
best comment on youtube period !
Haha
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.
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.
from a mathematical stand point they are the same.
HOWEVER, because of how memory is managedin a computer(both on write and read) results may vary.
bubble sort also falls in this kind of algorithm
Yep, mwtbones you're correct. Same basic mechanism, but the clocking is different. If this was built in actual hardware, then the clock lines would have to be transposed, rewiring the clock signals between the rows and columns. Still, it's an interesting observation. I wonder if there's a diagonal clocking interpretation?
The sorting is the same... the perspective is not. That is, mechanically they could be opposites (one could be more computational intensive one could be more memory intensive) but they are the "same" when swapped back over to each other.
Or to put it another way: statically they are the same. Once run to completion, they execute exactly the same comparisons on exactly the same input.
Dynamically however they aren't the same because they do so in different order.
This is very similar to the connection between breadth-first traversal vs. depth-first traversal of a tree. They visit exactly the same nodes and the same edges, which hints at some kind of underlying structural connection between the two, but dynamically they're clearly different.
To see the difference between the two algorithms, you only need to remove the "once run to completion" clause. What if we ask for just the three smallest numbers instead of a full sort? Selection sort will obviously behave very differently (and much better) than insertion sort.
Except this is not called Mathematicsphile. Saying they are the same while under the label of Computer oriented information is not truthful to the actual topic when someone goes to implement one over the other thinking they are equivalent.
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
Thank you for sharing these observations!
Deep Joshi Thank you!!!
Bubble sort guarantees the biggest non sorted element goes to the top
This video made my day. I was totally burnt, and now I'm in the mood to study on my whiteboard again. Thanks Professor.
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?
Err, insert sort works well on singly-linked lists as well. You just have to keep two extra references (to the nodes preceding either cursor).
Well the picture actually illustrates the change in sorting speed over time pretty well
Your problems are regarding the "implementation" , the types them self use the same model of steps in this clip here.
Regarding your "power out" problem, you wouldnt write your not completly sorted array to the harddrive, you work with it in your working memory till its sorted if you want to avoid any problem regarding that (and in any scenario where its really important to "finish" the sorting, you would use some kind of transaction that makes sure its finished before its used anywhere else).
----
Implementation problems are indeed important, no question, but this clip here doesnt take that into account, as it focuses on the "model" of the sorting types and compares the step by step approach in the shown visual diagram.
Also, isn't insertion sort much faster on nearly sorted lists?
No, you're not, because you don't have to update pointers to the previous node.
Now implement the sort with logic gates.
It would be a comparator gate 😇
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 disregards the implementation. Bu the implementation is important.
For example, the algorithms have different best case complexity.
One of the best thing I have watched after a long time related to Computer Science. Nice Perspective.
Wait, is he the one who wrote "Programming in Haskell"?
Edit: I checked and he is, indeed! Great job, awesome language!
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.
Insertion sort has O(n^2) like selection Sort. What kind of sort has O(n)? Even QuickSort isn't that fast.
O(n^2) worst case but O(n) best case for insertion. Whereas worst case for selection is always O(n^2). Better to play the odds that might be slightly faster than the odds when you know it's going to be awful.
You're certainly correct on the BigO, but I'd be remiss if I didn't stick up for my boy, Selection Sort. Yes it is guaranteed to run in n^2 regardless of input. However, it is among the most conservative of any sorting algorithm with regards to writes, especially in the worst case. In such a case, SS only has to perform n-1 swaps, which can be very advantageous if write speed is dramatically lower than read speed, or endurance of the write-to medium is of greater concern than run-time.
To that end, this demonstrates another weakness in the above video. His "finding the max/min" is in reality a bubbling of said max/min to the correct position, NOT a swap to a searched-for position, which is how selection sort actually works. I think he actually said the words "trickles down" which is textbook bubble sort.
schulmaster There is cycle sort.
@schulmaster Any algorithm can be made adaptive. Any algorithm can be optimized. In fact, I found a method to optimize selection sort to achieve O(n) best case, a bit more complicated but I can write it out in another comment if you wish. It uses a few extra pointers and requires the input list to be reverse sorted (for best case) but it still finds the minimum during each pass.
Point is, any algorithm can have optimizations like the one you pointed out. Your modification to insertion sort is still a modification. It just feels like a small modification because of your choice of programming language and CPU architecture. In some programming languages, aborting passes is not easy. Ultimately, what optimizations are "simple" and which are "complex" is arbitrary. But this video isnt about optimizations. This video is simply showing that, given the purely mathematical formulation of sorting given by the professor, insertion sort and selection sort are identical. If you want to try adding in optimizations (which ultimately starts factoring in your programming language and architecture), then its a different argument entirely
I love the Prof Hutton analogies !!
How did this not make the trending list??? Thank you so much this is what I needed!!!!!
Although this is an interesting observation, saying the two sorting algorithms are the same just because of this picture is stretching it a bit far.
Otherwise, I can say that quick sort with a pivot being the first element is the same as insertion sort is the same as selection sort... but such statement is extremely misleading.
that depends entirely on what you mean by "the same" which isn't at all a trivial thing.
For instance, if all you care about is that your algorithm sorts numbers correctly, then _any_ correct sorting algorithm is "the same".
But of course, if you care about efficiency, implementation details will matter.
They are literally exactly the same if you execute them in parallel
XClann Of course not. They run in the same time and memory. They even make the SAME COMPARISIONS.
Not misleading at all, that's actually mathematically accurate.
+Eduardo Gomes Nope. Quicksort runs in n log n in best cases. The best case for insertion is n and selection is n^2.
XClann I'm pretty sure Eduardo Gomes was talking explicitly about Insertion- and Selection-sort in that comment.
The picture is kind of neat. Saying the sorting algorithms are the same is really just playing with words. I can argue that all sorting algorithms are the same because they output a sorted array. I can see it being helpful one first learns about these two algorithms to compare them in this way. Ultimately helpful. Good video.
Your videos are excellent. You explain computer science concepts so well. Great job!
i love this channel! i feel lucky i found it xD a lot of interesting stuff put in simple words and explanations.
They're not the same: one is the dual of the other.
And computers really care anbout the order (cache coherency, load-store forwarding and other peculiarities in the way memory is accessed)
The first one wasn't even selection sort; it was more of a bubble sort. And the second one is hardly insertion sort, since he continues to compare numbers even after the insertion.
A dual is a graph such that planar faces are replaced by a node, and edges attach nodes of the dual when the original faces are adjacent.
As drawn in the video, the two algorithms are in fact isomorphic, the only measure of "sameness" that matters topologically. The dual of the directed graph shown would look very different.
He went through the whole array and picked the smallest. It sure looks like selection sort to me.
Bubble sort is more of "tagging along" with one element until you put it in the end of the array.
Thurston Sexton, the word 'dual' in mathematics has multiple meanings. The concepts of isomorphisms and duality are related, however. Go read the paper I linked to as it explains what I'm referring to very well.
Actually what is demonstrated here is bubble sort (which is the worst O(n^2) sorting algorithm in existence). It works _exactly_ as bubble sort, and performs _exactly_ as many comparisons (n^2/2) and swaps, and the order of the elements after each step is exactly as in bubble sort.
Insertion sort, in most cases, performs less comparisons and swaps than bubble sort (because when you are moving an element towards the beginning of the array, you can stop when it's in its correct place, and don't need to keep going). The worst case scenario is when the array is in exact reverse order, in which case insertion sort performs exactly as many steps as bubble sort. (It essentially does the same thing in this case, just in a different order.)
Actually if you parallelise them, Insertion, Selection, and EVEN Bubblesort are all the same!
I was thinking the same thing, and if you use sorting networks, these all algorithms would be O(n) of course the bigger the input the bigger the network needed
Shobhit Vashistha
I'd love them to make a video on bitonic merge sort
+Shobhit Vashistha what is sorting network ?
Gladius Sapientia
Basically just a big amount of comparators (the 2 input, 2 output boxes from the video) that work in parallel. If you have n/2 comparators, sorting n numbers works in just O(n) time. Bitonic merge sort is an algorithm that needs O(n*log^2(n)) comparations in total, and works in O(log^2(n)) time.
Bubblesort has different dependencies than Insertion or Selection. For this particular sequence, Insertion/Selection sort never compares 1 and 5, but Bubblesort does.
Beautiful explaination! Great video! :)
I didn't care for the point he makes but I really like the "boxes in a triangle" explanation
I cared for the point AND the "boxes in a triangle" explanation!
Then you watch these for entertainment. That's not very effective.
When seen this way the two may seem equivalent, but when programmed, insertion sort can be optimised a bit to make it faster, since one can stop comparing once the location is found. This can not be done with selection sort.
Yes, and also there are other possible improvements, like binary search. But the insertion process is still slow, so it doesn't make much difference.
i know just a little about programming but when I see insertion sort, I think to myself, huh, if I have to pick an algorithm, insertion sort is probably the one that I can implement more easily and more optimally
@@advanceringnewholder Nah, pick a random pair and swap them if they are in the wrong order. Repeat if necessary. After a very long process (upper limit: infinity) the entire set of items will be in order.
@@simonmultiverse6349 it's kinda like bogosort
Great video as always!
Beatiful explanation!!
Insertion sort is faster than selection sort, therefore they can’t be the same.
from the drawing i would've guessed that selection sort is faster...
Benjamin steffen If you are implementing insertion sort on something like a list. You would stop comparing after finding the right place to put the next number. The elements after that are already sorted.
Aren't they the same speed?
Because the first sort he went over is actually Bubble Sort, not Selection.
Insertion sort can be faster because you can use binary search to find the insertion point, but that's just a detail.
This is absolutely brilliant.
Bloody brilliant mate
Fantastic! Thank you so much for this video
great way of portraying it.
Wow, that's fascinating!
Well presented. Thanks.
Awesome Video!
MIND = BLOWN!
This could be an entire field of science, the way you represent a fundamental law changes the law.
pretty fascinating!
That's elegant! Not made that connection before
Would like to thumb up this video million times :) Really, whatta charming pearl!
Thank you so much!
wow! amazing! thanks a lot👍👍
This is very helpful
this is amazing!
Selection Sort and Insertion Sort are not the same algorithm. I think the speaker should have been more precise because they are algorithmically/mathematically not the same algorithm. I have a feeling I'll be now needing to correct some subset of students that will watch this video and think they will just not need to know one or the other and confuse the two.
On the other hand, I do think the visualization is helpful, and a neat way of explaining the two algorithms though that shows they are more like "duals" (very similar).
Daniel Page - The way he has drawn the algorithm is as a directed graph, with nodes representing functions. By construction, what the picture/video shows is that the two algorithms are mathematically isomorphic. The same number of comparisons are being done (nodes visited), and the same information cascade is occurring (edges travelled). The two names are only talking about a difference in order of operations, which topologically makes no difference.
+Thurston Sexton Yes, and that is relevant to my comment how? Still does not imply the algorithms are the same. You interpret the graph in two different ways to see what the algorithms do, that's the subtle difference here. It still does not mean the algorithms are the same algorithm. I mean, I can show you two isomorphic graphs whose graphs have a representation that hold very different meaning. That doesn't imply the graphs are identical in the same sense. It ONLY means the graphs are isomorphic. That doesn't mean the two algorithms are the same. They're literally not. If they were, you'd see them do the same operations every step.
As an educator and computer scientist, I see the handiness in the diagrams, but they do not prove they are the same algorithmically (which is the sense that was promised at the start, the speaker should have been more precise). It will only confuse people as that claim is not true.
amazing! thank you!
Fascinating ! Now I'll try to write that in python ...
This is so interesting!
This comparison hints at one of the differences between data-flow programming vs. process-flow programming.
It's also very easy to think of insertion sort like using marbles of different sizes, and pushing them in a line, and as the larger ones are higher value, and then fall into the next slot as long as it's bigger than the previous marble. So you're just moving it right until it falls into place. :) so it looks like a line:
@Oo. pushing over a wedge \./
Wish we could post inline images here.
im going to ask my uni lecturer if i can just "draw some pictures and forget about your fancy computing" 🤔
excellent video, thanks for sharing!
This is an (abstract) sorting machine that actually does the sorting in linear time. When we view its operation vertically it resembles or reminds us of selection sort, when we view it horizontally it looks like insertion sort. However it is neither selection nor insertion sort.
The sorting algorithms that we know and speak about (insertion, selection, etc.) are defined assuming a Turing machine (and Von-Neumann architecture, which is a Turing machine implementation). And they are not the same because they have different properties.
But the underlying assumption that the sorting algorithms are defined for the Turing machine often goes silently, teachers don't point it out and students don't know about it. This assumption is the real secret of the sorting algorithms (in the sense that people usually don't know about it).
> This is an (abstract) sorting machine that actually does the sorting in linear time.
It takes time that's linear in the size of the triangle (assuming you execute the triangles one at a time), but for n inputs you need a triangle of size Θ(n²), specifically n(n-1)/2.
For comparison-based sorting you can't do faster than O(n log n). Proof(ish): you can order n elements in n factorial (n!) different ways. A comparison gives you a one bit output, so k comparisons can distinguish 2^k different orderings-said another way, to distinguish m orderings, you need at least log m comparisons. Letting m = n! we see that you need log(n!) = log(1 * ... * n) = log(1) + ... + log(n). Half of the numbers in 1..n are at least n/2 and the other half is at least 2 (except for 1), so we get log(n!) >= (n/2) * log(2) + (n/2) * log(n/2) - 1 = (n/2) * (log(2) + log(n) - log(2)) - 1 = (n/2) * log(n) - 1 which is Ω(n log n).
(The logs are all base 2. If you select n such that n/2 > 4, i.e. such that 4 occurs in the small-numbers half, you can adjust the estimate to have a term of log(2*2) + (n/2 - 1)*log(2) = log(2) + (n/2)*log(2) = 1 + (n/2)*log(2). The extra 1 cancels out the "- 1" term and you get something which is aesthetically pleasing and easily seen to be Ω(n log n) without having to remember the exact rule whereby you can remove negative constant terms. Similarly if n is odd and 5 is in the smaller half, log(5) > log(4) = log(2) + log(2) and so you get a free "extra term" to compensate for splitting into "uneven halves" where the big-numbers half has one more element than the small-numbers half.)
there's quite a bit of disagreement here in the comments, but the fact is that the two algorithms, drawn as they are here (a directed graph), are isomorphic. This is a strong version of "sameness", tantamount to saying that any proofs about the behavior of one will apply to the other, purely via topology.
Alternative title: computer scientists stumble upon hardware description language ideas for sorting
Many sorting algorithms can be seen as the same if you see them in certain way.
For example:
Selection sort chooses the smallest of the unsorted elements and put it at the beginning, repeat until everything is sorted.
If instead of choosing the smallest number you choose the largest number and put it at the ending, it's the same algorithm, just with another comparison function and with other container to store the elements.
Now, if you use a heap to choose the largest element between the unordered ones, you have heapsort, but the basic idea is the same:
Take the "best" one of the unordered set, and add it to the end of the ordered set until the ordered set is complete.
Another example: if you create binary search trees in the standard way, in the end you are doing the same as quicksort: it chooses a privot(the root) and then you put all the smaller elements in one larger elements in the other side.
I know a context where selection and insertion is different: if you have a linked list with random access to store the output, insertion would be O(NlogN) (you make a binary search to know where to insert the new element, and then insert it in O(1)) while selection would be still O(N^2).
The idea of a linked list with random access may seem silly, but there are some situations where constraints are very close, for example, ordering a deck of cards in real life, another example may be to order something when the comparisons are very expensive (for example, if each comparison is a query to a web server) and the swaps are very cheap so you want to optimize the comparisons but not the swaps.
So basically, when represented as a sorting network, the difference between Selection Sort and Insertion Sort is row-wise vs column-wise ordering of operation. In CPUs and memory hierarchies order of operations can matter. Especially when the data to be operated on doesn't fit in a single cache line, and you need round-trips to memory. In modern CPUs the performance limitation for lightweight operations are commonly limited by memory access, and sometimes by branch miss-predictions. The result is it may be faster to do 100K logical operations with data from L1 cache and no branch miss-predictions than 10K logical operations with 1000 memory accesses and 1000 branch miss-predicions. That's a bit hyperbolic and probably don't represent logic that leads to the same result, but the take-away is an algorithm with higher branch miss-prediction and/or more memory accesses can be slower despite maybe even an order of magnitude less operations.
There is usually a cache for instructions and a cache for data, and the CPU designer has to make choices for both. The software writer may be able to ensure that data which need to be combined (e.g. to find larger & smaller of two numbers) are put close to each other, so a limited region of cache is required, thereby improving speed.
They are similar and this triangle view show their similarities but they are not the same. An algorithm is fundamentally a sequence of steps, when you change that sequence of steps you have a different algorithm. The visual model is interesting but the moment you actually implement it you have to make a decision on how the sequence of actions will take place, and that decision will produce different algorithms.
The main, VERY IMPORTANT, difference between insertion and selection sort is that insertion sort has the advantage that the operation of insertion can be made faster than selection. Inserting into a sorted region can be sped up by something like a binary search, while the operation of selection has no such optimization.
Yes, finding where to insert can be faster, but the insertion itself is slow, because you have to move half of the numbers on average.
And it doesn't really matter, because there are much faster sorting algorithms (quicksort being the most famous).
Gotta say, it was quite interesting indeed
cool thank you!
Very cool! ^.^
Insertion sort has a best case performance of O(n) while selection sort is O(n^2) for all cases. Selection sort is often useful in real time applications (due to its consistency), so it's important to make the distinction. Saying they're the same because of rows and columns is like saying quick sort and merge sort are the same because 'one is divide-then-conquer and the other is conquer-then-divide'.
In practice, though, insertion sort is much more efficient, because you can stop comparing as soon as you've found the place to insert the new element, whereas in selection sort you must scan through the array every time. The growth rate (O(n^2)) is the same, but insertion sort is the one that's actually used - it's actually much faster than merge or quick sort for small arrays. (Bubble sort is even worse, as it potentially does a swap for every comparison, whereas insertion and selection sorts only swap once once it knows where the element goes or which element is the smallest, respectively.)
this was epic
but the code for either algorithm is very different.
So which algorithm is best? (Fastest, least mem.....)
There's no such thing as "fastest" and "least memory". That's because it's dependent on your data. (Heck, there's an important class of sets where *Bubble* Sort is the fastest... (And, being in-memory and using only one temp variable, is least-memory.)
RonJohn63 not really correct selection sort has a best case time of Omega(n²) while insertion sort has a best case time of Omega(n) they both have the worst case time of O(n²) and the space complexity of O(1)
Just because this drawing is both types at the same thing, it doesn't mean that all insertion and selection sorts are the same. Of course this drawing is going to look like both, since the numbers have to get to a specific end point, but on the sheet of paper, you don't see what the process to get to that end point is.
But even though they have the same end result they are still different because they behave differently. Insertion sort does a lot of moving the data around which can sometimes be expensive while selection sort does a lot of comparisons. So depending on whether comparing or moving is expensive determines which sorting algorithm is faster, so they aren't exactly the same but it is still a very nice visualization trick.
Interesting take on things. Is it inspired from functional thinking?
what I've learned: insertion and selection aren't the same, as a sorter myself, I know how they work
Insertion: It'll try to make the final product as best as possible, and put new elements in their position
Selection: It'll look at each item, and remember where it goes, then in the next pass, it puts it in the right place.
While they might look the same, they are quite different when actually run. Inserting an element into the middle of an array is far more expensive than appending to the end.
There is one small difference between insertion and selection sort when the are put into code. Insertion sort is one of few that can realize that an incoming list is already sorted and terminate early
Very good. 🇧🇷
That happened to my learning nodes & graphs algorithms to determine closes distance or determine positions to a route. My code did both tasks just stores the answer in different vars.
What about the linear complexity of insertion sort on sorted lists? it behaves very different from selection sort in that manner.
Would you please let me know which application is used for the simple animation.
Surely this pictorial view holds for every O(n^2) sorting algorithm. It is basically a n^2 grid with binary comparison boxes on each vertex, and every different O(n^2) sorting algorithm has a different order of executing all vertices.
Your pictorial idea is also known as a data-flow diagram. It shows where the data goes (where the numbers go). It also shows which numbers depend on which other numbers.With this information, it still leaves you with _some_ freedom of choice about the order in which you do various operations. Making these choices will give you an algorithm.
AND WHAT IS MORE.... if hardware parallel processing is available, you have many more choices about which bits of hardware (doing the processing) are assigned to which bit of the problem, and when.
With insertion, when you see that the number you insert is smaller than the next one, you can stop there for that line, so you save half the time (in average)
And you are comparing the two worst sorting algorithms possible
Selection Sort: n(n-1)/2 comparisons, 2n-2 moves
Insertion Sort: ~log(n!) comparisons (often represented by O(n*log(n)), and ~n(n-1)/4 moves.
Did I get those right? For the IS comparisons, I am assuming the use of a binary search to determine where to insert incoming elements.
A Natural Insertion Sort gets better performance by taking advantage of naturally occurring runs. You can then optimize it further by inserting runs (if you are trying to insert the run (A, B), then you know that where A is inserted is a strict lower limit of where B can go). You basically end up with a Natural Insertion Sort, but the "insertion" is actually a "merge."
I personally like Insertion Sort more than Selection Sort, because it is easier to take advantage of that already sorted subset. (The mathematician in me: "something something the beauty of induction.")
How would the presentation of bubble sort (bubbling up the smallest number) differ from this presentation of selection sort? Because I really can't tell why you didn't call the first one bubble sort.
the title made me think of Harry Potter / Pottermore sorting.
you guys uploaded this one day after the release of Fantastic Beasts, so of course Harry Potter is on everyone's minds
"if you forget all your fancy computing" ha. It's interesting how you've done this. I sometimes have to draw diagrams to get my head around code, I'm more visual. if I can visualise it, I tend to understand it easier.
It's the same for everyone
So does this mean that both algorithms require the same computational resources? Is one quicker or more effiecent than the other or are they the same?
Cool!
Nice.
Correct me if I'm wrong, but is that not also bubble sort?
Ontonator nope, bubble sort starts with the whole array, and keeps switching positions of elements that are next to each other. it requires n^2 comparison operations to be made. but selection and insertion sort both requires n^2/2 comparisons.
bubble sort is also n²/2 if you stop comparing the "highest" numbers
Ontonator bubble sort will work diagonally in the same diagram may be
Bubble sort is effectively the same as selection sort when you start the latter at the highest values. Swapping neighboring elements is just one way to get the highest one to the top. As pointed out, you can skip those that are already sorted.
You can define insertion and selection sort with "bubbles".
You define a sorted part of the array (initially empty) and the rest is unsorted.
For the insertion sort, you take the first element of the unsorted part and bubble it up to its position into the sorted part. And repeat until the unsorted part is empty.
For the selection sort, you run a single bubble through the unsorted part so that the smallest reaches the sorted part.
And for the bubble sort, you just run your bubble through the whole array/list every time.
So you can see the insertion and selection sort as just optimizations that start or stop the bubble away from the boundaries of the array/list.
it would have been really great if you first define each one of them, then show that they are the same !
also it would be awesome to explaine some of n log(n) sorts like merge or quick sort
They've done videos on those before.
lies damnlies
where is that, what is it called ?
Although quicksort and merge sort are very different, with different asymptotic performance, quicksort is equivalent to unbalanced tree sort (in Haskell they are identical due to lazy evaluation).
How come insertion sort is usually preferred over selection sort, if their sorting networks are the same? Does it have to do with the algorhithmization of the processes?
Quicksort and mergesort do basically the same thing, split sequences into two and put them together again. The only difference is in which process do you do the comparisons.
I guess all sorting algorithms are the same at some level of abstraction.
what about Bogosort :D
Tuchulu They'd said at the end that they tried to write a paper to show that, but it didn't work out so easily. Indeed, think about how a quick sort works. You're comparing one number to everything else in a sequence. There isn't a simple way to use two-input two-output boxes to make that work. The only similarity is that you compare two different things and repeat that over and over again.
how would one go about implementing bogosort with abstract sorting machines? I wonder...
INPUT => ALGORITHM => SORTED = EVERY SORTING ALGORITHM
They're all, er... sorting ?
Are you guys working on a video on the Investigatory Powers Act and its implications for the privacy of UK citizens? If not then I think you should be looking into it. Maybe you could even get it ready for when it gets Royal assent.
That was a nice secret.
For those who blame him for differences in two algorithms, of course "algorithms" are different.
He clearly said the difference is by looking at rows or columns.
By interpreting the picture differently (row/column wise) you get the two algorithms.
I wouldn't call them the same, they just share some of their structure. So they're very similar but not the same.
If this is how you teach, your students have it really easy... :-)
What is this accent?
+MagmaMusen Scottish u believe >Sean
+MagaMusen u here? really surprises me :)
Thanks, love it. Interesting video as always. :)
My thoughts were "Scotsman gone to the US"..?
Cheers :) (what's always interesting is replying to comments through the UA-cam studio app as it doesn't actually show you what video the comment is about, though I had a fair idea having just put that one live... Now confirmed on desktop machine!) >Sean
This is gonna have a shell, merge and quicksort follow up I hope right?
Remember the times of ZX81 when sorting 5 numbers really was time critical :-)
What about memory on the stack? will it be the same?