Ok guys... I'm sorta new to this forum.. so hello all.. but neways.. here is my problem.. This is the assignment I have:
http://www.ece.uc.edu/~berman/228-2003/program2.html
Can someone basically explain what I should do? Am I supposed to like sort part of it using insertionsort and the other part with one of the other 2? I'm confused as to this whole threshold thing.
Here is what I have so far:
/* Program 2
Author: B. Josh Becker
*/
#include <iostream> // preprocessor
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;
void mergesort(int[], int, int);
void merge(int[], int, int);
void quicksort(int[], int, int);
void choosePivot(int[], int, int);
void partition(int[], int, int, int&);
void insertionSort(int[], int);
void main(){
int numbers[200] = {0};
int response, choice,threshhold;
cout << endl << "Would you like to randomly choose a list or should I create one at random?" << endl;
cout << "\t1) Create one (less than 100 values)" << endl;
cout << "\t2) Random" << endl;
cin >> choice;
switch(choice){
case 1:
{
int number;
cout << endl << "Please enter the number of values you would like in the array (less than 100):";
cin >> number;
cout << endl << "Please enter each number followed by the return key" << endl;
if (number>100)
break;
for (int i=0;i<number;i++)
cin >> numbers[i];
cout << "Here are the numbers you just entered:" << endl;
for(i=0;i<number;i++)
cout << numbers[i] << " ";
break;
}
case 2:
{
int number;
cout << endl << "Please enter the number of values you would like in the array:";
cin >> number;
srand( (unsigned)time( NULL ) );
for(int i=0;i<number;i++)
numbers[i]=rand();
cout << "Here are the random values:" << endl;
for(i=0;i<number;i++)
cout << numbers[i] << " ";
break;
}
default:{
cout << "Sorry invalid value" << endl;
break;
}
}
cout << endl << "Please enter a threshold value:" << endl;
cin >> threshhold;
cout << "This program allows the user to sort numbers with different sorting methods" << endl;
cout << "Would you like to use :" << endl;
cout << "\t1) Quicksort" << endl;
cout << "\t2) Mergesort" << endl;
cout << "\t3) Insertionsort" << endl;
cin >> response;
}
// Start for Mergesort
void mergesort(int a[], int left, int right)
{
if(left<right)
{
int mid=(left + right)/2;
mergesort(a, left, mid);
mergesort(a, mid+1, right);
merge(a,left,right);
}
}
void merge(int a[],int left, int right)
{
int size=right-left+1,
mid=(left+right)/2;
int y, put;
int *b=new int[size];
int count=0;
for(int x=left;x<=mid;x++,count++)
{
b[count]=a[x];
}
for(x=right;x>=mid+1;x--,count++)
{
b[count]=a[x];
}
for(x=0,y=size-1,put=left;x<=y;put++)
{
if(b[x]<=b[y])
{
a[put]=b[x];
x++;
}
else
{
a[put]=b[y];
y--;
}
}
delete[] b;
}
// Start for quicksort
void choosePivot(int theArray[], int first, int last){
{
int pivotIndex;
int mid = (first + last) / 2;
if( theArray[ first ] <= theArray[ mid ] )
{ if( theArray[ mid ] <= theArray[ last ] ) pivotIndex = mid;
else pivotIndex = ( theArray[ first ] <= theArray[ last ] ? last : first );
}
else if( theArray[ last ] <= theArray[ mid ] ) pivotIndex = mid;
else pivotIndex = ( theArray[ first ] <= theArray[ last ] ? first : last );
swap( theArray[ first ], theArray[ pivotIndex ] );
}
}
void partition(int theArray[], int first, int last, int& pivotIndex)
{
choosePivot(theArray, first, last);
int pivot = theArray[first];
int lastS1 = first;
int firstUnknown = first + 1;
for (; firstUnknown<=last;++firstUnknown)
{
if (theArray[firstUnknown]<pivot)
{
++lastS1;
swap(theArray[firstUnknown],theArray[lastS1]);
}
}
swap(theArray[first], theArray[lastS1]);
pivotIndex = lastS1;
}
void quicksort(int theArray[], int first, int last)
{
int pivotIndex;
if (first<last)
{
partition(theArray, first, last, pivotIndex);
quicksort(theArray, first, pivotIndex-1);
quicksort(theArray, pivotIndex+1, last);
}
}
//Start insertion sort
void insertionSort(int theArray[], int n)
{
for (int unsorted=1;unsorted<n;++unsorted)
{
int nextItem = theArray[unsorted];
int loc = unsorted;
for (;(loc>0) && (theArray[loc-1]>nextItem);--loc)
theArray[loc] = theArray[loc-1];
theArray[loc] = nextItem;
}
}
