[C++] MergeSort con Vector

di il
2 risposte

[C++] MergeSort con Vector

void merge_cormen(vector<int> &A, int p, int q, int r) {
    
    int n1 = q-p+1;
    int n2 = r-q;
    
    vector<int> L;
    vector<int> R;
    
    for(int i=0; i<n1; i++) L.push_back(A[p+i]);
    for(int j=0; j<n2; j++) R.push_back(A[q+j+1]);
        
    L.push_back(numeric_limits<int>::max()); 
	R.push_back(numeric_limits<int>::max());

    int i = 0; 
    int j = 0;
    
    for(int k=p; k<=r; k++){
        
        if(L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }
        else{
            A[k] = R[j];
            j++;
        }
    }
}

void merge1(vector<int> &A, int p, int q){
    if(p < q){
        int r = (p+q)/2;
        merge1(A, p, r);
        merge1(A, r+1, q);
        merge_cormen(A, p, q, r);
    }
}
Salve a tutti, avrei bisogno di un'occhiata al codice. Sto implementando il MergeSort con i vector, il codice funziona, ma non ordina gli elementi. Potreste aiutarmi a capire dov'è l'errore?

2 Risposte

  • Re: [C++] MergeSort con Vector

    Principalmente ci sono due problemi con il tuo codice, il primo è, i nomi che hai dato alle variabili. Per esempio 'n1' non fornisce nessuna informazione su cosa contiene quella variabile. Il secondo problema è causato proprio dal primo, se controlli bene la funzione merge1 vedrai che c'è un problema che è causato proprio dai nomi non descrittivi delle variabili.
  • Re: [C++] MergeSort con Vector

    Risolto: avevo attribuito gli indici ai vector in modo sbagliato. Per cui quando richiamava la funzione merge1, non veniva eseguito alcun istruzione.
Devi accedere o registrarti per scrivere nel forum
2 risposte