CSC 212: Programming with Data Structures

Homework 9: Quicksort

Due: Wednesday, April 13, 11:59pm

This is the last official homework for 212! (There is an optional redo Homework 10.) This assignment is individual, so everyone should submit their own original code. However, you are welcome to collaborate with other students and discuss aspects of the assignment outside of the code.

The purpore of this assignment is to implement quicksort, a practical, in-place sorting algorithm. We will also practice recursion and "backwards" code design.

Outline

Below is an outline for you code. To begin, download: Card.java and SortRecorder.java are almost the same as before, but SortRecorder has been modified to work with arrays. For quicksort, we'll be using a Card array to perform an in-place sorting algorithm.
  1. Run the program:

    First, run the code to make sure the unsorted cards show up. You can start with a smaller number if you like, or begin with the full list. You could also print them if that's easier than using the recorder to start out with.

  2. Quicksort:

    Then write a method "quicksort". Spend some time thinking about the arguments and the method signature. This method must be recursive. Use the notes from Class 19 as a place to start.

  3. Partition:

    Next write the method "partition", which will place the pivot in it correct position, and the rest of the cards should be in place relative to the pivot.

  4. Swap:

    Finally, write the method "swap", which should swap two cards in the array. Think about what this method should take in, and what the return type should be.

  5. Testing:

    Make sure to test throughly can use the recorder to create a nice visualization. Since this is an in-place sorting algorithm, the recorder should always display the same array of cards, but in gradually more sorted order.

Runtime

For the runtime component, we will perform a similar timing experiment as Homework 6. Create a similar setup for Quicksort, then test the runtime with a variety of numbers of cards. Record the runtime each time. Then divide each runtime by the number of cards that were used, and plot the results. Save your figure as "plot.png", and comment on your results in your readme.txt.

Extra Credit

For a small amount of extra credit, implement Radix sort for cards. The least significant "digit" is the value of the card (there are 13 "bins" for these). The most significant "digit" is the suit (there are 4 bins for these). This will require a bit of creativity and possibly modifying the SortRecorder if you use a different data structure.

To Submit

  • QuickSort.java
  • Card.java
  • SortRecorder.java,
  • Any timing classes
  • Plot (png) of your runtime
  • RadixSort.java (optional)
  • readme.txt, summarizing your observations on the timing results