Question

Problem Set 2: Inheritance and Method Overriding

The goal of this problem set is to apply inheritance and method overriding in order to create

a hierarchy of array sorters. There exist many algorithms to sort arrays. In this problem set,

we are especially interested in “in-place” sorting algorithms like Selection Sort and Insertion

Sort. In-place sorting refers to an approach in which we perform the sorting steps on the

underlying array rather than using extra storage. When using object-oriented design, we can

encapsulate the underlying array and the required array manipulation and access functions in

a common super class, whereas the actual sorting process is defined in a subclass. Hence,

sorting an array becomes a polymorphic operation and which sorting algorithm is applied

depends on the dynamic type (class) of the array sorter in question.

Consider the following main function:

int main()

{

int lArray[] = { 34, 2, 890, 40, 16, 218, 20, 49, 10, 29 };

unsigned int lArrayLength = sizeof(lArray) / sizeof(int);

SelectionSort lSelectionSorter( lArray, lArrayLength );

cout << "Test selection sort:" << endl;

cout << lSelectionSorter << endl;

lSelectionSorter.sort( cout );

InsertionSort lInsertionSorter( lArray, lArrayLength );

cout << "Test insertion sort:" << endl;

cout << lInsertionSorter << endl;

lInsertionSorter.sort( cout );

return 0;

}

The main function defines a local array of integers. It uses an initialized array variable

declaration, where the initializer determines the size of the array, here 10 elements. We also

need a variable that stores the array size. We can use a C++ idiom to ask the compiler to

calculate automatically for us: sizeof(lArray) / sizeof(int). In C/C++, sizeof(X)

returns the size of X in bytes at compile time. The variable lArray has type int[10]. So, sizeof(lArray) / sizeof(int) means (10*4)/4, where sizeof(int) = 4.

The remainder of the main function is dedicated to testing our sorting abstractions, which

should produce the following output:

Test selection sort:

[34, 2, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 10, 890, 40, 16, 218, 20, 49, 34, 29]

State: [2, 10, 16, 40, 890, 218, 20, 49, 34, 29]

State: [2, 10, 16, 20, 890, 218, 40, 49, 34, 29]

State: [2, 10, 16, 20, 29, 218, 40, 49, 34, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

Test insertion sort:

[34, 2, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 40, 890, 16, 218, 20, 49, 10, 29]

State: [2, 16, 34, 40, 890, 218, 20, 49, 10, 29]

State: [2, 16, 34, 40, 218, 890, 20, 49, 10, 29]

State: [2, 16, 20, 34, 40, 218, 890, 49, 10, 29]

State: [2, 16, 20, 34, 40, 49, 218, 890, 10, 29]

State: [2, 10, 16, 20, 34, 40, 49, 218, 890, 29]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

To achieve the required behavior, we need three classes: ArraySorterPS2, SelectionSort, and InsertionSort.

The class ArraySorter is given by the following specification.

#pragma once

#include <ostream>

class ArraySorter

{

private:

int* fArrayOfNumbers;

unsigned int fArraySize;

protected:

// service member function to be called once a sorting step has been finished

void stepCompleted( std::ostream& aOStream );

// swap elements in the underlying array

void swapElements( unsigned int aSourcIndex, unsigned int aTargetIndex );

public:

// array sorter constructor

ArraySorter( const int aArrayOfNumbers[], unsigned int aArraySize );

// array sorter destructor

virtual ~ArraySorter();

// return array element at index

const unsigned int at( unsigned int aIndex ) const;

// return size of underlying array

const unsigned int getRange() const;

// polymorphic sort function (takes an output stream to call stepCompleted)

virtual void sort( std::ostream& aOStream );

// output operator for array sorters

friend std::ostream& operator<<( std::ostream& aOStream, const ArraySorter& aObject );

};

A particular problem in C++ is that arrays parameters “decay” to pointer to the first element

of the underlying array. We often find in the literature that one says: “arrays are passed by

reference”. This is not true. Arrays are passed to a function by using a pointer. This is still

call-by-value. Nevertheless, passing a pointer feels like passing a reference.

So, to pass an array to a function (including the constructor), we require two parameters: the

pointer to the first element and the size of the array. This is quite different from Java and C#.

We write

ArraySorter( const int aArrayOfNumbers[], unsigned int aArraySize );

to mean that the ArraySorter constructor takes an array, aArrayOfNumbers, and a

corresponding size, aArraySize. The form aArrayOfNumbers[] is called open array, which

we can use in C++ to pass an array of any size. The compiler converts this expression into a pointer.

Passing arrays via pointers to the first element means that the actual array is not copied and

any change to its elements is visible anywhere in the program. For the purpose of this

assignment, we want to create a copy. We only want to sort the copy, not the original.

Somebody has provided us with a working solution and has implemented the ArraySorter

constructor and destructor. Use this code in your solution.

ArraySorter::ArraySorter( const int aArrayOfNumbers[], unsigned int aArraySize )

{

// copy array into sorter

fArrayOfNumbers = new int[aArraySize];

for ( unsigned int i = 0; i < aArraySize; i++ )

{

fArrayOfNumbers[i] = aArrayOfNumbers[i];

}

fArraySize = aArraySize;

}

ArraySorter::~ArraySorter()

{

// delete memory associated with array

delete [] fArrayOfNumbers;

}

We allocate resources (here memory) and release the resources ones the objects go out of

scope.

You need to implement all other functions. There are two protected functions:

stepCompleted and swapElements. The former must be called at the end of the outer

loop of the sorting process (both algorithms in this assignment have nested loops). It has to

print one line: State: […]. The method swapElements exchanges the underlying array

elements. The indices are expected to be within bounds.

Only the function sort is virtual, that is, can be overridden in subclasses. In class

ArraySorter it just invokes stepCompleted. The other public member functions provide

access to the corresponding information. The method at has to perform a range check and

through a range_error exception. See tutorial 4. There we used an exception in the

flatten method. Please note that you should call the ArraySorter::sort method from

the overridden sort methods. There is no keyword super in C++. To call a super method

one uses the fully-qualified name of the method one wants to call. In our case the super

method is denoted by a call ArraySorter::sort( aOStream ) where aOStream is the

output stream object passed to the sort method.

The output operator creates a textual representation of the underlying array. It must not emit newline at the end.

Implement the class SelectionSort. You need to map the selection sort algorithm. It has

an outer and an inner loop. Call stepCompleted at the end of the outer loop. Use the

following specification:

#pragma once

#include "ArraySorter.h"

class SelectionSort : public ArraySorter

{

public:

SelectionSort( int aArrayOfNumbers[], unsigned int aArraySize );

void sort( std::ostream& aOStream ) override;

};

Test:

SelectionSort lSelectionSorter( lArray, lArrayLength );

cout << "Test selection sort:" << endl;

cout << lSelectionSorter << endl;

lSelectionSorter.sort( cout );

Output:

Test selection sort:

[34, 2, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 10, 890, 40, 16, 218, 20, 49, 34, 29]

State: [2, 10, 16, 40, 890, 218, 20, 49, 34, 29]

State: [2, 10, 16, 20, 890, 218, 40, 49, 34, 29]

State: [2, 10, 16, 20, 29, 218, 40, 49, 34, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

Implement the class InsertionSort. You need to map the insertion sort algorithm. It has

an outer and an inner loop. Call stepCompleted at the end of the outer loop. Use the

following specification:

#pragma once

#include "ArraySorter.h"

class InsertionSort : public ArraySorter

{

public:

InsertionSort( int aArrayOfNumbers[], unsigned int aArraySize );

void sort( std::ostream& aOStream ) override;

};

Test:

InsertionSort lInsertionSorter( lArray, lArrayLength );

cout << "Test insertion sort:" << endl;

cout << lInsertionSorter << endl;

lInsertionSorter.sort( cout );

Output:

Test insertion sort:

[34, 2, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 890, 40, 16, 218, 20, 49, 10, 29]

State: [2, 34, 40, 890, 16, 218, 20, 49, 10, 29]

State: [2, 16, 34, 40, 890, 218, 20, 49, 10, 29]

State: [2, 16, 34, 40, 218, 890, 20, 49, 10, 29]

State: [2, 16, 20, 34, 40, 218, 890, 49, 10, 29]

State: [2, 16, 20, 34, 40, 49, 218, 890, 10, 29]

State: [2, 10, 16, 20, 34, 40, 49, 218, 890, 29]

State: [2, 10, 16, 20, 29, 34, 40, 49, 218, 890]

Answer 1

Below is required code in Separate class files. Let me know if you have any problem or doubt. Thank you.

=============================================================================

InsertionSort.h

========================

#pragma once
#include "ArraySorter.h"
class InsertionSort : public ArraySorter
{
public:
   InsertionSort(int aArrayOfNumbers[], unsigned int aArraySize);
   void sort(std::ostream& aOStream) override;
};

========================

InsertionSort.cpp

========================

#include "InsertionSort.h"

InsertionSort::InsertionSort(int aArrayOfNumbers[], unsigned int aArraySize) :
   ArraySorter(aArrayOfNumbers, aArraySize) {}

void InsertionSort::sort(std::ostream& aOStream) {
   // perform insertion sort
   for (unsigned int i = 1; i < this->getRange(); i++) {
       // find next value from array that is out of order
       int value = this->at(i);
       // set internal loop index
       unsigned int j = i - 1;

       // Move elements of array, that are greater than value to one place right
       while (this->at(j) > value) {
           // swap elements to move them right side
           this->swapElements(j, j + 1);
           // reduce loop counter
           if (j > 0) {
               j--;
           }
           else {
               break;
           }
       }
       // print each step
       ArraySorter::sort(aOStream);
   }
}

=========================

SelectionSort.h

=========================

#pragma once
#include "ArraySorter.h"
class SelectionSort : public ArraySorter
{
public:
   SelectionSort(int aArrayOfNumbers[], unsigned int aArraySize);
   void sort(std::ostream& aOStream) override;
};

============================

SelectionSort.cpp

============================

#include "SelectionSort.h"

SelectionSort::SelectionSort(int aArrayOfNumbers[], unsigned int aArraySize) :
   ArraySorter(aArrayOfNumbers, aArraySize) {}

void SelectionSort::sort(std::ostream& aOStream) {
   // perform selection sort
   for (unsigned int i = 0; i < this->getRange() - 1; i++) {
       // find the index of minimum element
       unsigned int minIndex = i; // start with current index
       int minValue = this->at(minIndex); // value of minimum element
       // find next min from array
       for (unsigned int j = i + 1; j < this->getRange(); j++) {
           if (minValue > this->at(j)) {
               // found new min value
               // reset min index and its value
               minIndex = j;
               minValue = this->at(j);
           }
       }
       // swap min element at current loop index
       this->swapElements(i, minIndex);
       // print each step
       ArraySorter::sort(aOStream);
   }
}

=============================

ArraySorter.h

=============================

#pragma once
#include <ostream>
class ArraySorter
{
private:
   int* fArrayOfNumbers;
   unsigned int fArraySize;
protected:
   // service member function to be called once a sorting step has been finished
   void stepCompleted(std::ostream& aOStream);
   // swap elements in the underlying array
   void swapElements(unsigned int aSourcIndex, unsigned int aTargetIndex);
public:
   // array sorter constructor
   ArraySorter(const int aArrayOfNumbers[], unsigned int aArraySize);
   // array sorter destructor
   virtual ~ArraySorter();
   // return array element at index
   const unsigned int at(unsigned int aIndex) const;
   // return size of underlying array
   const unsigned int getRange() const;
   // polymorphic sort function (takes an output stream to call stepCompleted)
   virtual void sort(std::ostream& aOStream);
   // output operator for array sorters
   friend std::ostream& operator<<(std::ostream& aOStream, const ArraySorter& aObject);
};

==============================

ArraySorter.cpp

==============================

#include "ArraySorter.h"

ArraySorter::ArraySorter(const int aArrayOfNumbers[], unsigned int aArraySize)
{
   // copy array into sorter
   fArrayOfNumbers = new int[aArraySize];
   for (unsigned int i = 0; i < aArraySize; i++)
   {
       fArrayOfNumbers[i] = aArrayOfNumbers[i];
   }
   fArraySize = aArraySize;
}

ArraySorter::~ArraySorter()
{
   // delete memory associated with array
   delete[] fArrayOfNumbers;
}

void ArraySorter::stepCompleted(std::ostream& aOStream) {
   aOStream << "State: [";
   // print current array elements order
   for (unsigned int i = 0; i < fArraySize; i++) {
       aOStream << fArrayOfNumbers[i];
       // add coma after each elements except for last
       if (i < fArraySize - 1) {
           aOStream << ", ";
       }
   }
   aOStream << "]\n";
}

void ArraySorter::swapElements(unsigned int aSourcIndex, unsigned int aTargetIndex) {
   // swap given element with given index in array
   int temp = fArrayOfNumbers[aSourcIndex];
   fArrayOfNumbers[aSourcIndex] = fArrayOfNumbers[aTargetIndex];
   fArrayOfNumbers[aTargetIndex] = temp;
}

const unsigned int ArraySorter::at(unsigned int aIndex) const {
   return fArrayOfNumbers[aIndex];
}

const unsigned int ArraySorter::getRange() const {
   return fArraySize;
}

void ArraySorter::sort(std::ostream& aOStream) {
   // call step completed to print each step at a call from derived classes
   stepCompleted(aOStream);
}

std::ostream& operator<<(std::ostream& aOStream, const ArraySorter& aObject) {
   // output current array elements in order
   aOStream << "[";
   for (unsigned int i = 0; i < aObject.fArraySize; i++) {
       aOStream << aObject.fArrayOfNumbers[i];
       if (i < aObject.fArraySize - 1) {
           aOStream << ", ";
       }
   }
   aOStream << "]";
   return aOStream;
}

=============================

Main.cpp

=============================

#include <iostream>
#include "SelectionSort.h"
#include "InsertionSort.h"
using namespace std;

int main()
{
   int lArray[] = { 34, 2, 890, 40, 16, 218, 20, 49, 10, 29 };
   unsigned int lArrayLength = sizeof(lArray) / sizeof(int);
   SelectionSort lSelectionSorter(lArray, lArrayLength);
   cout << "Test selection sort:" << endl;
   cout << lSelectionSorter << endl;
   lSelectionSorter.sort(cout);
   InsertionSort lInsertionSorter(lArray, lArrayLength);
   cout << "Test insertion sort:" << endl;
   cout << lInsertionSorter << endl;
   lInsertionSorter.sort(cout);
   return 0;
}