Problem 3

Implement Cocktail Shaker Sort, that is, implement class ShakerSortableIntVector

which is a public subclass of SortableIntVector:

#pragma once

#include "SortableIntVector.h"

class ShakerSortableIntVector : public SortableIntVector

{

public:

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

void sort( Comparable aOrderFunction = [] (int aLeft, int aRight)

{ return aLeft <= aRight; } ) override;

};

Cocktail Shaker Sort is bidirectional Bubble Sort. See Canvas for a pseudo code implementation. There is no need for a flag “is-sorted” even though some sources suggest one. 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.

The implementation of Cocktail Shaker Sort can be achieved solely by implementing the sort() method and using its default implementation for aOrderFunction. Please note that you need to use IntVector’s swap() member function to exchange elements.

There is only one Comparable function. However, it suffices to implement the bidirectional sorting process. Analyze carefully its behavior and interaction with Cocktail Shaker Sort to devise a proper solution. The implementation must sort the elements in decreasing order.

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

Dataset