CSE326 Sorting Exercise
Spring 2002

Due: Friday, April 12, 2001, at 5:30 PM.
  Electronic turn-in!

Reading in Lewis & Denenberg:

• Sections 2.2 (skip Expected-case and Amortized Analysis), 11.1, 11.2, 11.3 (Selection sort only), 11.4.

Programming

1. Set up your account (see below), get the sorts project (see Getting the Project below for details), and go through the tutorial.

2. Use randseq and the -t option to sorts to find the crossover point where Shell sort does better than Selection sort. Create a README file, and write a paragraph of your conclusions.

3. Implement Merge and Insertion sort, using sorts.C as a framework. Make sure they work correctly. Feel free to base your implementations on pseudocode from class or the textbook.

   You only need modify sorts.C. In case you're interested, I've included all the source code, but you don't need to look at it.

4. Find the crossover point where Merge sort does better than Insertion sort. Add your conclusions to the README file.

5. Extra-Credit: Write Quicksort. Compare Merge sort, Quicksort and the included Shell sort. Include your conclusions in README.

6. Turn in your assignment electronically, before the due-date. See Turnin Info for how to turn in; the project name is sorts.

1. After unpacking the sorts project (see below for details), make sorts. Play around with the resulting executable. (see hints)

2. The program randseq is in the course bin/ directory, which is in your path if you've set up your shell as described below. Play around with this program.

3. sorts expects a sequence on stdin, and randseq produces a sequence on stdout. To plug the output of randseq into sorts, use randseq | sorts (that is, type randseq, followed by a vertical bar, followed by sorts). This is known as piping the output of randseq into sorts. Try this, for a few of the different sorting routines.

   Open up a new file in the editor of your choice named, for example, seq1. Type in a short sequence suitable to input to sorts (i.e., a sequence of numbers preceded by the length of the sequence). For example:
        5 5 4 3 2 1
   Now try:
        sorts < seq1
   This causes sorts to get stdin from seq1.

4. Try timing sorts on larger inputs. For example,
        randseq -l 100 | sorts -t
   Try some other sorting methods.
        randseq -l 100 | sorts -t -l
   Note that you can combine the switches for sort: sorts -tl does the same thing as sorts -t -l. The timing output is in microseconds, abreviated usec (u is used because it is the closest English letter to the Greek letter mu, which is the standard abbreviation for micro).

5. Now on to debugging and compiling. From the command line, type ddd sorts to start up a debugger on the executable sorts. ddd-info from the command line will give more documentation (type info info to learn how to use the info system).

   The most common debugging tasks are displaying variables, setting breakpoints, and controlling execution. To display a variable, right-click on the variable in code and select Display. Everything that is displayed will appear in a separate pane; you can rearrange objects in that pane by clicking and dragging; right-clicking lets you modify them. For more complicated variables, you may need to select what you want to display first.

   To set a breakpoint at a function, right-click on the function name and select Break at. To set a breakpoint at a line, left-click to set the line, then right-click and select Set Breakpoint.

   The floating button bar lets you control your program's execution. Run runs a program from the beginning. Step steps the program, going into function calls. Next steps the program, stepping over function calls. Cont (continue) runs the program from its current point. Interrupt stops the program, useful if you've gotten into an infinite loop.

   To debug sorts, you'll need to arrange for the debugger to provide an input sequence. Go to Program...Run. In the Run with arguments box, type < file, where file is an input file like seq1, above. Then hit Run to start your program. Note that this is just filling in the rest of the command line you used to invoke sorts outside of ddd.

   You can also make files using randseq from the command line.
       randseq -l 50 > file
   Here file is the filename of your choice, and of course you can replace 50 with any other number.

6. The easiest way to compile projects is to use makefiles. You'll learn more about these over the course of the quarter. For now, note that you can build by typing make sorts at the command line. make can also be invoked from inside emacs, which can then jump to the location of compile errors, making fixing them easier.

• Try sorts -h.
• Try C-c if the program appears to hang (C-c means "Control-c").
• randseq has a -h flag as well.