Stapelüberlauf Ausnahme in Quicksort

Question

Ich versuche, eine schnelle Sortierung zu machen, aber ich habe Probleme mit einer Stapelüberlauf Ausnahme in VB.net.

Die Sortierung funktioniert richtig, wenn x = 3, intermittierend, wenn x = 5 und bei einer Gelegenheit sortiert Hälfte der Liste, wenn x = 10.

Bitte geben Sie dank

Dim x As Integer = 10 
    Dim numArrray(x - 1) As Integer 

    For i = 0 To x - 1 
     Randomize() 
     numArrray(i) = CInt(Rnd() * 9) 
    Next 

    Quicksort(numArrray, 0, numArrray.Length - 1) 

    For i = 0 To x - 1 
     Console.Write(numArrray(i)) 
    Next 
    Console.ReadLine() 
End Sub 

Sub Quicksort(ByVal array() As Integer, ByVal min As Integer, ByVal max As Integer) 
    Dim pivot As Integer 

    If min < max Then 
     pivot = partition(array, min, max) 
     Quicksort(array, min, pivot - 1) 
     Quicksort(array, pivot + 1, max) 
    End If 
End Sub 

Function partition(ByVal array() As Integer, ByVal min As Integer, ByVal max As Integer) As Integer 
    Dim pivot As Integer = array(max) 
    Dim count As Integer = min - 1 
    Dim placeholder As Integer 

    For i = min To max - 1 
     If array(i) < pivot Then 
      count += 1 
      placeholder = array(count) 
      array(count) = array(i) 
      array(i) = placeholder 
     End If 
    Next 
    If array(max) < array(count + 1) Then 
     placeholder = array(count + 1) 
     array(count + 1) = array(max) 
     array(max) = placeholder 
    End If 
    Return count 

End Function 

Answer 1

Seit seiner ein stack overflow es wird in den geschachtelten Aufrufen von Quicksort sein, wenn man sich die Partition anschaut Ich denke, dass Sie einen Begrenzungsfehler haben, wie in dieser Version des Algorithmus en.wikipedia.org/wiki/Quicksort sollten Sie count + 1 von der Partition auf Ihrer Die Anzahl der aktuellen Implementierungen kann unter min beginnen und so bleiben, was eine unendliche Regression wäre, da Ihr verschachtelter Aufruf die gleichen Eingaben hätte (dh wenn y ou return count = min - 1 dann führen Sie einen rekursiven Aufruf zurück zu Quicksort (Array, Pivot + 1, Max) == Quicksort (Array, Min, Max)