Problem 2

Implement Bubble Sort, that is, implement class SortableIntVector which is a public subclass of IntVector:

#pragma once

#include "IntVector.h"

#include <functional>

using Comparable = std::function<bool(int, int)>; class SortableIntVector : public IntVector

{

public:

SortableIntVector( const int aArrayOfIntegers[], size_t aNumberOfElements );

virtual void sort( Comparable aOrderFunction );

};

Bubble Sort is simple quadratic-time complexity sorting algorithm. See Canvas for a pseudo code implementation. There is no need for a flag “is-sorted” even though some sources suggest so. There is limited if any improvement on the performance of the algorithm. Worse, it may even slow it down due to the extra tests necessary. See D.E. Knuth’s comments on this matter.

Class SortableIntVector is a subclass of IntVector. It defines a constructor and we need to use proper class-chaining to initialize objects of class SortableIntVector. Remember, the initialization of the super class requires a super class constructor call defined as member initializer in C++. Please note that you need to use IntVector’s swap() member function to exchange elements.

The method sort() implements Bubble Sort. We can sort in increasing or decreasing order. Here we wish to sort in increasing order. The method sort() takes as parameter a Comparable function. Comparable is a type alias for the standard function template std::function<bool(int, int)>. That is, Comparable is a Boolean function that takes two integer values and returns true, if the left integer goes before the right integer. Programmatically, the left integer goes before the right integer if the value of the left integer does not exceed the value of the right integer.

To provide a matching function for Comparable, you need to define a lambda expression, an anonymous function object representing a callable unit of code, when calling the sort() method in main() for Problem 2:

// Use a lambda expression here that orders integers in increasing order.

// The lambda expression does not capture any variables of throws any exceptions.

// It has to return a bool value. lVector.sort( /* lambda expression */ );

You can use the test driver in Main.cpp (available on Canvas) to test your implementation. Please uncomment #define P2 for this purpose. Running the program should produce the following output:

Dataset