Sorting Homework

Due before class Wednesday 2018-02-14

Shellsort

Shellsort is an in-place comparison sort published by American mathematician and engineer Donald Lewis Shell in 1959. It extends another sorting algorithm, insertion sort in this case, allowing it to compare elements that are far apart.

Given a sequence of "gap values" or "h values", each pass of ShellSort considers only every h elements in the list and sorts these relative to one another.

As long as the sequence of h values ends in 1, the last pass will be a regular insertion sort.

While Shellsort requires more operations than quicksort, it is preferred over quicksort in some embedded or otherwise constrained environments.

  1. Implement Shellsort using an inner insertion sort like in the pseudocode below. Use Tokuda's sequence as gap values. A worked example and more in-depth description of the algorithm is available on Wikipedia s.v. Shellsort.

     1. For an unsorted list of size n, select the largest value in the Tokada sequence < n
     2. For each value, h, in the Tokada sequence from this value down to 1:
         a. For each position in the list from h up to the length of the list minus one
             i.   save the value in the current position to a temporary variable
             ii.  clear the value stored at the current position
             iii. move backward through the array in steps of size h given 
                  that your index in the list is >= h and the next value you would
                  encounter while doing this is greater than the value saved in temp
                     * Write this next value to the current location
                     # This moves elements in the gap sequence that are already sorted
                     # up to make room for the element currently being sorted
             iv.  once your index in the list is < h or the next value you would
                  encounter is less than or equal to the value saved in temp
                     * Write the value in temp to the current location
    
  2. If one exists, describe a dataset for which insertion sort would outperform this implementation of Shellsort. If one does not exist, explain why.

  3. If one exists, describe a dataset for which insertion sort would underperform this implementation of Shellsort. If one does not exist, explain why.
  4. Implement insertion sort as described in Skiena ยง4.3.5 and time its performance compared to your implementation of Shellsort over the dataset(s) you described in the two previous questions. Include your code with your submission.
  5. Describe your findings from the comparison.

Library sort methods

  1. Python has more than one built-in method for sorting. What are they and how do they differ?

Short answers

  1. What do the operations upheap (or what Skiena calls "bubbling up") and downheap ("bubbling down") refer to in heapsort? What are these methods used for? How do they differ?
  2. Describe the advantages and disadvantages of mergesort.

Submission Options

  • Submit your assignment as a single pdf to sastrand@pdx.edu before the start of class Wednesday 2018-02-14.
  • Create a private github repository and add github user sastrand as a collaborator. Email me with your repo link anytime before the due date. I will pull a final copy when I grade. Please make one .txt or .md file in the repo that will serve as your submission. For each question that includes code, include a link in your submission document to the file in the repo containing the relevant code.