In-Place-merge von zwei Arrays

Question

Wir haben eine Reihe von Größe m + n in denen m Elemente vorhanden, in sortierter Reihenfolge, und eine zweite Anordnung von Größe n, wieder in sortierter Reihenfolge. Wir wollen, dass beide sortiert und im ersten Array vorhanden sind. Kein drittes Array soll angegeben werden.

Beispiel:

1, 3, 55, 66, 77, _, _, _ 
    5, 9, 20 

Die Antwort sei:

1, 3, 5, 9, 20, 55, 66, 77 

Answer 1

Führen Sie eine regelmäßige Zusammenführungs-Sortierung durch, aber umgekehrt, indem Sie die größten Zahlen zuerst vergleichen, indem Sie (umgekehrt) in das Ende des ersten rückwärts laufenden Arrays speichern. Auf diese Weise werden die Elemente, die Sie zusammenführen, nie überschrieben (das funktioniert, ist leicht zu sehen, wenn Sie einen Moment darüber nachdenken).

Answer 2

bis zum Ende des ersten Arrays um den Inhalt des ersten Feldes verschieben

, so dass die leeren Elemente jetzt am Anfang sind . Dann füge die beiden Sequenzen wie üblich in das erste Array ein.

Answer 3

In-place erfordert grundsätzlich nur "konstante" Speichermenge, die sich bei verschiedenen Array-Größen nicht ändert. Die Frage selbst weist jedoch eine zusätzliche Speichermenge zu, die der Größe eines der beiden Eingabearrays entspricht, was im schlimmsten Fall O (n) Speicher ist. Dies macht im Grunde die Idee des „in-place“ sinnlos ...

Die Frage wäre vielleicht besser als „ohne zusätzlichen Speicher merge“ formuliert werden, die eine genauere Beschreibung der wirklichen Absicht ist ...

Answer 4

// merge the elements in B[] to A[], starting from the last one 
    void merge(int A[], int m, int B[], int n) { 
     // m-1 and n-1 represent the current element index in A[] and B[] respectively 
     while (n > 0) { // there are still elements in B[] not merged 
      if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[] 
      A[m+n-1] = A[m-1]; // move current element of A[] to its right position 
      --m; // decrease current element index of A[] 
      } 
     else { // current element in A[] <= current element in B[] 
      A[m+n-1] = B[n-1]; // move current element in B[] to its right position 
      --n; // decrease current element index of B[] 
     } 
     } 
    }