I don't understand this passage. What are the two alternatives? (Algorithms, 258)
Having said that, I can think of two possibilities. Given, for instance, h of 3 and a sequence:
1 2 3 4 5 6 7 8 9
-- two methods would be first:
Compare and exchange 1 and 4...
...2 and 5
...3 and 6
...4 and 7
...5 and 8
...6 and 9
-- or second:
Do an insertion sort on 1, 4, and 7
Do an insertion sort on 2, 5, and 8
Do an insertion sort on 3, 6, and 9
Is that what the authors are getting at? What is the difference between "using insertion sort independently on each of the h subsequences" and "inserting each item among the previous items in its h subsequence"?
Maybe the first method looks like this:
For each element in the array, perform an insertion sort that increments by h (instead of 1 -- why Shell Sort is a generalization of insertion sort). Then go to the next h in the increment sequence.
And the second method looks like this:
Iterate through the array. (Because we'll be looking h elements to the left of each item, we can start at h.) For each item, exchange it with the element h to its left if the left element is less until you reach the beginning of the h-sequence to which it belongs (i.e. and index less than or equal to h).
The second method I know is just a refined description of the implementation I discussed yesterday (cribbed from memory). So I just have to make sure that the first method really is different from the second. Well, in some sense, the two must be equivalent -- but they should be different operationally. So how are they different?
Because the first method goes through every element in one h-sequence and puts it into place before moving to the next h-sequence. The second, on the other hand, goes element by element and organizes each of the h-sequences as it goes. It must be like finishing five braids either by performing all the first's weaves, then all the second's weaves, in order, or by performing the first weave for the first, the first weave for the second, and so on -- in order, but a different order.
One way to implement shellsort would be, for each h, to use insertion sort indepen-Have to research different implementations of Shell Sort. Would also help to clarify the mistake I made in my discussion yesterday.
dently on each of the h subsequences. Because the subsequences are independent, we
can use an even simpler approach: when h-sorting the array, we insert each item among
the previous items in its h-subsequence by exchanging it with those that have larger
keys (moving them each one position to the right in the subsequence).
Having said that, I can think of two possibilities. Given, for instance, h of 3 and a sequence:
1 2 3 4 5 6 7 8 9
-- two methods would be first:
Compare and exchange 1 and 4...
...2 and 5
...3 and 6
...4 and 7
...5 and 8
...6 and 9
-- or second:
Do an insertion sort on 1, 4, and 7
Do an insertion sort on 2, 5, and 8
Do an insertion sort on 3, 6, and 9
Is that what the authors are getting at? What is the difference between "using insertion sort independently on each of the h subsequences" and "inserting each item among the previous items in its h subsequence"?
Maybe the first method looks like this:
For each element in the array, perform an insertion sort that increments by h (instead of 1 -- why Shell Sort is a generalization of insertion sort). Then go to the next h in the increment sequence.
And the second method looks like this:
Iterate through the array. (Because we'll be looking h elements to the left of each item, we can start at h.) For each item, exchange it with the element h to its left if the left element is less until you reach the beginning of the h-sequence to which it belongs (i.e. and index less than or equal to h).
The second method I know is just a refined description of the implementation I discussed yesterday (cribbed from memory). So I just have to make sure that the first method really is different from the second. Well, in some sense, the two must be equivalent -- but they should be different operationally. So how are they different?
Because the first method goes through every element in one h-sequence and puts it into place before moving to the next h-sequence. The second, on the other hand, goes element by element and organizes each of the h-sequences as it goes. It must be like finishing five braids either by performing all the first's weaves, then all the second's weaves, in order, or by performing the first weave for the first, the first weave for the second, and so on -- in order, but a different order.
Wow, super complicated
ReplyDelete