SUNY Geneseo Department of Computer Science

Lab 8 -- Quicksort

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Tuesday, March 27


This lab is intended to help you understand how Quicksort works.


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.


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 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.


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.