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!

[@basselkordy8223]

Thank you! i just learned about it and was looking for another resource so i watched this and got confused because my main source explained it like you did (which makes much more sense)

[@danielfernandes1010]

Thank you. It's unfortunate that this is one of the top videos when I look up for "shell sort".

[@student4373]

I was wondering why every other video explained it differently. Thank you.

[@ilovee271]

Yes, I think there's a bit complex but reasonable sequence formula that seems to get really close to O(n log n)!

[@Mars30999]

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

[@BartWillems1969]

And with his left hand as well!

[@hudzell]

The video is mirrored. He's writing normal for himself with his right hand and the video is flipped so we can read it.

[@TharaMesseroux1]

is he?

[@shinju7006]

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

[@allankirui554]

How does it work?😂

[@shinju7006]

@@allankirui554 Simply record a mirror. A mirror before them then a camera record the mirror.

[@shinju7006]

@bismillah eng. no color

[@ashmitchamoli781]

@@shinju7006 bruh just flip the video

[@piyushanand7965]

😂😂 first record the video from oposite side to the glass then edit the video in right to left manner

[@Brlitzkreig]

Genius idea with the glass wipeboard

[@johnphillip9013]

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

[@fedos]

Finally, an explanation that fully explains the algorithm.

[@FMgamer1]

how do you write backwards???

[@sdagur]

Yeah ,same question??

[@ozgunozerk]

Its probably mirrored after the recording

[@sebastianlacki8483]

Stop, that makes too much sense

[@HristoskoBG]

Probably just learned to write backwards, because I suppose he has an auditory in front of him

[@godofwinetits3826]

its another sorting algorithm

[@coltonbooth8633]

Im more impressed by how he writes backwards than anything else

[@jans.2686]

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

[@dariuselijah9277]

UNDERRATED COMMENT

[@HarshSharma-rw3vh]

😂😂😂😂

[@yesnickcarter]

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

[@xoxoo4877]

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

[@liquicitizendirk2147]

exactly my thought

[@bridger4954]

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

[@zerosandones701]

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.

[@marcosnavarro9420]

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.

[@sunflowerglaxy6735]

yesss i am trying to fix it frrfrfr

[@shikharvasisht1]

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?

[@SignzNSymbolz]

It was a mistake on the professor's part. He went back and said "somehow i ended up with two number ones" and then erased the comparison so that the 10 was on its own.

[@TrevorHigbee]

I assume you don't compare 5 with 10 because 3 is already being compared to 5. And 6 is already in a relationship w/ 8.

[@coolgorillaz9624]

@@TrevorHigbee i guess it depends on how you implement it, in Robert Sedgewicks Algorithms for c++ book, , the for-loop doing the swapping shown here goes up to

[@Brettsauces]

Basically, Dont compare the same number twice. So if say 8 is compared to 6, then next is 6 is compared to 1, dont compare the 6 again. Instead, start on the next uncompared number, which happens to be 10 in this case.

[@olabanjistv4626]

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 🤦🏽‍♂️

[@juancruzinfante6321]

yes

[@future-daypharmacists6647]

true

[@ElSkizzle]

He did it correctly. He went from gap-size 4 to gap-size 2.

[@elemindustries5540]

@@ElSkizzle the first gap-size was 3, second one was 2. -> No, he didnt take the half of the first gap-size.

[@Truchasgl3]

You dont need to take the half. You can select any gap as long as you do a gap 1 insertion sort at the end. The gaps used before it make the vector be "more sorted" to decrease the iteration needed in the 1gap sort. Taking the half helps. But you can do it with any sequence (some of them are more efficient than others).

[@jamband64]

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

[@XaxtonRevolution2]

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.

[@ya00278]

It's super clear! you deserve more likes!!

[@TruthTiger]

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

[@tylerforrester743]

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

[@IT_AvishkarBorkar]

my guy is the most confusing teacher ive ever met

[@kurobros4791]

Wait, I just can't fucking understand how he is writing all the letters in backwards.... Respecc. He already got a sub for that mad skill right there. Nothing else matter. Mad lad

[@housemajaliwa]

That was wonderful to watch

[@micahjacobson8533]

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

[@kailaspsudheer]

This guy takes class like Tony stark

[@giorgi23]

Now I understand why shell sort is not popular

[@firstnamelastname4685]

where could I know the calculation of the time complexity of shell sort? I know it may be too advance to be explained in this video , so I just would like someone to tell me where is a good step by step guide of calculating the complexity.

[@fedos]

Wikipedia has worst case complexities for various popular gap sequences. en.wikipedia.org/wiki/Shellsort#Gap_sequences Sedgewick, in the third edition of Algorithms in C++, explains "Our description of the efficiency of shellsort is necessarily imprecise, because no one has been able to analyze the algorithm. This gap in our knowledge makes it difficult not only to evaluate different increment sequences, but also to compare shellsort with other methods analytically."

[@sirhawkjames]

what da fuck my guy just writes backwards completely legibly casually

[@dakuisha5978]

In loop 1 why do you just leave the one hanging? In loop 2 why does the 10 and the 1 connect??? Thats a gap of 1 not a gap of 2. Also why do you just leave 9 alone? This is important info that you just kinda skipped...

[@MunyuShizumi]

This is an extremely inaccurate and misleading Shell sort explanation (honestly, just downvote the video), so here's a corrected version.. During the very first iteration (gap = 4), 1 is sitting isolated on the bottom for some odd reason at position 9 (one-based numbering, 1 = first position), where in reality it would've been compared with its left pair at position 5 (which has already been swapped during the first step!). Since a swap occurs (@5@9), position 5 is then checked against its left pair (@1) again. You might notice that this looks a bit like insertion sort now, and it is (in fact, Shell sort with gap = 1 is quite literally insertion sort). In short, you're adding a gap to insertion sort, each conceptual "nth element" subarray is just being insertion-sorted. Comparison/swap steps should look like this with gap = 4: italic = comparison only bold = (after) swap 7 6 8 9 3 2 10 5 1 *3* 6 8 9 *7* 2 10 5 1 3 *2* 8 9 7 *6* 10 5 1 3 2 _8_ 9 7 6 _10_ 5 1 3 2 8 *5* 7 6 10 *9* 1 3 2 8 5 *1* 6 10 9 *7* *1* 2 8 5 *3* 6 10 9 7 What now? You don't reduce the gap sequentially 4->3->2->1 as shown in the video. The very point of Shell sort is skipping gaps in large steps (typical sequences look something like 1, 4, 10, 23, 57, 132, 301, 701, ...), and optimizing this can be a little bit like dark magic sometimes. Any sequence that ends with gap = 1 will technically work in the end (at that point it's just an insertion sort), but the sequence shown in the video makes the algorithm stupidly inefficient and is entirely missing the point of Shell sort. After gap = 4, switching to gap = 1 should be most efficient, which turns this into insertion sort: _1_ _2_ 8 5 3 6 10 9 7 1 _2_ _8_ 5 3 6 10 9 7 1 2 *5* *8* 3 6 10 9 7 1 _2_ _5_ 8 3 6 10 9 7 1 2 5 *3* *8* 6 10 9 7 1 2 *3* *5* 8 6 10 9 7 1 _2_ _3_ 5 8 6 10 9 7 1 2 3 5 *6* *8* 10 9 7 1 2 3 _5_ _6_ 8 10 9 7 1 2 3 5 6 _8_ _10_ 9 7 1 2 3 5 6 8 *9* *10* 7 1 2 3 5 6 _8_ _9_ 10 7 1 2 3 5 6 8 9 *7* *10* 1 2 3 5 6 8 *7* *9* 10 1 2 3 5 6 *7* *8* 9 10 1 2 3 5 _6 7_ 8 9 10 Sorted.

[@m4h0r4ga]

I love the presentation. Thank you very much.

[@SumitDavdra]

I come here for shell sort, but know i thinking about glass board. Any one answer?

[@BelegaerTheGreat]

What an unnecesarily complex way to do something suboptimally.

[@behmog]

Very nice method to sort numbers. Thank you. Is there any method to retrieve the original sequence of numbers from the sorted numbers?

[@amnahhamzah9613]

what is the best case?

[@amitshiksha]

java code for shell sort: private void shell(int[] a) { int n=a.length; for(int gap=n/2;gap>0;gap=gap/2) //To create gap and reduce it by half { for(int i=gap;i=gap&&temp

[@georgecarlson3606]

those are some big words for a CHEAT

[@nimatagik7534]

how can you write backward man ? its really hard

[@johnpaulpineda9821]

Wow! Very good explanation. Shell sort becomes easy to learn. Thanks a lot Sir!

[@xoxoo4877]

you are choosing a gap, as number of elements/2, and in every new iteration, you are dividing it with 2

[@jigargadhia2093]

how well you explained, thank you

[@sunnyshah9013]

is it just me or the algorithm explained here is a bit off than what shell sort is?

[@TriachnidLOL]

Yeah seems kinda weird. Not really consistent i guess.

[@Whiteowl116]

yes i think he should compare the smallest number to its left neighboor after each swap to see if it should be moved further back.

[@bentroyer1]

how did he video tape this is that just a scary clear glass board?

[@ishitagupta5959]

Thank you!

[@welnyr]

3:55 Element one is doubled

[@shariyashaikh3886]

Thank you

[@XnDxNdXnD]

That was pretty intuitive explanation. Thx!

[@ecksem]

How are a bunch of students of a somewhat difficult engineering major freaking out about a mirrored video in the comments

[@KennyWhizz-m7k]

Exactlyyyy

[@manjuegazos4672]

Wait... there isn't 4

[@karotto594]

HOW ARE YOU WRITING BACKWARDS???!!

[@oggysaad1003]

Very well explained sir :)

[@harshitsinghai1395]

How are these videos made ?

[@darkinferno4687]

magic

[@TankNSSpank]

but why?

[@diweiye8420]

Now this might be a good algorithm to think, but this is DEFINITELY NOT what shell sort it.

[@fredtech6770]

i like your blackboard.it is transparent

[@БилалКиут]

THANK YOU!!!

[@singsarav]

Simply, by looking at at, I can say shell sort is least efficient compared to other methods. I have find the exact reason. I think binary tree is efficient in sorting. I don't have to do so many comparisons and swaps. I am looking for multithreaded binary tree sorting in java / javascript

[@srinivasasubramanyam5501]

You missed the last swap in first round. You can't cheat me.

[@marcelolopesdeamorimjunior9723]

fanfic 10/10 \

[@lucassmith6320]

This is wrong explanation go somewhere else

[@leydensjar]

This is not a correct explanation of Shell Sort.

[@TheNiczal]

Very bad explanation and even worst example,

[@hangchen6131]

Hahaha in the insertion sort

[@s-.-8821]

This is FALSE

[@josuejheymiticonaortiz3848]

GAAA!!1

[@ethan6708]

THIS IS WRONG