Zählinversion mit merge sort

Question

Ich weiß, dass es eine Menge dieser Implementierung hier in Stack gab, aber ich habe ein Problem, das ich nicht behandeln kann.

Zuerst habe ich die Merge-Sortierung bei khanacademy mit Javascript implementiert, dann schreibe ich den Code in C++ um und versuchte die Anzahl der Inversion in einem Array zu zählen.

Ich tat das Beste, was ich konnte, und verbrachte eine Stunde damit, zu verstehen, was ich falsch gemacht habe. Ich habe hier auf Stack nach einer anderen Implementierung gesucht und versucht, meinen Code zu korrigieren. Leider weiß ich nicht, was ich falsch mache. Ich denke, dass ich jede Inversion zähle. Vielen Dank im Voraus für eine Hilfe, verstanden zu haben, was falsch ist.

My Code:

int lowhalflength(int p, int q) 
{ 
    return q - p + 1; 
} 

int highhalflength(int q, int r) 
{ 
    return r - q; 
} 


int merge(int array[], int p, int q, int r, int lowhalf[], int highhalf[]) 
{ 
    int k = p; 
    int i; 
    int j; 
    int count = 0; 
    for (int i = 0; k <= q; i++ , k++) 
    { 
     lowhalf[i] = array[k]; 
    } 
    for (int i = 0; k <= r; i++ , k++) 
    { 
     highhalf[i] = array[k]; 
    } 

    k = p; 
    i = 0; 
    j = 0; 

    while (i <= (q - p) && j <= r - (q + 1)) 
    { 
     if (lowhalf[i] <= highhalf[j]) 
     { 
      array[k] = lowhalf[i]; 
      i++; 
     } 
     else 
     { 
      array[k] = highhalf[j]; 
      j++; 
      count += q - 1; 
     } 

     k++; 
    } 

    while (i < lowhalflength(p, q)) 
    { 
     array[k] = lowhalf[i]; 
     k++; 
     i++; 
    } 

    while (j < highhalflength(q, r)) 
    { 
     array[k] = highhalf[j]; 
     k++; 
     j++; 
    } 


    return count; 
} 

Die MergeSort Funktion:

int mergeSort(int array[], int p, int r) 
{ 
    int q = ((p + r)/2); 
    int* lowhalf = new int[lowhalflength(p, q)]; 
    int* highhalf = new int[highhalflength(q, r)]; 

    int count = 0; 
    if (p < r) 
    { 
     q = ((p + r)/2); 
     count = mergeSort(array, p, q); 
     count += mergeSort(array, q + 1, r); 
     count += merge(array, p, q, r, lowhalf, highhalf); 
    } 
    delete[] lowhalf; 
    delete[] highhalf; 
    return count; 
} 

Für array [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] der Ausgang 46, während es 45

EDIT sein sollte: die Antwort zu ändern, ist die folgende Zeile q-1 bis q+j-k. Ich habe es selbst gefunden, aber ich weiß nicht, wie ich es interpretieren soll. Jeder Hinweis oder Beweis, warum es richtig ist, wird wirklich wünschenswert sein.

Answer 1

Sie können meinen Code zum Zählen Inversionspaar und Ihre Merge-Funktion soll wie folgt in effizienter Weise aussehen verwenden wie:

int merge(int *array, int lower, int mid, int upper) { 

    // Initialisation of the sizes of two subarrays and subarrays also. 
    int left_array_size = mid - lower + 1; 
    int right_array_size = upper - mid; 
    int left_array[left_array_size], right_array[right_array_size]; 

    int j = 0; 
    for (int i = lower; i <= mid; i++) { 
     left_array[j++] = array[i]; 
    } 
    j = 0; 
    for (int i = mid + 1; i <= upper; i++) { 
     right_array[j++] = array[i]; 
    } 

    // Performing merging in a non-increasing manner and count inversion pairs.. 
    int i = 0, k; 
    j = 0; 
    int resultIntermediate = 0; 
    for (k = lower; k <= upper;) { 
     if (left_array[i] <= right_array[j]) { 
      array[k++] = left_array[i++]; 
      if (i >= left_array_size) break; 
     } 
     else { 
      array[k++] = right_array[j++]; 

      // If a element in left_array_size is greater than an element from 
      // right_array_size then rest of all other elements will also be 
      // greater than that element of right_array_size because both 
      // subarrays are sorted in non-decreasing order. 
      resultIntermediate += left_array_size - i; 

      if (j >= right_array_size) break; 
     } 
    } //end of for loop. 


    // Performing merging if i or j doesn't reach to its 
    // maximum value i.e. size of the subarrays. 
    while (i < left_array_size) { 
     array[k++] = left_array[i++]; 
    } 
    while (j < right_array_size) { 
     array[k++] = right_array[j++]; 
    } 

    // Returning the result... 
    return resultIntermediate; 

} //end of the merge function. 

und Funktion Inversionspaar

int countInversionPair(int *array, int lower, int upper) { 
    int count_inv_pair = 0; 
    // Do recusion untill the problem/array can be subdevided. 
    if (lower < upper) { 

     // Partition the Array into two subproblems. 
     int mid = (lower + upper)/2; 

     // Call the countInversionPair() function for these two 
     // subarrays/subproblems recursively to count number of 
     // inversion for these subproblems/subarrays. 
     count_inv_pair = countInversionPair(array, lower, mid); 
     count_inv_pair += countInversionPair(array, mid + 1, upper); 

     // Merge these two subarrays into a sigle array 
     count_inv_pair += merge(array, lower, mid, upper); 
    } 
    return count_inv_pair; 
} 

Jetzt zählen Sie können die Nummer des Inversionspaares erhalten, indem Sie die Funktion von main wie folgt aufrufen:

int count_inv_pair = countInversionPair(array, 0, size - 1); 

Und jetzt erhalten Sie Ihre Antwort ..

Answer 2

Vielen Dank für euch alle, vor allem @Shiv und @WhozCraig, Sie gaben mir und eine Idee, wie man es löst. Die Antwort lautet: q-1 zu q+j-k