Алгоритм MergeSort с объектными классами

Question

Я пытался выяснить это в последние часы, но без успеха.

У меня есть несколько классов, которые я использую для добавления данных, и поэтому я могу их отображать, но теперь мне нужно реализовать MergeSort algorithem для сортировки этих данных в зависимости от названий.

У меня есть компакт-диск Object, который наследует все остальные классы, а объект CD имеет заголовок свойства, введите char.

Теперь, когда я передать указатель на мой класс я делаю Comparision и проверки, но это не работает, как он должен:

Это моя функция для алгоритма сортировки:

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]; 
} 

Любая идея как реализовать что-то подобное?

Answer 1

В коде, который вы публикуете на codepad, есть несколько ошибок, я укажу в комментариях к программе. Поскольку вы не дали нам определения Popular, Symphony и Opera, у меня будет своя. Для удобства я поместил весь код в один файл.

#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; 
} 

Вот результат:

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 

Answer 2

Во-первых, обновите свой вопрос, чтобы показать свой реальный код для merge, merge_sort и CD. Я буду ссылаться на фактический код, размещенный в комментариях.

Ваша проблема, вероятно, связана с сортировкой заголовков, а не сортировкой на основе названий. Всюду в вашем коде, где вы назначаете название компакт-диска другому, вы ошибетесь. Вы сравните названия, но вы перемещаете и реорганизовать сами объекты (. Или в случае, указатели на самих объектов)

В любом случае, чтобы исправить эту проблему, вы просто заменить любой код, как это:

x->title = y->title; 

с этим:

x = y; 

Например, вместо

b[i]->title = a[h]->title; 

вам должен был бы написать

b[i] = a[h]; 

Кстати, распределение памяти и открепление не то, что вы делаете, как задним числом, чтобы увидеть, работает ли он или нет! Даже посредственный программист заботится о памяти; хорошие имеют дело с памятью с прямой любовью и уважением.