SUNY Geneseo Department of Computer Science

Lab 8 -- Quicksort

Purpose

Background

A case-study in, and explanation of, Quicksort's design appears in sections 10.1 and 10.2 of our textbook.

This exercise is based on an animation of Quicksort. In general, algorithm animations attempt to demonstrate an algorithm in action by displaying some visual representation of the data that the algorithm works on, and using this visual representation to show how the data change as the algorithm executes. In the case of sorting, the main data item is an array of numbers, and the main change that the animation shows is numbers changing place within this array as they rearrange themselves into sorted order. Almost all sorting animations show numbers as bars, with the length of the bar corresponding to the value of the number.

Exercise

The animation you will use runs as an applet on a Web page. Therefore, you should start this lab by pointing a Web browser at http://web.engr.oregonstate.edu/~minoura/cs162/javaProgs/sort/QuickSortH.html. The animation proper is at the bottom of the page.

You control the animation via five buttons at the bottom of the animation. Three of these buttons are labelled "Step," "Delay," and "Continue." These essentially select the mode in which the animation executes: single step, in which the animation executes one step of the algorithm each time you click on "Step;" continuous but slow mode, in which the animation executes the algorithm without intervention from you, but slowly enough that you can (kind of) see each step executing; and full speed mode, in which the animation executes the algorithm as fast as it can. The other two buttons are labelled "Restart" and "Quit." "Restart" causes the animation to reset itself to the beginning of the algorithm, reading any data entered into the text field above the buttons. "Quit" has very little effect. Experimenting with these buttons a little should give you a good sense of how to use them.

Use the animation to answer the following questions. I expect you will want to run the animation several times, observing what it does and trying to relate those observations to what you already know about Quicksort, in order to answer these questions.

• This animation makes heavy use of color (too heavy, perhaps -- if, for any reason, you have trouble distinsguishing the colors, let me know). In particular, bars may, at various times, be colored orange, purple, sky blue, dark blue, green, yellow, gray, and a dull blue-gray. The first questions deal with how the algorithm uses these colors...
  • What does an orange bar represent in this animation?
  • What does a purple bar represent in this animation?
  • What does a sky blue bar represent in this animation?
  • What does a dark blue bar represent in this animation?
  • What does a green bar represent in this animation?
  • What does a yellow bar represent in this animation?
  • What does a gray bar represent in this animation?
  • What does a blue-gray bar represent in this animation?
• The purpose of an algorithm animation, of course, is to help you understand an algorithm. The next set of questions therefore deal with how Quicksort's behavior translates into observable patterns in the animation, and vice versa...
  • At the highest level, Quicksort does two things: partition (part of) an array, and recursively sort the partitions. Does the animation spend more time showing one of these things than the other? Why?
  • Sometimes the animation will mark a number of items as becoming "sorted" without any apparent action on the part of the algorithm (the data set that the algorithm sorts by default when you first load the Web page shows this behavior). What, in terms of how Quicksort works, makes this happen?
• This particular animation allows you to input your own data for the algorithm to run on. To do this, type data values in the text box just above the control buttons; separate values with spaces. In the final set of questions, you need to use your understanding of Quicksort to come up with data sets on which the algorithm behaves in certain ways...
  • Devise a set of 15 data items that causes the first round of partitioning to split the array into "low" and "high" parts of exactly the same size (i.e., 7 items each).
  • Is it possible for this implementation of Quicksort of step the lower index for partitioning above the end of the array? If so, does this cause any problems (e.g., an "array index out of bounds" error)? If it is not possible, why not? Show a data set that causes the lower index to step past the end of the array if it is possible.
  • Is it possible for this implementation of Quicksort of step the higher index for partitioning below the start of the array? If so, does this cause any problems (e.g., an "array index out of bounds" error)? If it is not possible, why not? Show a data set that causes the higher index to step past the end of the array if it is possible.
  • In teams of two, try to find a set of 15 values that requires the least number of swaps for Quicksort to sort. (This is a competition, after a manner of speaking -- the team with the fewest swaps wins bragging rights and chocolate.)
  • In teams of two, try to find a set of 15 values that requires the largest number of swaps for Quicksort to sort (another competition, with the same prizes as above).

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.

Bring written answers to the questions to your grading appointment. If something isn't clear in an answer, or either of us wants to pursue it further as we talk, we can load and run the animation, but the quickest way to deal with most answers will be to have them in writing when we start.