CS14 Program 4

Assigned: May 24^th, 2002

Due: Friday, June 7^th, 2002 11pm

Important: This program has two parts. Both have to be completed, and both are due on the same day. The two parts are independent; you can start with either one. Please note that the two parts have to be turned in separately. There are two different turnins; you will need to select the correct one. Programs turned into the wrong directory will not be graded. Please play close attention: when you go to the turnin page, the default assignment is Heap, which is part 1 of this program. To turn in part 2, you will need to click on the down arrow to the right of the assignment name, and select Sort from the menu that shows up. The menu also includes Xtra, which is for the extra credit assignment.

Topics

· Sorting

· Timing programs

· Comparison of running times of different algorithms on different data

The data

Both parts of this assignment involve writing programs that read in many numbers and sort them. Please adhere to the following rules about the input.

1. Do not solicit user input.
2. All data should be read in using a loop that reads in numbers until there are no more. The loop looks like this:

while (cin << num)

{ }

3. When entering numbers from the keyboard, the loop terminates when the input is Control-D (Linux) or Control-Z (Visual)
4. For large amounts of data, entering from the keyboard is not practical. If the numbers you wish to sort are in a file (they are), you can redirect the input to come from the file, like this (Linux only):
1. If your executable is called mysort, and the input is in file infile, type

mysort < infile

2. Every cin << num statement will look for input in the file rather than the keyboard.
3. The loop will terminate when end-of-file is reached.
4. Please use redirection (the method just described) when you read data from files. Do not hardwire file names into your program. Do not ask the user for the names of files.

Part I – Heapsort

In this part of the program, you will use a heap to sort numbers in three different ways. Two involve a heap class that you write. The third uses STL.

First, you will need to write a heap class. The heap should be implemented in an array, as described in class and in chapter 11 of your book.

Operations on the heap include

• Heap() – constructor. Allocate enough room to accomodate the largest amount of data.
• ~Heap() – destructor.
• getSize() – returns how may numbers are in the heap.
• isEmpty() – true if the heap is empty.
• insert(int num) – insert num into the heap
• extractMax() – removes the largest number from the heap and returns it
• buildHeap() – reads in numbers and builds a heap by filling the array, then repeatedly calling reHeap(i) with i going from n/2 to 0.
• sort() – sorts the heap and prints out the sorted array. Note that the sort destroys the heap; when done, the array is sorted but the heap is empty.
• bubbleUp() – private auxiliary function for insert. Takes a heap + one new number at its end and converts it into a heap by bubbling the number up to its correct position in the heap
• reHeap(int) – private auxiliary function for deleteMax. Takes an array that is almost a heap except for maybe the root and reheaps it.

After you have your heap class, write two programs that use the heap to sort in subtly different ways:

The first program will read in numbers in the main and insert them one by one into the heap. It will then call sort() to sort and print the numbers in the heap.

The second program will declare a Heap object, then call buildHeap() and sort(). All input is done inside buildHeap().

The two programs differ only in the way that the heap is created.

The third program you write in this part uses the STL class priority_queue (which is actually a composite of queue and vector). There is a sample program that uses it in sample.cpp that you are welcome to cannibalize. The program should read in the numbers, inserting them one by one into the priority_queue, then print them in sorted order by printing the top (root) and extracting it until the priority_queue is empty.

The Data

Data files are in the directory ~deganit/cs14/heap. This is a directory, not a web page. You can redirect the files right from there. Like this

heap1 < ~deganit/cs14/heap/h1

Or, you can download the files from here and clutter up your own diskspace.

To Do

· Write the heap sorting programs

· Time your programs on each of the data files. Provide a README text file (no Word files please) that has the timing data in a table (rows are the programs, columns are data files).

· Add a short paragraph after your data explaining the results. Is this what you expected? Does the data make sense?

What to turn in

· All your .h and .cpp files

· A makefile that compiles all your programs when you type

make all

and creates executables called

heap1

heap2

heap3

· README

Part II – Comparing Sorting Algorithms

Write programs to sort numbers using each of the following algorithms

· Insertion sort

· Sort using a tree (you should have one lying around)

· Quicksort

· (Bonus) RadixSort

· (Bonus) ShellSort

The Programs

Each program will read numbers from a file and sort them.

The Data

Data files are in the directory ~deganit/cs14/sort. This is a directory, not a web page. You can redirect the files right from there. Like this

sort1 < ~deganit/cs14/sort/s1

Or, you can download the files from here and clutter up your own diskspace.

To Do

· Write the sorting programs

· Time your programs on each of the data files. Provide a README text file (no Word files please) that has the timing data in a table (rows are sorting algorithms, columns are data files).

· Add a short paragraph after your data explaining the results. Is this what you expected? Does the data make sense?

What to turn in

· All your .h and .cpp files

· A makefile that compiles all your programs when you type

make all

and creates executables called

sort1

sort2

sort3

· README

Please make sure you name, login and lab section appear in at least one of your files.

There is a two hour grace period after the turnin time. No late programs will be accepted after the grace period. Turn in what you have before 11pm to ensure at least partial credit.