Shell Sort (Implementation)
A free video tutorial from Tim Buchalka
Java Python Android and C# Expert Developer - 1M+ students
4.5 instructor rating • 12 courses • 1,024,382 students
In this video, we'll implement the shell sort algorithm.
Learn more from the full courseData Structures and Algorithms: Deep Dive Using Java
Learn about Arrays, Linked Lists, Trees, Hashtables, Stacks, Queues, Heaps, Sort algorithms and Search algorithms
15:57:06 of on-demand video • Updated August 2021
- Learn the strengths and weaknesses of a variety of data structures, so you can choose the best data structure for your data and applications
- Code an implementation of each data structure, so you understand how they work under the covers
- Learn many of the algorithms commonly used to sort data, so your applications will perform efficiently when sorting large datasets
- Learn what’s available in the JDK for storing and sorting data, so you won’t waste time reinventing the wheel
English (bright music) (keyboard clicking) Sarah: Okay, so let's implement shell sort. I've created a project. I'm using package academy.learnprogramming.shellsort. I've added the usual intArray, the code for printing out the array and we don't need the swap method for this because insertion sort doesn't use swap and this is just, essentially, a variation on insertion sort. So let's go. So the first loop we're gonna have is the one that's going to initialise the gap value that we're using and then reduce it on each iteration. So we'll say for int gap equals intArray .length over two. Because remember, we're going to start with intArray, a gap of intArray.length over two. Which for this array, will be seven over two which is three. And then we're gonna keep going as long the gap is greater is zero because if the gap is zero, then that means that we're gonna be comparing elements against themselves. So we need a gap of one. For the final iteration, remember for shell sort, the final iteration always has to have a gap of one because we want the final iteration to essentially be insertion sort. And on each iteration, we're going to divide the gap value by two. And so on the first iteration, our gap value will be seven over two which is three. On the second iteration, it'll be three over two which is one. So the second iteration will be essentially an insertion sort. So now we're going to code the actual comparing and shifting. And as you'll see, and I'll show you this afterwards, that what we're gonna code here is essentially insertion sort. It's gonna look slightly different because it's using gap. But it's essentially insertion sort, and we'll compare the two implemetations, the two sets of code in a minute. So I'm gonna say four int i equals gap. I less than intArray.length because we're gonna want to look at all the elements in the array. I plus plus. And we're gonna start out as we did with insertion sort. We're gonna assign a newElement field with intArray i. Intarray i is the value that we're going to be looking at. So that's essentially intArray gap. And we're gonna use j to do the traversing. So we're gonna say while j is greater than equal to the gap because if j becomes less than the gap, that means that we've hit the front of the array. And intArray, j minus gap is greater than newElement. Well what do we wanna do? We wanna shift the element at intArray j minus gap up gap positions. So we're gonna say intArray j equals intArray j minus gap. And so what we're saying here, if we were doing the, we're starting out with a gap of three, so we're starting at seven, just as we did with the slides. And in the first iteration, we're gonna compare seven to j minus gap, right? Because we're going to assign seven to newElement. J is gonna start at three. And we're gonna say if intArray j minus gap while our gap for the first iteration is three. So if intArray zero which is 20, is greater than seven which it is, then we wanna shift seven up three positions. So we're going to assign intArray j which is three. So intArray three with intArray three minus three which intArray zero. So we're essentially gonna take what's at position zero and assign it into position three. And then once we've done that, we wanna subract the gap from j because we're saying that now we're going to want to compare newElement with whatever comes three positions over. Well, we've hit the front of the array at this point. We'll loop and we'll say, well j has to be greater than or equal to the gap and it isn't because at this point, it's zero. And that's because there's no elements to the right here. So first, we wanna compare seven against 20. If we could, we'd then compare seven against whatever occurs three places in front of 20, but there is nothing. And so we're gonna drop out here. And what do we wanna do at this point? Just like with insertion sort, while we're basically saying we found the insertion point for seven when we drop out. And so we're going to assign intArray j with newElement. And this should look somewhat familiar because this is essentially what we were doing with insertion sort. And so, after we've done that, we loop back around to this loop and i would become four. So it would become 55. J would become four and then what would happen is it's gonna compare 55 against 35. And it's not gonna do anything because 55's greater than 35. And at that point, once again, it's gonna wanna jump ahead three places and there's nothing so we're gonna just loop around. I will become five, so it's gonna compare one against minus 15. And because one is greater than minus 15, it's not gonna do anything, it's gonna loop around. And once again, it's gonna wanna compare to whatever's three spaces over and there isn't anything, so we're gonna loop back. I will become six, so minus 22. We're gonna compare minus 22 against whatever's here. Now it's not seven anymore, it's 20 because we moved 20 here. Minus 22 is less than 20, so we're gonna shift 20 here. And then we're gonna compare minus 22 to whatever's three spaces over. And this time, we do have something three positions over. We actually have seven here because on the very first iteration, we moved seven to the front. Minus 22 is less than seven, so we'll shift seven back to where it was originally was and then at this point, it's gonna wanna compare three spaces over and there isn't anything. We've hit the front of the array and so we'll assign minus 22 here. And at that point, we'll loop around, i will become seven and it'll fail this condition. And so we'll drop out, loop back around to the gap loop. Reduce the gap to one and at this point, when we enter this code, we're essentially doing an insertion sort. And that's how shell sort optimises insertion sort. So let's run this to make sure it's working. And we get the usual minus 22, minus 15, one, seven, 20, 35, and 55. So let's go out to a couple of slides for a minute to compare the code for insertion sort with the code for shell sort. Okay, so here's the code that we wrote for insertion sort. And we can see that here we're starting with a the first unsorted index as one. We assign newElement with whatever's at that value. We have i and then of course, we loop through all the elements to the end of the array and if possible, we shift elements to the right. And if we drop out of this loop, then we have found the insertion position for newElements. So we assign newElement to i. Here's shell sort. And if you ignore this part for a minute, you'll see that this code is pretty much the same. The only difference is, instead of using one, we're using whatever the gap value is. So in the first iteration we're gonna use three. And once again, if we go back to insertion sort, we're gonna assign intArray first unsorted index to newElement. While in shell sort, we assign whatever's at i, the gap value to newElement. We assign i to j. It's pretty similar to what we're doing here except the loop is taking care of assigning i. Here, we need a different index because we don't wanna be changing i as we traverse the, not the sorted partition, but the part of the array that we're looking for in insertion position four. And then we say in shell sort, while j is great or equal to gap and intArray j minus gap is greater than newElement, as long as that's true, we're going to shift the elements that we're comparing against. We're gonna shift it up the array by gap positions and then we need to decrease the position of the next element that we look at by the gap because we always want to be looking at the element that's gap positions away. And this very similar to what we're doing here. We're saying the same thing, as long as we haven't hit the front. And this is saying, as long as we haven't hit the front and as long as the element we're looking at in the, for shell sort it's not really the sorted partition, but the element we're looking at that's gap positions away, is greater than newElement. And back in insertion sort, as long as the element we're looking at is greater than newElement, we wanna do the shifting. And here, we wanna do the shifting. And here, because we're using a gap, we have to calculate the next index we wanna look at differently. We can't just decrement it by one as we are with insertion sort because we're assuming a gap of one here. And then when we drop out of this loop, we assign newElement to intArray i. And here, when we drop out of the loop, we assign newElement to intArray j. So I think if you take a look at these two sets of code, here's insertion sort again and here's shell sort, you can see that we're doing the same thing inside here as we're doing with insertion sort. It's just that we're examining elements that are farther away, except on the final iteration. On the final iteration, when the gap is one, what we're doing in here is exactly the same thing as what we're doing in here. And so the final iteration when the gap is one, we're essentially doing it in insertion sort. And that's what shell sort does, but of course, with shell sort, in the final iteration we've already moved several of the elements closer to their sorted positions and so there's going to be a lot less shifting that has to take place. And that's how shell sort improves on the insertion sort algorithm. And as I mentioned, you can also use the same idea to improve on bubble sort. You do some preliminary work. So instead of examining neighbours and swapping them, you'll exam elements that are further apart and swap them if necessary. And so by the time you get down to the bubble sort where you're using a gap of one, there'll be a lot less swapping to do. So that's shell sort. That's what the shell sort algorithm does for insertion sort and it can also do it for bubble sort. I'll see you in the next video.