1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
|
#include <iostream>
#include <ctime>
using namespace std;
template <class T>
void quickSort(T[], int, int);
template <class T>
int partition(T[], int, int);
template <class T>
void swap(T& val1, T& val2);
int const MaxElements = 10;
int main()
{
clock_t before;
clock_t after;
double result;
int counter;
int* arr;
int max[MaxElements];
int size = 0, start = 0, end = size - 1;
cout << "Enter size of set (At most 10 seperate inputs): ";
cin >> size;
arr = new int[size];
if (size >= MaxElements)
{
cout << "set size must be less than " << MaxElements << "\n";
system("PAUSE");
exit(1);
}
for (int i = 0; i < size; i++)
{
cout << "Input value:";
cin >> arr[i];
}
cout << "Numbers Entered: ";
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
end = size - 1;
before = clock();
quickSort(arr, start, end);
after = clock();
cout << endl << "Numbers Sorted: " << endl;
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl << "Comparisons: " << counter << endl;
result = static_cast<double>(after - before) / CLOCKS_PER_SEC;
cout << "It took " << result << " milliseconds" << endl;
return 0;
}
template <class T>
void swap(T & val1, T & val2)
{
int temp = val1;//putting value 1 in a temp container
val1 = val2;
val2 = temp;
}
template <class T>
int partition(T arr[], int start, int end)
{
int counter = 0;
int pivot = arr[end];//choosing our pivot at the end of the array of numbers (you can choose the pivot in any postion)
int i = (start - 1);//do this to continue down the path of arrays
for (int j = start; j <= end - 1; j++)//j begins at the start of the arry and when. Now we compare the j to the pivot and move on
{
counter++;//counting comparisons
if (arr[j] <= pivot)//current value being scanned is smaller than or equal to pivot
{
i++;//increment index
swap(arr[i], arr[j]);//swap the two values of i and j
}
}
swap(arr[i + 1], arr[end]);//swaping the pivot now infront of where the i is hence the +1
return(i + 1);//returning the info
}
template <class T>
void quickSort(T arr[], int start, int end)
{
if (start < end)//if the starting point is less than the pivot
{
int pi = partition(arr, start, end);
quickSort(arr, start, pi - 1);
quickSort(arr, pi + 1, end);
}
}
|