Overview / Logistics

The purpose of this lab is to give you practice with the abstract classes and inheritance. In the process, you will also implement an algorithm to sort objects along a number line.

You can obtain the starter code by typing

git clone https://github.com/ursinus-cs174-f2022/Lab4_AbstractSorting.git

I have provided a makefile, and the entry point for running the code with a main is in driver.cpp

Learning Objectives

• Separate out class specification from implementation between header files and cpp files, respectively
• Implement general code to implement algorithms that can apply to many specific types, using abstract classes

Background: Abstract Classes And Comparable Objects

Abstract Classes are classes that include pure virtual methods. The declarations look like this:

where the =0 is what causes this to be pure virtual. What this means is that we must override the class with a subclass that implements this method; we cannot use the abstract class by itself. Thus, we think of an abstract class as specifying a functionality that we would like inheriting objects to have. For this reason, abstract classes are often named as "something-able".

You will be working with an abstract class called Comparable, which specifies the ability to compare two objects in a total order via the pure virtual method compareTo. The method works as follows:

• If x.compareTo(y) < 0, then x < y
• If x.compareTo(y) == 0, then x = y
• If x.compareTo(y) > 0, then x > y

I've provided one class, CompInt, which implements this method for int variables. This class is a very thin wrapper class around an ordinary int, and the compareTo method is implemented quite simply as

The only trick here is that we have to cast other to a CompInt* type in order to access the field x.

---

Task 1: getMinIndex (1 Point)

One amazing thing we can do with abstract classes is to implement general purpose algorithms that can apply to many specific types. In our case, anything that is Comparable can be put into what's known as a total order; put simply, we can order Comparable objects along a number line.

To demonstrate this, fill in the definition of the getMinIndex method in comparable.cpp, which takes in an array of Comparable* pointers, and which should return the index of the element which is smaller than all of the others, according to the total order induced by the compareTo method. If there are ties, then it should return the smallest index.

As an example, I have setup an array of 10 CompInt* references in driver.cpp. The minimum index in that example should be 7.

---

Task 2: CompString String Wrapper (2 points)

To show off the generality of your code in the last part, create a class called CompString that wraps around a C++ string and implements the compareTo method to sort strings alphabetically. You can use the < operator to compare char components of each string. For example, you would find in C++ that 'a' < 'c' evaluates to true.

When you are finished, test your getMinIndex method on an array of CompString* references. As an example, suppose you had the following array of 10 CompString objects

Then you should find that the minimum index is 4, which corresponds to the string "college" (note how "college" comes before "collegeville" in the alphabet).

---

Task 3: Insertion Sort (2 points)

In addition to findMinIndex, create a void method sort which puts the elements in a Comparable* array into sorted order, using their compareTo method. For this, you can use an algorithm known as insertion sort. The pseudocode for this algorithm is as follows:

If this works properly, then the strings in the example in task 2 should print in the following order after calling sort:

To help you understand better why insertion sort works, have a look at the following two videos below: