CODEWITHSUNDEEP
calgorithmsortingsequenceshellsort
fresh42juice
fresh42juice

Reputation: 117

How do I perform shell sort using sequence {3,2,1}?

Suppose I have an array:

30 20 29 19 28 18 27 17 26 16 25 15 24 14 23 13 22 12 21 11

I am not understanding how to do the shell sort using sequence 3: Would I simply do this:

30 20 29 19 28 18 27 17 | 26 16 25 15 24 14  |23 13 22 12 21 11

Where I split it into 3 parts and sort the respective parts? And then do the same with 2 sorting after, except split into halves? What is the right way to do this? Can someone please explain?

Upvotes: 0

Views: 654

Answers (1)

Hogan
Hogan

Reputation: 70538

If you look at your array and number the locations

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
30 20 29 19 28 18 27 17 26 16 25 15 24 14 23 13 22 12 21 11

In a shell sort, what you do is start with a skip number (in your case 3) so to make the first "list" you take a number and skip. With 3 this would be 1st, 4th, 7th etc.

So you would have a list of 

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
30       19       27       16       24       13       21

and a second list of 

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
   20       28       17       25       14       22       11

The 3rd list is the remaining items.

For the next round you do it with one less... so items at odd number locations and items at even number locations.

In response to comment below

A Shell sort is an in-place sort — that means you don't remove the items to new lists or create any new data structures. You are using the array to "treat" items which are "far apart" in terms of array locations as next to each other. You don't actually make new lists or new arrays (that is why I showed my diagrams as I did); you just look at these locations.

Why?

Because it means that when you start (for example with 3) you are moving stuff farther) -- eg the 13 that starts at location 16 gets moved to location 1 in the first pass. Then as you reduce the number you start doing more local changes. This means you gain an advantage over a typical bubble sort. Still not good — but MUCH better than a bubble sort.

Upvotes: 2

Related Questions