All the Fast Sorts

				
//**************************************
// Name: All the Fast Sorts
// Description:Has all the fast sorts and times it
// By: Abid Kapadya
//
// Inputs:Size of vector, what u want each element to b(in MAX)
//
//This code is copyrighted and has// limited warranties.Please see http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=3480&lngWId=3//for details.//**************************************

/////////////////////////////
// Sorting Template Program
//
// Author: Abid Kapadya
// Date: 2.26.02
// Period: 4
//
#include <iostream.h>
#include <iomanip.h>
#include <winSIOUX.h>
#include "SysTimer.h"// used for timing
#include "apstring.h"
#include "randgen.h"
#include "apvector.h"
void fillArray (apvector<int> &nums);
void screenOutput (const apvector<int> &nums);
void sortMenu (apvector<int> &nums);
template <class typeReplacedAtComileTime>
void swap (typeReplacedAtComileTime &a, typeReplacedAtComileTime &b);
void selectionSort (apvector<int> &list);
void insertionSort (apvector<int> &list);
void mergeSort(apvector<int> &list, int first, int last);
void quickSort (apvector<int> &list, int first, int last);
void merge(apvector<int> &a, int first, int mid, int last);
int findPosOfSmallest( apvector<int> list, int from, int to );
int main()
{
// Set the window to close when the application quits.
SIOUXSettings.autocloseonquit=true;
// Set the window to NOT display the save dialog when it quits
SIOUXSettings.asktosaveonclose=false;
apvector<int> list;
sortMenu(list);
return 0;
}
void fillArray (apvector<int> &nums)
/* Asks the user for two inputs: 1) the number of data to generate, and
2) the largest possible random integer to create. Then proceeds to fill
the array, from 1..number */
{
RandGen randGetter(100);// seed used so we all get same series of
// random numbers, this is good for comparison reasons
int numToGenerate,largestRand;
	cout << "Enter the number to generate up to(inclusive): ";
	cin >> numToGenerate;
	cout << "Enter the largest possible random integer to create: ";
	cin >> largestRand;
	
	nums.resize(numToGenerate);
	
	for( int i=0; i<numToGenerate; ++i )
	{
		nums[i]=randGetter.RandInt(0,largestRand);
	}
}
void screenOutput (const apvector<int> &nums)
// prints out the contents of the array in tabular form, 12 columns
{
cout << setiosflags( ios :: right );
for( int x=0; x<nums.length(); ++x )
{
	if( x%12 == 0 ) // 12 columns
		cout << endl;
	cout << setw(6) << nums[x] << " ";
}
}
//you can send this swap function two objects of ANY datatype and it'll "swap" them
template <class typeReplacedAtComileTime>
void swap (typeReplacedAtComileTime &a, typeReplacedAtComileTime &b)
{
typeReplacedAtComileTime temp = a;
a = b;
b = temp;
}
void selectionSort (apvector<int> &list)
{
	
	int N=list.length(), posOfSmallest;
	
	cout << endl << "SELECTION_SORT" << endl << endl;
	
	for( int outer=0; outer<N-1; outer++ )
	{
		posOfSmallest = findPosOfSmallest( list, outer, N-1 );
		swap( list[outer], list[posOfSmallest] );
	}
}
int findPosOfSmallest( apvector<int> list, int from, int to )
{
int smallestPos=from, i;
for(i=from+1; i<=to; i++)
{
	if( list[i]<list[smallestPos] )
		smallestPos=i;
}
return smallestPos;
}
	
void insertionSort (apvector<int> &list)
{
int pos;
for( int i=1; i<list.length(); ++i )
{
	pos = i;
	
	while( (pos>0) && ( list[pos-1]>list[pos] ) )
	{
		swap( list[pos-1], list[pos] );
		pos--;
	}
}
}
void mergeSort(apvector<int> &list, int first, int last)
{
int mid;
if (first == last)
;// empty case; only 1 value; do nothing
elseif (1 == last - first) // list of 2 values, swap if necessary
{
if (list[first] > list[last])
swap (list[first], list[last]);
}
else// general (recursive) case
{
mid = (first+last) / 2;
mergeSort (list, first, mid);
mergeSort (list, mid+1, last);
merge (list, first, mid, last);
}
}
void merge(apvector<int> &a, int first, int mid, int last)
/* Takes in entire vector, but will merge the following sections
together: Left sublist from a[first]..a[mid], right sublist from
a[mid+1]..a[last]. Precondition: each sublist is already in
ascending order */
{
int aPtr=first, bPtr=mid+1, cPtr=first;
int total=last-first+1, loop;
bool doneA = false, doneB = false;
apvector<int> c(a.length());
for (loop=1; loop<=total; loop++)
{
if (doneA)
{
c[cPtr] = a[bPtr];
bPtr++;
}
else
if (doneB)
{
c[cPtr] = a[aPtr];
aPtr++;
}
else// ok to compare, valid data in each sublist
if (a[aPtr] < a[bPtr])
{
c[cPtr] = a[aPtr];
aPtr++;
}
else
{
c[cPtr] = a[bPtr];
bPtr++;
}
cPtr++;
if (aPtr > mid) doneA = true;
if (bPtr > last) doneB = true;
}// for loop
for (loop=first; loop<=last; loop++)
a[loop] = c[loop];
}
void quickSort (apvector<int> &list, int first, int last)
{
int g = first, h = last;
	int midIndex, dividingValue;
	midIndex = (first + last) / 2;
	dividingValue = list[midIndex];
	do
	{
		while (list[g] < dividingValue) g++;
		while (list[h] > dividingValue) h--;
		if (g <= h)
		{
			swap(list[g], list[h]);
			g++;
			h--;
		}
	}
	while (g < h);
	if (h > first) quickSort (list,first,h);
	if (g < last) quickSort (list,g,last);
}
void sortMenu (apvector<int> &nums)
{
char choice;
apstring junk; // used to pick up endl, then ignore it
fillArray(nums);
apvector<int> holdOriginal(nums);// want to use the original unsorted
// vector each time we sort and count
SysTimer clock;
do
{
cout << "Sorting algorithm menu" << endl << endl;
cout << "(1) Selection sort" << endl;
cout << "(2) Insertion sort" << endl;
cout << "(3) Recursive mergesort" << endl;
cout << "(4) Quicksort" << endl;
cout << "(5) Print Vector" << endl;
cout << "(6) Quit" << endl << endl;
cout << "Choice ---> ";
cin >> choice;
getline(cin, junk); // dump endl
if (choice != '5')
nums = holdOriginal;// reset vector so we can again sort the same original unsorted data
if ('1'<=choice && choice<='5')
{
	clock.start();
// START YOUR TIMER HERE (figure out and use systimer class)
switch (choice)
{
case '1' : selectionSort(nums); break;
case '2' : cout << endl << "INSERTION_SORT" << endl << endl;
insertionSort(nums); break;
case '3' : cout << endl << "MERGE_SORT" << endl << endl;
mergeSort(nums, 0, nums.length()-1); break;
case '4' : cout << endl << "QUICK_SORT" << endl << endl;
quickSort(nums, 0, nums.length()-1); break;
case '5' : screenOutput(nums); break;
}
// STOP YOUR TIMER HERE and print elapsed time with appropriate message
// but don't print time if option 5 was chosen
clock.stop();
if( choice >='1' && choice<='4' )
	cout << clock.elapsedTime();
clock.reset();
		
cout << "\n\nPress ENTER To go on ...";
getline(cin, junk);
clrscr();
}
else if (choice != '6')
{
clrscr();
cout << "Can you read? Try Again!\n";
}
}
while (choice != '6');
}