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;
}``````

## All 4 Replies

Program 1 has a bad compare function. See if you can spot the problem.

``````int	AbstractSort:: compare(int x, int y)	//compare func
{
comparisonCount++;
return x -x;
}``````

Program 2 doesn't appear to USE its compare function, so whether it's right or wrong is irrelevant.

Yeah, I seeit. x-x. Funny how that made it into there and not the second version- they were copied across. Thanks on the first issue, but where am i missing the call on the second. I am taking this c++ class and html AND java along withthe javascript in the html. so I am having languages running together

>> where am i missing the call on the second.

Do a search for the word "compare" in Program 2 and notice that it's never called. Do the same search in Program 1 and note where it's used. Since you say Program 2 sorts properly and since to do so requires comparisons, presumably you're comparing somewhere without calling "compare", so presumably you must have lines within your sort function with comparison operators < > <= >= ==. Find them and change them so they call the "compare" function.

Thanks, that makes sense. I understand why we are spending so much time on polymorphism and virual calls now.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.