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!
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)
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.
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.
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).
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.
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.
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."
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
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 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
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.
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...
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
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
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.
Suppose to learn Shell sort but then I spent almost 10’ to know how learning glass works, 😂
How does it work?😂
@@allankirui554 Simply record a mirror. A mirror before them then a camera record the mirror.
@bismillah eng. no color
@@shinju7006 bruh just flip the video
😂😂 first record the video from oposite side to the glass then edit the video in right to left manner
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!
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)
Thank you. It's unfortunate that this is one of the top videos when I look up for "shell sort".
I was wondering why every other video explained it differently. Thank you.
Thank you so much for putting this on the Internet. Had problems grabbing the shell sort concept.
Anyone get distracted and impressed by how well he is writing in reverse?
And with his left hand as well!
The video is mirrored. He's writing normal for himself with his right hand and the video is flipped so we can read it.
is he?
how do you write backwards???
Yeah ,same question??
Its probably mirrored after the recording
Stop, that makes too much sense
Probably just learned to write backwards, because I suppose he has an auditory in front of him
its another sorting algorithm
Genius idea with the glass wipeboard
I took Data Structures at SDSU almost 20 years ago. It was the class that changed my life. Loved it.
This helped me out a lot. Thank you Dr. Edwards
your videos rock i was totally lost when it came to BigO and now from your vids i get. thanks for sharing the knowledge .
Finally, an explanation that fully explains the algorithm.
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.
I love the presentation. Thank you very much.
glad to see Jack Barker move on from his box idea into a new hobby of sorting
UNDERRATED COMMENT
😂😂😂😂
It's super clear! you deserve more likes!!
Excellent work! Your glass presentations make comp sci concepts crystal clear
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.
Im more impressed by how he writes backwards than anything else
That was wonderful to watch
Very nice method to sort numbers. Thank you. Is there any method to retrieve the original sequence of numbers from the sorted numbers?
how well you explained, thank you
That was pretty intuitive explanation. Thx!
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 🤦🏽♂️
yes
true
He did it correctly. He went from gap-size 4 to gap-size 2.
@@ElSkizzle the first gap-size was 3, second one was 2. -> No, he didnt take the half of the first gap-size.
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).
Great explanation, probably the best and shortest one I've seen so far. Thank you!
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.
yesss i am trying to fix it frrfrfr
you choose ---> gap=4 , then number 1 must goes in the first row (with 3, 7)
exactly my thought
my guy is the most confusing teacher ive ever met
what is the best case?
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.
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."
Thank you!
how did he video tape this is that just a scary clear glass board?
Very well explained sir :)
THANK YOU!!!
you are choosing a gap, as number of elements/2, and in every new iteration, you are dividing it with 2
Thank you
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
Now I understand why shell sort is not popular
This guy takes class like Tony stark
How are these videos made ?
magic
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?
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.
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.
@@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
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.
Wow! Very good explanation. Shell sort becomes easy to learn. Thanks a lot Sir!
how can you write backward man ? its really hard
How are a bunch of students of a somewhat difficult engineering major freaking out about a mirrored video in the comments
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...
3:55 Element one is doubled
Hahaha in the insertion sort
Hm.. a lot of unanswered questions..
I believe if you want questions answered you'll have to take his course.
@@BrennanDemarest I don't have to. I was merely pointing out that he doesn't cover important parts in shellsort.
i like your blackboard.it is transparent
is it just me or the algorithm explained here is a bit off than what shell sort is?
Yeah seems kinda weird. Not really consistent i guess.
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.
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
those are some big words for a CHEAT
Wait... there isn't 4
HOW ARE YOU WRITING BACKWARDS???!!
what da fuck my guy just writes backwards completely legibly casually
but why?
Now this might be a good algorithm to think, but this is DEFINITELY NOT what shell sort it.
fanfic
10/10
\
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
GAAA!!1
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.
You missed the last swap in first round. You can't cheat me.
This is not a correct explanation of Shell Sort.
This is FALSE
This is wrong explanation go somewhere else
Very bad explanation and even worst example,
THIS IS WRONG