Shell Sort Tasks

Now try the following tasks. If you have problems completing them, contact your tutor

Task 1

Using a paper-based approach work your way through at least one example of Shell sort. You may wish to use the data set used here initially, but you should try at least one data set of your own making.

Task 2

Implement a function called shellsort to be used with the program you developed for previous sections. You will find that you will need to pay great care with loop counters for this exercise. For this first implementation you should use slice sizes of 2, 4, 8 and so on until it reaches the insertion sort stage. Count the number of comparisons and moves required to sort the datasets.

Task 3

Implement a  function called shellsort2.  This should differ from the previous version in that it has a second array embedded in the function that holds the number of slices to be used for a given pass.  (In the bench-checked example above the values in the array would start 3, 5 and 10)

Use this function to experiment with different sequences of slices (in general the program uses a sequence in increasing order) . Record the number of comparisons and moves required to sort the datasets for different sequences.

Next: Merge Sort