PIC 10b Fall 2000 HW #6

Homework FAQ.

Solution set.

Due date: Dec. 8. Lecture 1's due time is:  5:30pm. 
=========         Lecture 2's due time is:  noon.

Reading Assignment: Reading in Sedgewick. Finish 6.1-6.4, 8.1, 8.3, 14.1-14.2
===================
        
Files to submit:   pic10bhw6file1.cpp   - your sorting algorithm and driver
=================                 

HW6 Purpose: To learn more about recursion and sorting. Bottom up 
============ versions of n-way sorting are a common method of external
             sorting used in databases. On this homework you will
             implement a recursive 3-way sort algorithm.

General Instructions
====================
The file pic10bhw6file1.cpp should contain: (1) a driver function to get
numbers from the user then call the sorting function and print out the results, 
(2) a sorting function, and (3) a merge function. A session with the driver 
program looks like:

Hello, I'm the nifty 3-way sorting program
==========================================

Please enter some numbers to be sorted.

Enter number 1:
12

Would you like to enter another number (y/n)?
y

Enter number 2:
1

Would you like to enter another number (y/n)?
y

Enter number 3:
5

Would you like to enter another number (y/n)?
n

Sorting the numbers you entered yields:
1
5
12

The sorting function should have the prototype:

template <class Item>
void mergesort(Item a[], int l, int r);

Unlike the mergesort in program 8.3 in Sedgewick your program should
split a[] into three almost equal sized parts, sort these parts and
merge the three results.

The merge function should have the prototype:

template <class Item>
void mergeABC(Item d[],int l,int t1,int t2,int r);

mergeABC merges the subarrays of d between l and t1, t1 and t2, and t2 and
r.




HW6 Point Breakdown
=======================
If the submit program didn't collect your file
because you misnamed it or you did not follow
the required formatting instructions in the syllabus
you will get a 0 without an opportunity for a regrade.


How well your code is commented.........1pt.
Driver program gets data correctly......1pt.
Driver program calls sorting algorithm
    correctly...........................1pt.
Driver program prints out result 
correctly...............................1pt
mergesort partitions data set into three
parts as asked..........................1pt.
mergesort sorts data correctly..........1pt.
mergeABC works..........................2pts
============================================
Total...................................8pts


Bonus: 2 pts.
======

Write another program called pic10bhw6file2.cpp.
This file contains a driver program like in the regular
assignment, but calls a different sorting algorithm.
This sorting algorithm first inserts all of the items
in the array to be sorted into a binary search tree.
Then it does a in-order traversal of this tree copying
the nodes it visits back into the original array.
The driver program then prints out this sorted array.

Additional explanations
=======================

A binary seach tree is a binary tree with the property that
it is either a node or it is a tree whose left and right subtrees are binary 
search trees and its root is greater than all the values stored in
its left subtree and less than or equal to all the values in its right subtree.


For example,


               5
              / \
             /   \
	    /     \
           3       7
            \
             4

is a binary search tree, but


            5
           / \
          /   \
         /     \
        4       7
         \
          3

is not since 4 > 3 but 3 is in the right subtree of 4.

To insert a node in a binary search tree start at the root than go left or right
down the tree depending on whether or not the value you are inserting is
larger than the value stored in the current node. For instance to store
6 in the tree


               5
              / \
             /   \
	    /     \
           3       7
            \
             4

We would start at 5 then go to the right subtree since 6>=5 then we'd
go to the left subtree of 7 since 6<7. As this is a null subtree
we create a new node with 6 in it and hang it to the left of the node with the
7. So we get:


               5
              / \
             /   \
	    /     \
           3       7
            \     /
             4   6


If we want to insert another 3 and another 7 we'd get the tree.

               5
              / \
             /   \
	    /     \
           3       7
            \     / \
             4   6   7
            /
           3

i.e., There can be values in the right subtree equal to the root. Notice
an in-order traversal of the above give 3 3 4 5 6 7 7 which is sorted.

This kind of sorting is called tree sort. For the "typical" unsorted array,
each insert will take expected time O(log N). So N insert takes O(NlogN) time.
The traversal can be done in O(N) time so the whole algorithm is
O(NlogN) on average.