#include <iostream>
#include <algorithm>
#include <ctime>
#include <fstream>
#include <cstdlib>
using namespace std;
//functions used for sorts
void generateSortedArray(int arraySize, int*& sortedArray);
void generateReversedArray(int arraySize, int*& reversedArray);
void generateRandomArray(int arraySize, int*& randomArray);
int insertionSort(int arraySize, int array[]);
void sort(int arraySize, int*& sortedArray, int*& reversedArray, int*& randomArray, int algoChoice, int sortChoice);
void quickSort(int *array, int left, int right);
int partition(int *array, int left, int right);
void printArray(int arraySize, int *array);
int main()
{
//declaration of variables to be used throughout program
char answer;
int arraySize = 0,algoChoice = 0, sortChoice = 0;
//initialization of pointer arrays
int *sortedArray = NULL;
int *reversedArray = NULL;
int *randomArray = NULL;
randomArray = new int [arraySize];
sortedArray=new int[arraySize];
reversedArray=new int[arraySize];
cout << "Enter the number of elements in the array: ";
cin >> arraySize;
cout << endl;
//used 6500 since 6400 is the highest my computer will calculate
while(arraySize >= 0 && arraySize <=6500)
{
cout << "What algorithm would you like to use (1 = insertion 2 = quicksort): ";
cin >> algoChoice;
cout << endl;
//breaks into the switches
sort(arraySize, sortedArray, reversedArray, randomArray, algoChoice, sortChoice);
cin >> answer;
//if the user wants to calculate another sort, they just enter y
if(answer =='y')
{
cout << "Enter the number of elements in the array : ";
cin >> arraySize;
cout << endl;
}
else
return -1;
}
//deallocation of memory
delete [] randomArray;
delete [] reversedArray;
delete [] sortedArray;
return 0;
}
void generateSortedArray(int arraySize, int*& sortedArray)
{
//sets range for elements
for(int i=
0; i<arraySize; i++
) {
sortedArray[i] = (rand() % arraySize)+1;
}
//sorts in ascending order
int temp;
int counter, index;
for (counter = 0; counter < arraySize - 1; counter++)
{
for (index = 0; index < arraySize - 1 - counter; index++)
if (sortedArray[index] > sortedArray[index+1])
{
temp = sortedArray[index];
sortedArray[index] = sortedArray[index+1];
sortedArray[index+1] = temp;
}
}
}
void generateReversedArray(int arraySize, int*& reversedArray)
{
for(int i=
0; i<arraySize; i++
) {
reversedArray[i] = (rand() % arraySize)+1;
}
//code to reverse the elements
int temp;
int counter, index, flag = 1;
for (counter = 1; (counter <= arraySize) && flag; counter++)
{
flag = 0;
for (index = 0; index < (arraySize - 1); index++)
if (reversedArray[index+1] > reversedArray[index])
{
temp = reversedArray[index];
reversedArray[index] = reversedArray[index+1];
reversedArray[index+1] = temp;
flag =1;
}
}
}
void generateRandomArray(int arraySize, int*& randomArray)
{
for(int i=
0; i<arraySize; i++
) {
randomArray[i] = (rand() % arraySize)+1;
}
//shuffles elements in array
random_shuffle(randomArray , (randomArray + arraySize));
}
//The insertion sort splits an array into two sub-arrays.
//The first sub-array is always sorted and gets larger as the sort continues.
//The second sub-array is unsorted and contains all the elements not yet inserted into the first sub-array.
// The second sub-array gets smaller as the sort progresses
int insertionSort(int arraySize, int *array)
{
int i,j,key;
for(j=
1; j<arraySize; j++
) {
key=array[j];
i=j-1;
while(array[i]>key && i>=0)
{
array[i+1]=array[i];
i--;
}
array[i+1]=key;
}
return 0;
}
//This sort starts by dividing the original array into two sections (partitions) based upon the value of the first item in the array.
//the first section will contain all the elements with values less than the first item.
//The second section will contain elements with values greater than (or equal to) the first element
void quickSort(int *array, int left, int right)
{
int middle;
if(left<right)
{
middle=partition(array, left, right);
quickSort(array,left,middle-1);
quickSort(array,middle+1,right);
}
} //end quicksort(...)
int partition(int *array, int left, int right)
{
//the variable "middle" is the pivot of the process
int middle = array[left];
int i = left;
int j = right+1;
do
{
do
{
++i; //increment i while the array element is less than the pivot and decrement j while it's greater.
}while(array[i]<middle);
do --j; while(array[j]>middle);
if(i<j)//if i is less than j swap the elements
swap(array[i], array[j]);
}
while(i<j);
swap(array[j], array[left]);
return j;//returns middle index
}
//main code
void sort(int arraySize, int*& sortedArray, int*& reversedArray, int*& randomArray, int algoChoice, int sortChoice)
{
//the clock variables, start and end, are used to time the execution for every sort
clock_t start, end;
//algorithm choice = insertion sort
if (algoChoice == 1)
{
cout << "What sorting would you like to use: (1=sorted, 2=reversed, 3=random): ";
cin >> sortChoice;
switch(sortChoice)
{
//ascending array
case 1:
generateSortedArray(arraySize, sortedArray);
start = clock();
insertionSort(arraySize, sortedArray);
end = clock();
cout << endl;
cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << "Writing contents of sorted array to sorted2^15.out" << endl;
printArray(arraySize, sortedArray);
break;
case 2:
//user selects 2: elements in descending order
generateReversedArray(arraySize, reversedArray);
start = clock();
insertionSort(arraySize, reversedArray);
end = clock();
cout << endl;
cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << "Writing contents of sorted array to sorted2^15.out" << endl;
printArray(arraySize, reversedArray);
break;
case 3:
//user selects 3: elements are randomized
generateRandomArray(arraySize, randomArray);
start = clock();
insertionSort(arraySize, randomArray);
end = clock();
cout << endl;
cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << "Writing contents of sorted array to sorted2^15.out" << endl;
printArray(arraySize, randomArray);
break;
default:
//user selects anything other than 1-3, this error prints
cout << "Invalid choice of sort" << endl;
break;
}
cout << endl;
cout << "Do you want to test again? ";
//end switch(sortChoice)
} //end if (algoChoice == 1)
//choice 2 = quicksort
else if (algoChoice == 2)
{
cout << "What sorting would you like to use: (1=sorted, 2=reversed, 3=random): ";
cin >> sortChoice;
switch(sortChoice)
{
//the left cell chosen will obviously be 0 since it's the first element of the array. the right
//element is the array size minus 1 since arrays start at 0.
case 1:
generateSortedArray(arraySize, sortedArray);
partition(sortedArray, 0, arraySize-1);
start = clock();
quickSort(sortedArray, 0, arraySize-1);
end = clock();
cout << endl;
cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << "Writing contents of sorted array to sorted2^15.out" << endl;
printArray(arraySize, sortedArray);
break;
case 2:
generateReversedArray(arraySize, reversedArray);
partition(reversedArray, 0, arraySize-1);
start = clock();
quickSort(reversedArray, 0, arraySize-1);
end = clock();
cout << endl;
cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << "Writing contents of sorted array to sorted2^15.out" << endl;
printArray(arraySize, reversedArray);
break;
case 3:
generateRandomArray(arraySize, randomArray);
partition(randomArray, 0, arraySize-1);
start = clock();
quickSort(randomArray, 0, arraySize-1);
end = clock();
cout << endl;
cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << "Writing contents of sorted array to sorted2^15.out" << endl;
printArray(arraySize, randomArray);
break;
default:
cout << "Invalid choice of sort" << endl;
break;
}
cout << endl;
cout << "Do you want to test again? ";
//end switch(sortChoice)
} //end else if(algoChoice == 2)
else
cout << "Invalid algorithm choice" << endl;
}
//had trouble sending out to file. it would only send within 100-200 elements.
//couldn't find out why
void printArray(int arraySize, int *array)
{
ofstream outFile;
outFile.open("C:/Documents and Settings/user/My Documents/sorted2^15.out");
for(int i=0; i< arraySize; i++)
{
outFile << array[i] << " ";
if (i%8==0)
outFile << endl;
}
}
Offline 
Marked 
