Sorts 5 Shell Sort

Dr. Rob Edwards from San Diego State University summarizes shell sort - a tricky sort to get the complexity right

[Tumbolisu]

This video doesn't actually explain the algorithm correctly. Shell sort doesn't take 2 elements at a time like this. It simply takes all elements that are a certein gap size appart, and then performs an insertion sort on these. Thus, the final insertion sort only ever has to move elements that are very close together. How close depends on the previous gap size.
Also, the time complexity of shell sort is a bit harder to describe, as it depends on the gap sizes used. Halfing the gap size each time will indeed result in the worst case being O(N²). However, many different gap sizes have been tested in the past. Some have a worst case of O(N^3/2), others O(N^4/3). Some number sequences for gap sizes have an unknown time complexity, but tests show that they are even better than that!

[Mars]

Anyone get distracted and impressed by how well he is writing in reverse?

[johnphillip]

Thank you so much for putting this on the Internet. Had problems grabbing the shell sort concept.

[shinju]

Suppose to learn Shell sort but then I spent almost 10’ to know how learning glass works, 😂

[fedos]

Finally, an explanation that fully explains the algorithm.

[yesnickcarter]

I took Data Structures at SDSU almost 20 years ago. It was the class that changed my life. Loved it.

[xoxoo]

you choose ---> gap=4, then number 1 must goes in the first row (with 3, 7)

[coltonbooth]

Im more impressed by how he writes backwards than anything else

[jans.]

glad to see Jack Barker move on from his box idea into a new hobby of sorting

[bridger]

Great explanation, probably the best and shortest one I've seen so far. Thank you!

[marcosnavarro]

Your explanation helped me understand the selection sort very well but I believe you might have made a mistake on your first round when gap = 4. When gap = 4 it should have compared 7 and the 1. After comparison the 7 would then be inserted to where the one is and the loop should run one more time after that comparing the 3 and the one. Effectively putting the 3 where the seven originally was at the start and replacing the 3 at the start of the array with a 1. I may be wrong but after tracing the algorithm that is the answer I got and the shell sort worked.

[olabanjistv]

In the second round of the sort, where you not suppose to compare with the length of 2. Which is half of 4 that you started with 🤦🏽‍♂️

[XaxtonRevolution]

At the last step, when you switched the 2 and the 3, it wasn't a swap, the end result is the same as if you swapped. But the steps of your decision tree are to insert each number in its correct place by comparing it to all of the numbers to the left of it. If the numbers were simply being swapped at the last step, it would be a bubble sort.

[TruthTiger]

This helped me out a lot. Thank you Dr. Edwards

[tylerforrester]

your videos rock i was totally lost when it came to BigO and now from your vids i get. thanks for sharing the knowledge .

[shikharvasisht]

At 3:03, I could not understand why you compared 10 to 1, after 8 to 6. Shouldn't this be 5 to 10, 7 to 9, and 6 to 1?

[zerosandones]

Why does this decrease the time complexity? How many ops do you have to spend swapping? Which gap size should you use? Why is the complexity what it is? Great intro to the algorithm and thank you for creating the content... would love to see more detail.

[mhrga]

I love the presentation. Thank you very much.

[jamband]

Excellent work! Your glass presentations make comp sci concepts crystal clear

[micahjacobson]

if the gap was halved to two, shouldn't you have been comparing 3 and 8, 2 and 5, etc?