I have put together a program using a class AbstractSort that can be used to analyze the number of comparisons performed by a sorting algorithm. Anyway, I built the programs( I have 2 here) and the first one counts the passes but does not order the array created and the second one does better with the array but I lose the counting function somehow. Any ideas where I screwed up?
PROGRAM 1
// This Program uses a class named AbstractSort as a framework
// For sorting algorithms that sort by comparing pairs of array entries.
// To obtain a concrete class for sorting, one first subclasses
// The AbstractSort class and then overrides the pure virtual function
// Sort. The sort() function must call the compare(int, int) function
// To compare pairs of array entries.
*/
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
class AbstractSort
{
public:
virtual void sort(int arr[], int size) = 0;
int getComparisonCount()
{
return comparisonCount;
}
void resetComparisonCount()
{
comparisonCount= 0;
}
protected:
int compare(int x, int y);
private:
int comparisonCount;
};
// AbstractSort::compare
// Returns -1, 0, or 1 a la strcmp
// This also keeps track of the number of comparisons performed
int AbstractSort:: compare(int x, int y) //compare func
{
comparisonCount++;
return x -x;
}
// derived class
class MaxSort : public AbstractSort
{
public:
void sort(int arr[], int size);
};
//MaxSort::sort sort the given array with the given number of elements
void MaxSort::sort (int arr[], int size)
{
resetComparisonCount();
for (int k = size = size-1; k>=1; k--)
{
int indexOfLargest =0;
for (int ix = 1; ix <= k; ix++)
{
if (compare (arr[ix], arr[indexOfLargest]) > 0)
{
indexOfLargest = ix;
}
}
swap(arr[indexOfLargest], arr[k]);
}
}
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.\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(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);
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;
system("pause");
return 0;
}PROGRAM 2
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
class AbstractSort
{
public:
virtual void sort(int arr[], int size) = 0;
int getComparisonCount()
{
return comparisonCount;
}
void resetComparisonCount()
{
comparisonCount= 0;
}
protected:
int compare(int x, int y);
private:
int comparisonCount;
};
// AbstractSort::compare
// Returns -1, 0, or 1 a la strcmp
// This also keeps track of the number of comparisons performed
int AbstractSort:: compare(int x, int y) //compare func
{
comparisonCount++;
return x - y;
}
// derived class
class MaxSort : public AbstractSort
{
public:
void sort(int arr[], int size);
};
//MaxSort::sort sort the given array with the given number of elements
void MaxSort::sort (int arr[], int size)
{
resetComparisonCount();
int indexOfMin;
int pass;
int j;
for ( pass = 0; pass < size - 1; pass++ )
{
indexOfMin = pass;
for ( j = pass + 1; j < size; j++ )
if ( arr[j] < arr[pass] )
indexOfMin = j;
swap ( arr[pass], arr[indexOfMin] );
}
}
// swap function for integers
void swap ( int& x, int& y )
{
int temp;
temp = x;
x = y;
y = temp;
}
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.\n";
cout << "How large do you want the array to be (max size=100)? ";
// 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(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 maxSort1;
maxSort1.sort(arr, size);
cout << "\nThe sorted array is: \n";
for (int k = 0; k < size; k++)
{
cout << arr[k] << " ";
}
cout << "\nNumber of comparisons performed is: " << maxSort1.getComparisonCount() << endl;
system("pause");
return 0;
}