Was sollte in einer Mergesort-Merge-Funktion getan werden, wenn die Array-Länge geradzahlig ist, insbesondere in dem Fall, in dem Größe = 2 ist?

Question

Ich habe eine Mergesort-Merge-Funktion implementiert, aber obwohl ich sie so gut wie möglich kopiert habe, bin ich auf das Problem gestoßen, wenn die linken, mittleren, rechten Parameter 0,0,1 sind. In diesem Fall scheint die Logik völlig ruiniert zu sein. Wenn das Eingangsfeld 14,7 eingegeben wird, werden 14,7 ausgegeben. Der Grund ist, dass links == Mitte und so wird es sofort eingefügt.

Die Mergesort-Funktion hat hier Testfälle bestanden, aber es wird nur die Merge-Funktion debuggt.

Ich hätte gedacht, dass die 0,0,1 ist eine ungültige Parameter-Spezifikation, aber nein, gibt es keine andere Möglichkeit, das mittlere Element in einer Länge = 2-Array übergeben.

Ich habe versucht, meinen Code aus zur Basis von https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/code/MergeSort.java

// Takes in an array that has two sorted subarrays, 
// from [p..q] and [q+1..r], and merges the array 
var merge = function(array, p, q, r) { 
    console.log(array); 
    console.log(p); 
    console.log(q); 
    console.log(r); 
    var tmp = {}; 
    var k = p; 
    var middle = q; 
    while(p<=middle && q <= r){ 
    console.log("aaa"); 
    console.log(array[p]); 
    console.log(array[q]); 
    console.log("bbb"); 

    if (array[p] < array[q]){ 
     tmp[k] = array[p]; 
     k++; 
     p++; 
    } else { 
     tmp[k] = array[q]; 
     k++; 
     q++; 
    } 
    } 
    while(p<middle){ 
     //tmp[k] = array[p]; 
     k++; 
    p++; 
    } 
    while(r >= q){ 
     //tmp[k] = array[q]; 
     k++; 
    q++; 
    } 

    for(var i in tmp){ 
    array[i] = tmp[i]; 
    } 
    console.log(array); 
    console.log(tmp); 
    console.log("test"); 
}; 


// Takes in an array and recursively merge sorts it 
var mergeSort = function(array, p, r) { 
    var lowerIndex = p; 
    var higherIndex = r; 
      if (lowerIndex < higherIndex) { 
      var middle = Math.floor(lowerIndex + (higherIndex - lowerIndex)/2); 
      // Below step sorts the left side of the array 
      mergeSort(array,lowerIndex, middle); 
      // Below step sorts the right side of the array 
      mergeSort(array,middle + 1, higherIndex); 
      // Now merge both sides 
      merge(array,lowerIndex, middle, higherIndex); 
     } 
}; 

var array = [14, 7, 3, 12, 9, 11, 6, 2]; 
array = [14, 7]; 
mergeSort(array, 0, array.length-1); 
console.log("Array after sorting: " + array); 
//Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]); 

Answer 1

Der Index nur einer der Bereiche gehören Mitte muss. Im Moment verwenden Sie <= zu vergleichen, damit es zu beiden gehört.

Es scheint mir, dass es weniger verwirrend wäre, die allgemeinere Konvention zu verwenden, einen Bereich als den ersten Index auszudrücken, der Wert ist, und den ersten Index, der ungültig ist. Ihre Eingabe von 0,0,1 bedeutet, dass der erste Index über [0,0] einschließlich liegt und Ihr zweiter Index über [0,1] liegt. Sie vergleichen also die Daten bei array[0] mit sich selbst und fügen sie dann der Liste der Ausgaben hinzu. Wenn die Mittel- und Endpunkte exklusiv sind, bedeutet dies, dass die Eingabe für die Bereiche [0,1) und [1,2] eindeutig ist. (In einem Bereich bedeutet eine runde Klammer exclusive)

Answer 2

In Ihrer Nomenklatur sind die Array-Grenzen inklusive: Die untere Grenze ist das erste Element eines Bereichs, die höhere Grenze ist das letzte Element des Bereichs. Das mid Element ist das letzte Element des linken Sub-Array und daher die richtige Array beginnt mit mid + 1, wie Sie in Ihre Anrufe sehen:

 mergeSort(array, lowerIndex, middle);  // sort left array 
     mergeSort(array, middle + 1, higherIndex); // sot right array 

Aber in merge Sie mid nach rechts Bereich zuweisen: Der Index q sollte bei einem Element nach der Mitte beginnen. (Plus, verwenden Sie die Grenzen inkonsequent: In der ersten Schleife, in dem Sie das kleinste Element wählen entweder p oder q, Sie p<=middle testen, die mit Ihrer Nomenklatur konsistent ist und später verwenden Sie p<middle

Hier ist Ihre merge Funktion. korrigiert:

 var merge = function(array, p, middle, r) { 
      console.log(p, q, r); 
      var tmp = {}; 
      var k = p; 
      var q = middle + 1; 

      while(p <= middle && q <= r){ 
      if (array[p] < array[q]){ 
       tmp[k++] = array[p++]; 
      } else { 
       tmp[k++] = array[q++]; 
      } 
      } 

      while(p <= middle) tmp[k++] = array[p++]; 
      while(q <= r) tmp[k++] = array[q++]; 

      for(var i in tmp) array[i] = tmp[i]; 
     } 

I Pete zweiter Vorschlag exklusive obere Grenzen Verwendung in dieser Nomenklatur ist der Sub-Arrays ist array[lo:mid] und array[mid:hi], weil mid und hi, dessen init. ial Wert ist array.length, sind nicht Teil des Bereichs.