Question

C++

Analysis of Sorting Algorithms

Design a class AbstractSort that can be used to analyze the number of comparisons performed by a sorting algorithm. The class should have a member function compare that is capable of comparing two array elements, and a means of keeping track of the number of comparisons performed. The class should be an abstract class with a pure virtual member function

void sort(int arr[ ], int size)

which, when overridden, will sort the array by calling the compare function to determine the relative order of pairs of numbers. Create a subclass of AbstractSort that uses a simple sorting algorithm to implement the sort function. The class should have a member function that can be called after the sorting is done to retrieve the number of comparisons performed.

Answer 1

//C++ CODE TO COPY//

#include<iostream>
using namespace std;

//abstratc class AbstractSort
class AbstractSort
{
   // Data members of class
public:
   int count_compare;
   //constructor
   AbstractSort()
   {
       this->count_compare = 0;
   }
  
   //compare function which will return true if first index (element) will greater than second
   //element provded in parameters
   bool compare(int elem1, int elem2)
   {
       //increment compare counter each time this function called
       count_compare++;
       if (elem1 > elem2)
           return true;
       else
           return false;
   }
   // Pure Virtual Function sort
   virtual void sort(int arr[], int size) = 0;

};

class sorting : public AbstractSort
{
public:
   //constructor
   sorting() : AbstractSort(){};
   void sort(int arr[], int size)
   {  
       //sorting elements by comparing each to array elements
       for (int i = 0; i < size; i++)
       {
           for (int j = i + 1; j < size; j++){
               //calling parent class compare function to determine maximum number
               if (compare(arr[i], arr[j])){
                   int temp = arr[i];
                   arr[i] = arr[j];
                   arr[j] = temp; // change elements location(index) if previouse one is greater than next one
              
               }
           }
       }
   }

   //getting total comparisons during sorting done
   int getCompareCount()
   {
       return this->count_compare;
   }
};

//amin driver function
int main()
{
   //initialising sorting class object
   sorting *sort = new sorting();
  
   //array which we have to sort
   int arr[] = {3, 8, 100, 23, 50, 7, 1, 55, 2};
   int size = sizeof(arr) / sizeof(arr[0]);

   cout << "\nArray before sorting: ";
   for (int i = 0; i < size; i++)
   {
       cout << arr[i]<<" ";
   }
   //calling to sort function
   sort->sort(arr, size);
   cout << "\n\nArray after sorting: ";
   for (int i = 0; i < size; i++)
   {
       cout << arr[i]<<" ";
   }
   cout << "\n\nNo of Comparison done: " << sort->getCompareCount() << endl;

   return 0;
}

//OUTPUT//

Comment down for any queries!
Please give a thumbs up if you are satisfied and helped with the answer :)