Quicksort Rekursion

Question

So habe ich erfolgreich ein Quicksort implementiert, das das Element ganz links als Pivot jedes Mal verwendet. Ich habe versucht, Quicksort mit dem mittleren Element zu implementieren und einige komplizierte Ergebnisse zu haben. Ich habe von Beispielen gearbeitet, die sich Quicksort rekursiv selbst aufrufen, ohne die Aufrufe in irgendeiner Art und Weise zu umhüllen, und wie Sie sich vorstellen können, bleibt es beim ersten Aufruf an sich hängen.

Die ersten Aufrufe zur Partitionierung mit den Samples, die ich verwendet habe, partitionieren das Array korrekt, dann, als es sich dem Ende nähert, tauscht einfach die zwei der Elemente am Anfang immer und immer wieder.

Die Strategie, die ich versuche, ist, das mittlere Element aus der Liste als Pivot auszuwählen, es am Ende des Arrays zu verstauen und dann mit dem Tausch der Indizes fortzufahren. Nachdem es abgeschlossen ist, lege ich den Drehpunkt zwischen die partitionierten Arrays. Sieht nach ein paar Pässen gut aus, aber wie ich schon erwähnt habe, bleibt er früh dran und kommt nie zum Aufruf, der die zweite Partition sortieren soll.

alle nudges wären sehr dankbar - ich auch in stark arbeitet, wenn Sie etwas sehen, aus (und hoffentlich, dass verursacht keine Probleme, aber ich vermied Duck Typing für diesen

der Original-Array ist

[100, 305, 2, 2002, 18, 99, 211, 30, 50, 1000, 403, 4, 400, 77]

und als Stapelüberlauf

das Array erreicht ist

[2, 4, 18, 30, 50, 99, 77, 100, 211, 1000, 403, 305, 400, 2002]

class OtherQuickSort { 

static void sort(int[] array){ 

    quickSort(array, 0, array.length - 1) 

} 

static void quickSort(int[] array, int first, int last){ 
     int pivotIndex = partition(array, first, last) 

     quickSort(array, first, pivotIndex - 1) 
     quickSort(array, pivotIndex, last) 
} 

static int partition(int[] array, int first, int last){ 
    int pivotIndex = (first + last)/2 
    int pivotValue = array[pivotIndex] 

    swapIndices(array, pivotIndex, last) 

    int indexFromRight = last - 1 
    int indexFromLeft = first 

    while(indexFromLeft <= indexFromRight){ 
     while(array[indexFromLeft] < pivotValue){ 
      indexFromLeft++ 
     } 
     while(array[indexFromRight] > pivotValue){ 
      indexFromRight-- 
     } 

     if(indexFromLeft <= indexFromRight) { 
      swapIndices(array, indexFromLeft, indexFromRight) 
      indexFromLeft++ 
      indexFromRight-- 
     } 
    } 

    swapIndices(array, indexFromLeft, last) 

    indexFromLeft 
} 

static void swapIndices(int[] array, int left, int right){ 
    int leftValue = array[left] 
    array[left] = array[right] 
    array[right] = leftValue 
} 
} 

Answer 1

Sie müssen Ihre quickSort-Methode aktualisieren. Der Wert im pivotIndex ist bereits in seiner sortierten Position, sodass Sie ihn nicht erneut übergeben müssen.

static void quickSort(int[] array, int first, int last){ 
    if(last > first){ 
     int pivotIndex = partition(array, first, last); 

     quickSort(array, first, pivotIndex-1); 
     quickSort(array, pivotIndex+1, last); 
    } 
}