Introduction

This project is to write a program, in C++, for a racing competition between different sorting algorithms.

You will learn how to run several algorithms, including normally recursive algorithms, in an interleaved

fashion. You will also learn in detail how to perform a sort in-place in an array.

This project will involve a Race Mgr object, which will create an algorithm object for each algorithm. The

Race Mgr will then repeatedly give each algorithm a turn to advance by calling its step() method. Finally, the

Race Mgr will stop calling an algorithm's step() function when it returns that it has completed its sorting task.

Each algorithm will be given a copy of the array of integers to be sorted.

Each algorithm's step() method will run 1 step of the algorithm which involves a single basic operation, a

comparison. Other details about the step() behavior are different for each algorithm.

Bubble Step() Details

The Bubble Sort also treats the array as a sorted prefix followed by an unsorted suffix. Its state consists of

the unsorted value to insert (it is in the front cell of the suffix), and the index of the next prefix cell to check

which is the last cell in the prefix, and the length of the array.

Initially, the prefix consists of the 0th array cell and the suffix is from cell 1 to the end of the array. So the

initial state has the unsorted value at index 1 and the next sorted prefix cell to check is at index 0 just like the

Insertion Sort.

The step() method attempts to bubble up the next unsorted value from its unsorted suffix position into its

correct spot in the sorted prefix by comparing the unsorted value to the next sorted value: one comparison. If

unsorted wins, then the two values are swapped in their cells (one bubbling move). Once the swap is done, the

state must be updated so that the next sorted index to check is incremented, and also so that that next unsorted

value is tracked as it bubbles up. Else, if unsorted loses, then it is currently in its correct place in the prefix and

the state must be updated to setup for the new front of the suffix and the end of the prefix.

Please help me write the class and the step()