Lonto di end

I hate to break it to you, but your teacher gave you slightly wrong information because this is not insertion sort, but rather optimized gnome sort. insertion sort is slightly different. i’ll explain later.

(Edit: this is Optimized Gnome Sort not Gnome Sort.) I hope you weren't trying to learn Insertion Sort because the video title is misleading; the sorting algorithm in this is actually Optimized Gnome Sort, not Insertion Sort. Still a good video though.

actually, this is optimized gnome sort

if you couldn't understand this even just by reading and needed this to fully understand, maybe you should stop trying

@@mernus7512 stop being so toxic

Here's an outline of what's going on. The goal is to get all the numbers in order. At the beginning, each dancer in turn (starting with a[5]) says "Hey dancer five places ahead of me, let's trade places if I'm smaller!" The reason we start with a[5] is because they're the first dancer who has someone five places ahead of them. So a[5] calls out to a[0] and trades places (thus putting their numbers in a better order); then a[6] calls out to a[1] but doesn't trade places because those two are already in the proper order; then a[7] calls out to a[2] but doesn't trade places, and so on. Why five places, exactly? This is actually an arbitrary value; it could have been different. The idea is that by looking five (or however many) places and swapping, you're very roughly putting things in order already. The small numbers get to travel way over to the left, and the bigger numbers get swapped over to the right. Some numbers are still going to be out of order, though, so now go back and do the same thing, but with a more fine-toothed comb: in the next pass (0:50), you'll see that they look exactly three places to the left every time. After swapping, they swap again if possible with their new three-places-over neighbour. Then, in the final pass (1:50), they simply look to their immediate neighbour every time, and this must put them all in order. (It might be easiest to understand the algorithm by watching this final pass first.) Again, the purpose of the first two passes was to do some rough work so that by the time the final pass starts, it's already in pretty good shape; the low numbers are near the beginning and the high the end. Note that they could have just started with the final pass (i.e., skipping the "look 5 ahead" and "look 3 ahead" phases), and this would still successfully sort the numbers. However, it would have likely involved more work since you would have to do more comparisons; you wouldn't have the benefit of an almost-sorted array. The final phase alone is called "Insertion sort" and has its own dance video.

Gnomesort and Insertionsort are closely related, but they differ in one step: Insertionsort saves the position of the next element to sort, while Gnomesort goes back up to that position. Since they don't compare the elements again after inserting at the right position, it's Insertionsort.

@@RyanLucroy well if you search for insertion sort explained and watch the video with the robots, you will see that insertion sort keeps the current element in an auxiliary array, until all of the necessary swaps of the elements to the left of it are performed. So to go to it in more detail, if this was insertion sort, after the 7 was placed in its correct position, the rest would be different; the 2 would be moved from a[5] to an auxilliary array then compared with the 8 and then the 8 would be moved from a [4] to a[5] but the next step would not be to move the 2 to a[4] but rather to compare the 2 to the variable stored in a[3] which is the 7 and because the 7 is higher, the 7 gets moved from a[3] to a[4] and then the 2 gets compared with the the variabled stored in a[2] which is 3 and because 3 is higher, the 3 gets moved from a[2] to a[3] then the 2 is STILL in the auxiliary array and gets compared with the variable stored in a[1] which is 1 and because 1 is NOT higher than 2, the 2 finally gets moved from the auxiliary array to a[2]. So with insertion sort, NO ELEMENT CAN BE MOVED FROM THE MAIN ARRAY TO AN AUXILIARY ARRAY MORE THAN ONCE.

@@RyanLucroy if gnome sort saved the position of the next element to be sorted, it would still be different from insertion sort; it would be optimized gnome sort.