Fall 2000 PIC 10b HW6 Solutions Page

Return to homework page.

//
//
// File: pic10bhw6file1.cpp
//
// Contents: program to test and implement a three-way recursive merge sort
//

#include<iostream>

//
// Global Constants
//
static const int SIZE = 1000; //max size of array to be sorted

//
// Functions Prototypes
//

template <class Item>
void mergesort(Item a[], int l, int r); //algorithm to sort an array between
                                        //indices l and r using 3-way mergesort

template <class Item>
void mergeABC(Item d[],int l,int t1,int t2,int r);
				//merges the three subarrays of d given by
                                //d[l]..d[t1] and d[t1+1]..d[t2] and d[t2+1]
                                //..d[r].
// Function name: main()
//
// Purpose: Driver program to test 3-way merge sort algorithm
//          first gets data to sort into an array. Then calls the sorting
//          algorithm and prints out the results.  
//
// Known Bugs: none
int main()
{
	bool flag = true;
	int a[SIZE], cnt=0;
	char c;

	//
	//Print intro
	//
	
	cout << "\nHello, I'm the nifty 3-way sorting program\n";
	cout  << "==========================================\n\n";

	cout<< "Please enter some numbers to be sorted.\n";

	//
	// get data into array
	//

	while(flag && cnt < SIZE)
	{
	  flag=false;
    
          cout << "\nEnter number"<< cnt+1 << ":\n";
	  
	  cin >> a[cnt];

	  cout << "\nWould you like to enter another number (y/n)?\n";
	  cin >> c;
	  if(c=='y') flag =true;
	
	  cnt++;
	}

	//
	//sort the data
	//

	mergesort(a,0,cnt-1);

	//
	//Print it out
	//

	cout<<"\nSorting the numbers you entered yields:\n";
	for(int i=0; i < cnt; i++)
	  cout << a[i] << endl;

	return 0;
}

// Function name: mergesort
//
// Purpose: sort array a[] between
//          indices l and r using 3-way mergesort
//
// Known Bugs: none

template <class Item>
void mergesort(Item a[], int l, int r)
{
	if(r<=l) return; //if one item then sorted already

	if(l+1 == r) //if two items compare and swap if necessary 
	{
		if(a[l] > a[r]) 
		{
		   int t=a[l];
		   a[l] = a[r];
		   a[r] = t; 
		}
		return;
	}

	//
 	// Three or more items
	//

	int delt= (r-l+1)/3, m1= l+delt-1, m2=r-delt;
	
	mergesort(a, l, m1);
	mergesort(a, m1+1, m2);
	mergesort(a, m2+1, r);

	mergeABC(a, l, m1, m2, r);	
}

// Function name: mergeABC
//
// Purpose: merges the three subarrays of d given by
//          d[l]..d[t1] and d[t1+1]..d[t2] and d[t2+1]..d[r]
//
// Known Bugs: could avoid copying into aux before merging
//             if used stuff we did not covered in Sedgewick

template <class Item>
void mergeABC(Item d[],int l,int t1,int t2,int r)
{
	static Item aux[SIZE]; //temporary array used in merging

	int i,j=t1+1,k=t2+1, min, *t;
	int auxj,auxk;

	for(i=r+1; i>l; i--)
		aux[i-1]=d[i-1];

	for(int m=l; m<=r; m++)
	{
	  auxj = aux[j]; auxk = aux[k]; //to avoid multiple computations of
                                        //what aux[j] and aux[k] are
               
          min= auxj*auxj+auxk*auxk; //start min off larger than auxj and auxk

	  if(i<=t1) {min = aux[i]; t=&i;} //t stores address of either i,j,k
                                          //depending on which of aux[i],
                                          //aux[j], and aux[k] is the smallest

	  if(auxj < min && j<=t2) {min = auxj; t=&j;}
          if(auxk < min && k<=r) {min = auxk; t=&k; }

	  d[m]=min;
	  (*t)++;
	}
		
}

//
//
// File: pic10bhw6file2.cpp
//
// Contents: program to test and implement a tree sort algorithm
//

#include<iostream>
#include<cstddef>

//
//
// struct's
//
//
				    

// Struct Name: node
// Purpose: our struct for a binary tree
//          node.
// 
// Known Bugs: none
template<class Item>
struct node 
{
	Item item; 
	node<Item> *l, *r;
	node(Item i, node<Item> *left, node<Item> *right) 
			{item=i; l=left; r=right;}  
}; 

//
// Global Constants
//
static const int SIZE = 1000; //max size of array to be sorted

//
// Functions Prototypes
//

template <class Item>
void treesort(Item a[], int l, int r); //algorithm to sort an array between
                                        //indices l and r using treesort

template <class Item>
void InsertNode(node<Item> *curNode, node<Item> *newNode);

template<class Item>
Item *InOrderCopy(node<Item> *curNode, Item *arr);


// Function name: main()
//
// Purpose: Driver program to test 3-way merge sort algorithm
//          first gets data to sort into an array. Then calls the sorting
//          algorithm and prints out the results.  
//
// Known Bugs: none
int main()
{
	bool flag = true;
	int a[SIZE], cnt=0;
	char c;

	//
	//Print intro
	//
	
	cout << "\nHello, I'm the nifty tree sorting program\n";
	cout  << "=========================================\n\n";

	cout<< "Please enter some numbers to be sorted.\n";

	//
	// get data into array
	//

	while(flag && cnt < SIZE)
	{
	  flag=false;
    
          cout << "\nEnter number"<< cnt+1 << ":\n";
	  
	  cin >> a[cnt];

	  cout << "\nWould you like to enter another number (y/n)?\n";
	  cin >> c;
	  if(c=='y') flag =true;
	
	  cnt++;
	}

	//
	//sort the data
	//

	treesort(a,0,cnt-1);

	//
	//Print it out
	//

	cout << "\nSorting the numbers you entered yields:\n";
	for(int i=0; i < cnt; i++)
	  cout << a[i] << endl;

	return 0;
}

// Function name: treesort
//
// Purpose: sort array a[] between
//          indices l and r using treesort
//
// Known Bugs: none

template <class Item>
void treesort(Item a[], int l, int r)
{
	if(r<=l) return; //if one item then sorted already
	
	node<Item> *root = new node<Item>(a[l], NULL, NULL); 
                                //put a[l] as root of tree 	
	node<Item> *tmp;

	//
	// Insert nodes into binary tree
	//
	for(int i=l+1; i <= r; i++)
	{
		tmp = new node<Item>(a[i], NULL, NULL);
		InsertNode(root,tmp);
	}

	//
	// Do an in order traversal and copy items back from tree
	//

	InOrderCopy(root,a);

}

// Function name: InsertNode
//
// Purpose: assuming that curNode is the root node of a binary tree, 
//          this function inserts the node newNode into this tree.
//
// Known Bugs: probably better to have this as part of a binary search tree
//             class

template <class Item>
void InsertNode(node<Item> *curNode, node<Item> *newNode)
{
	node<Item> **child;

	//
	// First we find under which subtree newNode belongs
	//

	child = (newNode->item < curNode->item) ? &(curNode->l)
	                                         : &(curNode->r);

	//
	//if curNode's appropriate subtree is an external
	//node than we just afix newNode instead.
	//

	if(*child == NULL) {*child = newNode; return;}

	//
	//Otherwise, we do the insert into the appropriate subtree
	//

	InsertNode(*child, newNode);
}

// Function name: InOrderCopy
//
// Purpose: copies using an inorder traversal, the binary
//          tree stored at curNode into array location pointed to by arr
//
// Known Bugs: none

template<class Item>
Item* InOrderCopy(node<Item> *curNode, Item *arr)
{
	Item *arrAdvance=arr;

	if(curNode->l != NULL) arrAdvance= InOrderCopy(curNode->l,arr);

	*arrAdvance = curNode->item;
	arrAdvance++;
	
        if(curNode->r != NULL) arrAdvance= InOrderCopy(curNode->r, arrAdvance);

	return arrAdvance;
}