C++ Abstract base class array of ptrs to ptrs

Question

I have an abstract base class (Comparable) with Date and Time virtually inheriting from it and a DateTime class v-inheriting from Date and Time.

My problem is this: I was tasked with dynamically allocating an array of Comparables.

Comparable ** compArray;
compArray = new Comparable *[n]; // where n is user specified number of elements

I then populate the array with DateTimes in alternating order. I need to sort this array using a quicksort and bubblesort combination. Bubble if length < 8. Comparable** from and Comparable ** to are the only parameters I'm allowed to use.

But I'm completely stuck. At this point it isn't worth pasting in the code I have due to it's frantic haphazardness.

Any help would be greatly appreciated. I've spent the past few hours trying to finish this up, only have sorting left in my project. Which is due tomorrow late morning.

Thanks in advance, Joel

EDIT:

  void Sort(Comparable** a);
  void quicksort(Comparable** from, Comparable** to); 
  Comparable** partition(Comparable** from, Comparable** to);
  void Swap(Comparable** from, Comparable** to); 
  void safeRead(istream& sin, Comparable* d, const char* prompt);
  void printArray(ostream & sout, Comparable **a, int size);

I was given the above to use as my arraySort.h

I'm using: int aSize = _msize(a) / sizeof(Comparable) - 1; as my length variable... which I have to calculate instead of passing it, which is kind of annoying.

I'm mainly just having headaches over dereferencing the ** and calling it's lessThan or equals method in quicksort. Once I understand how to do a quicksort with it'll 'click' and I'll be able to easily to bubble sort.

EDIT: I currently have the following as my bubble sort, it doesn't sort the array at all.

  void Swap(Comparable** from, Comparable** to)
  {
    Comparable** tmp;

    tmp = from;
    **from = **to;
    to = tmp;

  }

  void bubbleSort(Comparable** a, int size)
  {

    int i, j;

      for (i=0; i<size-1; i++)
      {
        for (j= size - 1; j > i; j--)
          if(a[j]->lessThan(*a[j-1]))
            Swap(&a[j], &a[j-1]);

      }
  }

Answer 1

Comparable** from and Comparable** to are the only parameters I'm allowed to use.

That's a bit silly, because having a size parameter would be a better API.

Anyway, one work-around (I don't know whather it's allowed) would be to do what C does for character strings: i.e. make the array one (1) element bigger than it needs to be when you allocate it, and set its last element to zero (null) to mark the end of the array (so that the callee can look for a null pointer to discover where the array ends).

Answer 2

You should overload the operator "<" for your classes, so that you can compare two of them in order to sort them. After that, it's a matter of implementing bubblesort and quicksort, something pretty straightforward (you will find plenty of explanations and example code in google). Maybe I didn't understand exactly whats your problem, so if this doesn't help please be more explicit :)

Answer 3

Keep in mind that the following line:

Comparable ** compArray = new Comparable *[n];

... is allocating an array of pointers; it isn't allocating any actual objects. So the next thing to do after allocating the above array is to set each pointer in compArray to point to a valid object. (Whether you set them by calling new for each one, or set the pointers to point at existing objects that you have somewhere else, is of course up to you)

Assuming you've done that, the next thing you probably want to do is write an IsLessThan() function that compares two pointers based on what they point to:

bool IsLessThan(const Comparable * a, const Comparable * b) {return (*a) < (*b);}

Note that the above is very different from comparing the pointers themselves!

Next step after that would be to write a BubbleSort function to sort your array. It might look like this:

 void BubbleSort(Comparable ** ptrArray, int arrayLen)
 {
    [... bubble sort routine would go here ...]
 }

... and it could just iterate repeatedly over the pointers in the array, and whenever it finds a pair of adjacent pointers that are in the wrong order (i.e. IsLessThan(ptrArray[i], ptrArray[i+1]) == false), swaps the pointers. Once it makes it through an entire pass of the array without having to swap any pointers at all, you know you're done, and you can allow the function to return.

Once that's working correctly (it will be inefficient, of course, but that's okay), the final step is to write the QuickSort routine:

 void QuickSort(Comparable ** ptrArray, int arrayLen)
 {
    if (arrayLen < 8) BubbleSort(ptrArray, arrayLen);
    else
    {
        [... quick sort routine would go here ...]
    }
 }

I don't remember QuickSort well enough to address it here, but hopefully the above will get you at least most of the way through the assignment.

Answer 4

You have to have alternating Dates and Times so you don't need to create the DateTime object, do you?

Remember you are sorting an inplace array. From and to are like the begin() and end() parts of the STL containers.

void QuickSort(Comparable** from, Comparable** to)
{
    int n = to - from;
    if (n < 8) BubbleSort(from, to);
    else {
        // the trick in here is remembering you have to sort in pairs
    }
}

Comparable** array = new Comparable*[n];
for (int i = 0; i < n; i += 2) {
    array[i] = new Date();
    array[i+1] = new Time();
}

// sort it
QuickSort(array, array+n);