MergeSort Algorithm with Object Classes

Question

I have been trying to figure out this thing in the past hours but with no success.

I have several classes which I am using to add data, and so I can display them, but now i have to implement a MergeSort algorithem to sort this datas depending on the titles.

I have the Object CD, which all other classes inherits from, and object CD has the property title, type char.

Now when i pass the pointer to my class I do the comparision and checking, but it's not working how it should:

This is my Function for the Sorting Algorithm:

void merge(CD *a[], int, int, int);

void merge_sort(CD *a[], int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        merge_sort(a, low, mid);
        merge_sort(a,mid + 1, high);
        merge(a, low, mid, high);
    }
}

void merge(CD *a[], int low, int mid, int high) {
    int h, i, j, k;
    CD *b;
    h = low;
    i = low;
    j = mid + 1;


    while ((h <= mid) && (j <= high)) {
        if (a[h]->title[100] <= a[j]->title[100]) {
            b[i].title[100] = a[h]->title[100];
            h++;
        }
        else {
            b[i].title[100] = a[j]->title[100];
            j++;
        }
        i++;
    }
    if (h > mid) {
        for (k = j; k <= high; k++) {
            b[i].title[100] = a[k]->title[100];
            i++;
        }
    }
    else {
        for (k = h; k <= mid; k++) {
            b[i].title[100] = a[k]->title[100];
            i++;
        }
    }
    for (k = low; k <= high; k++) 
        a[k]->title[100] = b[k].title[100];
}

Any idea how to implement something like this ?

Answer 1

There are several faults in the code you post on codepad, I'll point out in the program comments. Since you didn't give us the definitions of Popular, Symphony and Opera, I'll have my own. For convenience, I put all the code in one file.

#pragma once
#include <string>
#include <iostream>

using namespace std;

class CD {
public:
    string publisher, title, location, year, empty;
public:
    CD()
    {
        publisher = "";
        title = "";
        location = "";
        year = "";
        empty = "";
    }

    void virtual input() = 0;

    void virtual output() = 0;
};


class Popular : public CD
{
public:
    Popular(const string& name)
    {
        title = name;
    }
    virtual void input()
    {
        return;
    }
    virtual void output()
    {
        return;
    }
};

void merge(CD *a[], int, int, int);

void merge_sort(CD *a[], int low, int high) {
    int mid;
    if (low < high) {
        mid = low + (high - low) / 2; //avoid overflow
        merge_sort(a, low, mid);
        merge_sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

void merge(CD *a[], int low, int mid, int high) {

    int p1 = low;
    int p2 = mid + 1;
    CD ** merged = (CD**)malloc(sizeof(CD*) * (high - low + 1)); // CD *b[high] isn't illegal c++ syntax, VLA is part of C99.
    int p = 0;
    while(p1 < mid + 1 && p2 < high + 1)
    {
        if(a[p1]->title > a[p2]->title)
        {
            merged[p] = a[p2];
            p2++;
        }
        else
        {
            merged[p] = a[p1];
            p1++;
        }
        p++;
    }

    while(p1 < mid + 1)
    {
        merged[p++] = a[p1++];
    }

    while(p2 < high + 1)
        merged[p++] = a[p2++];

    for(int i = 0;i < (high - low + 1); i++)
    {
        a[low + i] = merged[i];
    }

    free(merged);
}

int main() {
    CD *cdptr[100]; //pointer declaration for each of our class

    int n = 0, choose;

    // just to test the mergesort
    CD* c1 = new Popular("hello");
    CD* c2 = new Popular("world");
    CD* c3 = new Popular("coldplay");
    CD* c4 = new Popular("pink");

    cdptr[n++] = c1;
    cdptr[n++] = c2;
    cdptr[n++] = c3;
    cdptr[n++] = c4;

    char terminate = 'n'; // you should initialize this variable.

    do // do-while statement which allows the user to enter data and terminate the program when he wants
    {
        cout << "\n1.Classical";
        cout << "\n2.Popular";
        cout << "\n3.Sort";
        cout << "\n4.Display";
        cout << "\n5.Terminate program";
        cout << endl << endl;
        cout << "\nChoose category: ";
        cin >> choose;
        switch (choose)                            //switch for the user to choose the type of input
        {
            //skip the case 1, 2
            case 3:
                merge_sort(cdptr, 0, n - 1); //  element indices begin at 0.
                break;
            case 4:
                if (n == 0)
                    cout << "\nNo data entered!" << endl;
                for (int i = 0; i < n; i++) {
                    cdptr[i]->output();
                    cout << endl;
                }
                break;
            case 5:
                cout << "\nDo you want to terminate the program? (y/n)";
                cin >> terminate;
                break;
            default:
                cout << "\nNot recognized value!" << endl;
        }
    } while (terminate != 'y');

    for(int i = 0; i < 4; ++i)
        cout<<cdptr[i]->title<<endl;

    delete c1;
    delete c2;
    delete c3;
    delete c4;
    return 0;
}

Here's the output:

1.Classical  
2.Popular
3.Sort
4.Display
5.Terminate program


Choose category: 3

1.Classical
2.Popular
3.Sort
4.Display
5.Terminate program


Choose category: 5

Do you want to terminate the program? (y/n)y
coldplay
hello
pink
world