Assignment 9: Sorting out Big-O    [100 Points]
Due Tuesday, November 18th by 11:59pm

This week's homework includes big-O analysis of software, first through loop-counting (analysis of iterative algorithms) and recurrence relations (analysis of recursive algorithms). The second part asks you to implement some of the best-designed algorithms for CS's most-studied task: sorting, including an "impossible" Big-O(N) sorting algorithm.

This week's problems may be done singly or in a pair. If you do work in a pair, be sure to adhere to the pairwork guidelines of (1) equal hands-on and oversight contributions to the work and (2) equal understanding of the submitted assignment.

Problem 1: Big-O running times...

40 points

This homework is available on paper and you may not share this homework assignment with anyone outside of the class (it has solutions from previous assignments). You can get a copy of this part of the homework:

• in class November 17th (Mon) -- not recommended
• on Colleen's door (Olin 1280)

• in class November 17th (Mon) or November 19th (Wed)
• under Colleen's door (Olin 1280) by Thursday November 20th (Thurs) by 4:30 (same deadline as the exam)

Problem 2: Sorting in Racket and Prolog

20 points

For this problem, you'll implement parts of the two "classical" sorting algorithms in both Racket and Prolog: selection sort and insertion sort. In each case, use the starter files sort.rkt and sort.pl.

Selection sort is the algorithm in which either the max or the min value is repeatedly found and removed from a list - and added to a new, sorted list in the appropriate order. For this assignment, you'll implement minsort, i.e., the selection each time should be the minimum element.

Insertion sort is, in a sense, the dual approach: rather than find the correct next-element to place into the new list (as in minsort, above), the algorithm repeatedly removes the first element from the original list and inserts it into the growing sorted list in the right spot. In this case the work is done in that insertion step: getting the new element into the right place.

Each of these files has some scaffolding (to make sure that it's actually selection sort and insertion sort being implemented. Each also has a number of tests to check your sorting algorithms. Here are those starter files -you'll need to change the name of sort.txt to sort.pl:

• sort.rkt
• sort.txt - to change to sort.pl

Writing additional tests is welcome here (and always a good idea), but we will not be checking for those during the grading. Submit these files as sort.txt and sort.pl to the usual place in the submission system.

Problem 3: Minsort, Heapsort, and Bucketsort: Java

40 points

For this problem, you should use the starter file Sort.java that is linked here:

• Sort.java
• SortTest.java

If you're getting an error about the static keyword, you may have a slightly earlier version of Java -- no worries! To fix this,

• Cut the definition of the Heap class from within the Sort class.
• Paste that definition above the Sort class (outside of it) and below all of the import statements.
• Remove the static keyword. (Do not add the public keyword.)
• Change the line Heap H = new Sort.Heap(); to the line
  Heap H = new Heap(); within the heapsort method.
• That's it! It should work and the tests should work unchanged... . When you submit your file, it will have that new structure, and that will be compeltely OK.
• Just for reference, a static inner class, such as Heap is really a "helper" class, just as in this example. However, it's absolutely all right to have more than one class in a file and to use those additional classes as helpers.

minsort is as described above. Here, there are two primary methods for implementing minsort (though variations are welcome):

• The "placeholder" approach
  
  An int[] can not hold a null value (since ints are not objects). So, if you wanted to find each min, in turn, and place it into a new array, you would need a "safe" value to use as a placeholder. One way to do this would be to first find the max element and then use MAX+1 to be the "placeholder." If you take this approach, you could create a new array and then find and insert the min of the old array, one at a time, into the new array. Each time you'd replace it with the "placeholder" value. Then, as a final step, you could copy the elements back to the original array.



• The "swap as you go" approach
  
  Here, you could keep track of the index, let's call it k (from 0 ... last index) of the next min to find. Then, find the min of the elements from A[k] ... A[last index]. Then, swap that min with the value in A[k]. Increment until you've made it all the way through... .

bucketsort is as described in class (on Thursday). It's also commonly called "counting sort." Here's a reminder/illustration of the algorithm:

• Create enough buckets so that each element in your list will fit in the buckets. (We're only sorting ints here.) For example, if our list to sort is { 4, 2, 4, 0, 0, 4 }, we will need five buckets with indices b = 0,1,2,3,4.
• Each bucket will accumulate the count the number of times "its element" appears in the original list. (This is why bucketsort is sometimes called counting sort.) In our example, here are the final counts bucket[b] for each bucket-index b:

   2  0  1  0  3   (buckets[b], the # of times b appears)
   0  1  2  3  4   (b, the index used for buckets)
  

• Once you have this fully-filled buckets list, you can traverse the buckets and "read out" the sorted elements by expanding the counts: { 0, 0, 2, 4, 4, 4 }
• This example is convenient because the min element was 0. If the min element is not 0, your algorithm will have to account for that offset! (The buckets array, like all arrays, will have its initial index at 0 no matter what.)

Be careful as you take things out of the buckets -- empty buckets can be tricky! As part of this implementation, we ask that you not simply allocate "a lot" of buckets - rather, you should determine the number of buckets needed, based on the min and max values in the input array, and then use that number.

heapsort is already implemented in Sort.java. Like make fast algorithms, it uses a clever data structure in order to achieve its efficiency -- your task is to implement the Heap data structure, which will ensure that heapsort runs as intended. Your Heap class has a single data member, which is a resizable array known as an ArrayList in Java. Since your ArrayList will contain integers, its full datatype is ArrayList<Integer>. This whole name is the name of the type of the data member heapdata.

Although the above description shows there's some overhead to using Java's ArrayList class, there are many advantages. Here are some of the methods provided by Java's library that you'll need to write percolate:

• heapdata.size() this returns the # of nodes currently in the heap. Note that this means that the first (min) element's index will be 0 and the last element's index will be heapdata.size()-1.
• heapdata.set( i, val ) this method sets element i to have a value of val
• heapdata.get( i ) this method returns the value that's currently stored at index i

The percolate algorithms

Recall that each of these two algorithms strives to maintain the "heap property" that each node in the heap is less than its one or two children:

• In percolate_down, the element in spot 0, namely heapdata.get(0) needs to descend through the heap until the heap property is satisfied. The way it will descend is by swapping places with the smaller of its two children. Remember that if i is the index of a heap element, then its two children are at indices 2*i+1 and 2*i+2. If there are no children, both of those values will be larger than the index of the last value; if there is exactly one child, it will have index 2*i+1.
• In percolate_up, the the element in the last spot of the heap, which is lasti = heapdata.size()-1, needs to ascend through the heap until the heap property is satisfied. The way is will ascend is by swapping places with its parent - again, only if needed. Remember that if i is the index of a heap element, then (i-1)/2 (with integer division) is the index of the parent of that heap element.

With those methods, you should implement the percolate_up() and percolate_down() methods in the Heap class. the appropriate length, then implement the repeated min-finding to that new array, and then run a short loop to copy the elements back to the original array.

The file SortTest.java, above, has tests for each of those sorting implementations. One note: the graders will not only be looking to see that your submission passes the tests, but that they implement the specified sorting algorithm. Java does have Arrays.sort built-in - in fact, we use it in the tests file, but don't use it to implement these sorting methods... !

Submit your Sort.java in the usual way.

As with the Racket and Prolog files, writing additional tests is welcome, but we will not be checking for those - so you will not need to submit the tests file in this case.

Extra credit...

There are two entirely optional extra-credit challenges this week:

• Analyzing the Improved StoogeSort algorithm...
• Implementing quicksort in Java...

Improved StoogeSort!

The first optional - and challenging! - extra-credit problem worth up to +5 points is to write a recurrence relation and solve it for the Stooge's improved StoogeSort. Improved StoogeSort does the following:

• Same base cases as ordinary StoogeSort
• If the list has many elements,
  • recursively sort the first two-thirds (leaving the last third untouched in its place)
  • recursively sort the last two-thirds (leaving the new first third untouched in its place)
  • again recursively sort the first two-thirds (again, leaving the last third untouched in its place)

Place your answer at the bottom of hw9pr1.txt at the bottom of the other part 1 solutions. Note that if you find the result irrational, you may have gotten it! This one requires handling a more intricate geometric series... .

Quicksort!

The second extra-credit option (again, up to +5 points) is to implement quicksort in Java. The signature provided in the file is

public void quicksort( int[] A )

public void quicksort( int[] A, int low, int hi )

One of the advantages of quicksort is not only that it's fast, but that it can be written to avoid the use of any additional arrays! So, for this implementation, do not use any additional allocations of arrays -- simply use local variables (single ints) and the provided array A. Warning: be sure your implementation always creates recursive calls whose size is smaller than the original call -- one common implementation bug is caused by recursing infinitely (well, until the stack runs out!)

There are tests in SortTest.java to test quicksort; again, the graders will take a look that it's actually quicksort that you've implemented! :^)