Having trouble getting the QuickSort to work in this code. I turned off the counter for now, just trying to get the sorted array to display correctly. This is the results I get from the code:
This program keeps track of the number of comparisons required to
to sort a randomly generated array array.
How large do you want the array to be? 4
Array to be sorted is:
677 419 981 377
The sorted array is:
-858993460 -858993460 -858993460 -858993460 Press any key to continue . . .
Here is the code I'm using
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib> // For random
using namespace std;
class AbstractSort
{
public:
void QuickSort(int arr[], int s, int e);
int getComparisonCount()
{
return comparisonCount;
}
void resetComparisonCount()
{
comparisonCount= 0;
}
protected:
void swap(int *x, int *y);
private:
int comparisonCount;
};
// AbstractSort::compare
// This also keeps track of the number of comparisons performed
void AbstractSort:: swap(int *x, int *y)
{
//comparisonCount++;
//return x - y;
int temp;
temp = *x;
*x = *y;
*y = temp;
}
class MaxSort : public AbstractSort
{
public:
void QuickSort(int arr[], int s, int e);
};
//MaxSort::sort sort the given array with the given number of elements
void MaxSort::QuickSort (int list[], int m, int n)
{
//resetComparisonCount();
int key,i,j,k;
if( m < n)
{
//k = choose_pivot(m,n);
k = ((m+n)/2);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
QuickSort(list,m,j-1);
QuickSort(list,j+1,n);
}
}
int main()
{
const int MAX_SIZE = 100;
int arr[MAX_SIZE];
int size;
// Explain the program
cout << "This program keeps track of the number of comparisons required to\n";
cout << "to sort a randomly generated array array.\n";
cout << "How large do you want the array to be? ";
// Get the size of the array
cin >> size;
if (size > MAX_SIZE)
{
cout << "The size of the array must be no greater than 100.";
exit(1);
}
// Initialize random number generator
srand((unsigned int)time(0));
// Fill the array with random numbers
for (int k = 0; k < size; k++)
arr[k] = rand() % 1000;
// Output array to be sorted
cout << "Array to be sorted is: \n";
for (int k = 0; k < size; k++)
cout << arr[k] << " ";
// Sort and output results
MaxSort maxSort;
//maxSort.sort(arr, size);
maxSort.QuickSort(arr,0,MAX_SIZE - 1);
cout << "\nThe sorted array is: \n";
for (int k = 0; k < size; k++)
cout << arr[k] << " ";
//cout << "\nNumber of comparisons performed is: " << maxSort.getComparisonCount() << endl;
return 0;
}Thanks!