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;
}
|