CmSc 250 Fundamentals of Computing III

Laboratory exercise 07: Shell sort algorithms

The purpose of this laboratory exercise is to implement three Shell sort algorithms and compare their performance

Task 1:

Download Lab07_ShellSort.cpp. It contains Insertion sort method and the original Shell sort method implemented. It has stubs for Sedgewick sort, Hibbard sort and Knuth sort. Its action is as follows:

  1. Read the size of the array to be sorted (less or equal 40000)
  2. Create an array with random numbers
  3. Sort the array with
    1. Insertion sort
    2. Shell sort
    3. Sedgewick sort
    4. Hibbard sort
    5. Knuth sort

Before each sorting the array is copied and the copy is sorted.

Each sorting function counts the number of swaps and then reports it.

Task 2: Create a project with the program and make sure it runs.

Task 3: Implement Sedgewick sort using the sequence of increments proposed by Sedgewick:
1, 19, …. 1 + 9*4k + 9*2k,… k = 0, 1, 2, …

You will need first to implement a function that computes the elements in the sequence and stores them in an array increments[], and then organize the outer loop in the shellsort function to take the gaps from that array. Include code to count the number of copying operations (called not quite correctly swaps)

Task 4: Implement Hibbard sort using the sequence of increments proposed by Hibbard:

1, 3, 7, …. 2k - 1,… k = 1, 2, …

The steps are the same as in Task 3.

Task 5: Implement Knuth sort using the sequence of increments proposed by Knuth:

1, 4, 13, …. (3k -1)/2,… k = 1, 2, …

The steps are the same as in Task 3.

Task 6: Run the program with various sizes of the array to be sorted and record the number of copying operations for each sorting method and each size. Can you say that for a given size some of these sorts are better than others? Explain your answer in a written report to be turned in as a Word file.

Task 7: At the end of the Lab send the source code (C++) or zipped Java project. Change the extension of the sipped file to .250. The complete program and the report are due on Tuesday 10/19 by 5 pm.