0:01

Now, we'll look at Shellsort which is a bit elementary on the face of it but it's

Â not at all elementary as you'll see. The idea of Shellsort is that Insertion Sort

Â is inefficient because elements really move only one position at the time even

Â when we're kind of know that they have a long way to go. The idea behind Shellsort

Â is that we'll move entries several positions at a time and the way we're

Â going to do it, it's called h-sorting the array. So, an h-sorted array is h

Â different inter leaves sorted sub-sequences so in this case with h=4

Â if we start at L and look at every fourth element - M, P, T - then it's sorted. If

Â we start in the second place at E and look at every fourth element, it's sorted. So

Â this is 4 interleave sequences, that's a 4-sorted array. And what we're going

Â to do is implement a sorting method that h-sort for decreasing sequences of values

Â of h. This is one of the oldest sorting methods invented by Shell in 1959. So, in

Â this case, it starts out with the input example shown and then the 13-sort -

Â a few items are moved, 4-sort - a few more are moved, and then finally, a 1-sort.

Â And the idea is that each of the sorts can be implemented with only a few

Â exchanges given that the previous ones happened. So first thing is how do we get an

Â array h-sorted? That's actually pretty easy. We just use Insertion Sort but

Â instead of going one back every time we come with a new item, we go h back. So for

Â example when we come to this A in the Insertion Sort, then it's, we look at the

Â array before that and then there was M and E in the positions three back so we

Â exchange the A with the larger one to its left, that's M and then the other larger

Â one to its left, that's E and then put it into position. So the code is the same as

Â insertion, as for Insertion Sort, except that when we go backwards through the

Â array we skip by h instead of just by one. That's how we h-sort an array. And the

Â idea is we're going to use Insertion Sort because of two reasons based on our

Â understanding of how Insertion Sort works. While the first thing is if the increments

Â are big then the size of the sub arrays that we're sorting are pretty small so any

Â sorting method including Insertion Sort is going to work well. But the other thing is

Â if the increments are small because we've done previous h-sorts for bigger

Â values of h, the array is partially sorted and so Insertions Sort is going to be

Â fast. You wouldn't work to use Shellsort as the basis for h-sorting because that

Â always takes quadratic time no matter what order there is in the array. So let's look

Â at example of Shellsort with increment 7, 3, and 1. So, we start with

Â this sort example and then 7-sorting it - just involves doing insertion

Â sort but just reaching back 7 each time. In this case, the 4

Â subfiles stretched out at seven each only have two elements in them. And then we

Â 3-sort. Now, because it's 7-sorted and a 3-sort elements are either

Â already in placed or on a go back a few strides. On this case, it's only the A

Â that goes back two. And then we 1-sort and again because of the fact that it's

Â been 7-sorted and 3-sorted, the arrays are almost in order when it comes

Â time to do the 1-sort and most of the items only go back one or two positions.

Â So we have to do a few extra passes to do the higher sorts but the each element

Â moves only a little bit on each path and that's how Shellsort gains its efficiency.

Â So actually once you 1-sort, that's Insertion Sort so you're going to always

Â get a sorted result. The only difference is how efficient is that. Now the

Â intuition behind Shellsort and actually the mathematical fact is that if you've

Â got an array that's h-sorted and then you k-sort it for another value k different

Â from h, it's still h-sorted. This is one of those mathematical facts that seems

Â obvious but then if you try to prove that maybe it's a little more subtle than you

Â think. So, if you think of all this is, is, is trivial and easy, go ahead and try

Â to write down a proof that a g-sorted array remains g-sorted even after it's

Â h-sorted. But most people will accept that and it's a fact and that's how Shellsort

Â gains efficiency. Now there's another problem is what increment sequence should

Â we use for Shellsort. One of the first things you might think of is let's try

Â powers of two. Actually that one doesn't work at all, very well at all because it

Â winds up not comparing elements in even positions with elements in the odd

Â positions until the 1-sort which means performance can be bad. Shell's original

Â idea is to try powers to two minus one and that works okay. Knuth when he wrote his

Â books in the 60s proposed the increment sequence 3x + 1. We'll start with the

Â 1, 4, 13, 40, 121, 364 like that and that's good because it's

Â easy to compute. When we're using in Shellsort of course, we find the largest

Â increment less than our file size and then do the sorts for decreasing values of that

Â increment. But finding the best increment sequence is a research problem that has

Â confounded people for quite a long time. Here's an increment sequence that I found

Â after maybe a year's work and it works well but nobody knows if that's the best

Â one. So here's the implementation in Java of Shellsort for Knuth's 3x + 1

Â increment sequence. We'll just go ahead and compute the increments that are

Â less than n, n / 3 and then starting at that increment whatever it is and say,

Â we started 364 then next time we need an increment, we'll just divide it by 3,

Â 364 integer divide by 3, 364 integer / 3 it gets 121, 40 and so forth. So,

Â this h = h / 3 gets us to the next increment. And then, the implementation is

Â just Insertion Sort. We just go through starting at h for i and when we do the

Â insertion, the j loop, we decrement j by h each time, otherwise the code is exactly

Â like Insertion Sort. So, just adding this extra loop for h-sorting and this extra

Â loop to compute the increments to Insertion Sort, we get a slightly more

Â complicated piece of code but its much, much more efficient. Here's what it looks

Â like for a bigger array. We start with the randomly ordered input and you can see

Â that it gets more and more in order on each time that we h-sort for the

Â decreasing values of h. Here's an animation. This animation does the whole

Â h-sort for each subarray. It's a little better feeling for what's going on.

Â And now to do the high ones pretty quickly and now it's doing the 1-sort and again

Â it steps through the array pretty quickly. If it's partially sorted it doesn't make

Â much difference - does the higher sorts a little bit faster. But that's simple to

Â implement and very efficient sorting algorithm. Now, the analysis of Shellsort

Â is still open. Now, there's a few things that we can say. For example we can say

Â that the number of comparison and the worst case is O(N3/2) for the 3x + 1

Â increments. But actually in practice it's much less than that. The problem is nobody

Â knows an accurate model for describing the number of compares taken by Shellsort

Â for any interesting increment sequence. This seems to be with a small value,

Â multiple of n times the number of increments used which is some multiple maybe of n log n

Â but nobody is been able to find an accurate model that proves that for any

Â interesting increment sequence for Shellsort. So, why we are interested in

Â this algorithm? Well, it's a simple idea that leads to substantial performance

Â gains. It's very useful in practice because it's pretty fast except for very

Â huge arrays. It's going to beat even the classical sophisticated methods for medium

Â sized arrays. And it doesn't take much code. It's often used in embedded systems

Â or in hardware sort type systems because there's so little code involved to

Â implement it. And it just leads to a lot of interesting questions. This gets to the

Â intellectual challenge of developing algorithms. If you think what we've been

Â studying so far is trivial, go ahead and find a better increment sequence. Try some

Â technique to discover one and try to say something about the average-case

Â performance of Shellsort. People have been trying to do that for 50 years without a

Â whole lot of success. So, the lesson is that we can develop good algorithms or

Â good implementations without much code but there are some out there that are still

Â waiting discovery. It could be that there are some increment sequence out there that

Â make Shellsort more efficient than any other method, any of the sorting method

Â that we know for pratical file size, no one can deny that. That's Shellsort or

Â first non-trivial sorting method.

Â