0

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;
	}
}
2
Contributors
1
Reply
3
Views
14 Years
Discussion Span
Last Post by Wiecek5
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.