StackOverflowException in QuickSort

Question

Ich muss eine schnelle Sortierung verwenden, um einige sehr große Listen (Tausende von Elementen) zu bestellen. Wenn ich dies jedoch versuche, erhalte ich die Ausnahme System.StackOverflowException.

Von einigen schnellen googlen ich weiß, dass dies entweder von einer sehr großen Liste ist, habe ich jedoch diese Möglichkeit ausgeschlossen, indem Sie die Funktion auf einer kleinen Liste) oder von einer Subroutine rekursiv unendlich nennen. Obwohl das folgende Codebeispiel Rekursion verwendet, wenn ich einen Aufruf der Unterroutine Swap() lösche, wird die Ausnahme nicht mehr ausgeführt, obwohl Swap() keine anderen Unterroutinen aufruft.

Kann jemand irgendetwas sofort mit diesem Code falsch finden? Es ist das erste Mal, dass ich eine Rekursion verwende.

#Region "QuickSort" 
    'Subroutine for QuickSort, called upon recursively until list is sorted' 
    Private Sub QuickSort(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) 'min is index of first term, max is index of last term' 
     If min < max Then 'Checks if list is sorted' 
      Dim pivotLoc = Partition(list, min, max) 'Gets the next pivot position' 
      QuickSort(list, min, pivotLoc) 'Sorts the two new sublists' 
      QuickSort(list, pivotLoc + 1, max) 
     End If 
    End Sub 

    Private Function Partition(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) As Integer 
     Dim pivot = list(min, 0) 'Initially sets the pivot to be the minimum value in the list' 
     Dim leftWall = min 

     For i As Integer = min + 1 To max 'For each item in sublist' 
      If list(i, 0) < pivot Then 'If current item is less than the pivot swap it onto other side of pivot' 
       Swap(list, i, leftWall) 
       leftWall += 1 'Increment leftWall' 
      End If 
     Next 

     Swap(list, min, leftWall) 'When this line exists System.StackOverflowException occurs' 
     Return leftWall 
    End Function 

    'Subroutine that swaps values in list around using temporary storage variables' 
    Private Sub Swap(ByRef list(,) As Integer, ByVal x As Integer, ByVal y As Integer) 
     Dim tempVal = list(x, 0) 
     Dim tempIndex = list(x, 1) 

     list(x, 0) = list(y, 0) 
     list(x, 1) = list(y, 1) 

     list(y, 0) = tempVal 
     list(y, 1) = tempIndex 
    End Sub 
#End Region 

Danke, Alex.

EDIT: Wenn es jemand hilft, hier ist der Pseudo-Code ich es beruhte: here

Answer 1

Dies ist die Arbeitslösung:

#Region "QuickSort" 
    'Subroutine for QuickSort, called upon recursively until list is sorted' 
    Private Sub QuickSort(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) 'min is index of first term, max is index of last term' 
     If min < max Then 'Checks if list is sorted' 
      Dim pivotLoc = Partition(list, min, max) 'Gets the next pivot position' 
      QuickSort(list, min, pivotLoc) 'Sorts the two new sublists' 
      QuickSort(list, pivotLoc + 1, max) 
     End If 
    End Sub 

    Private Function Partition(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) As Integer 
     Dim pivot = list(min, 0) 'Initially sets the pivot to be the minimum value in the list' 
     Dim pivotIndex = list(min, 1) 
     Dim leftWall = min 

     For i As Integer = min + 1 To max 'For each item in sublist' 
      If list(i, 0) < pivot Then 'If current item is less than the pivot swap it onto other side of pivot' 
       Swap(list, i, leftWall) 
       leftWall += 1 'Increment leftWall' 
      End If 
     Next 

     'Swap(list, min, leftWall) 'When this line exists System.StackOverflowException occurs' 

     'Instead do this' 
     list(leftWall, 0) = pivot 
     list(leftWall, 1) = pivotIndex 

     Return leftWall 
    End Function 

    'Subroutine that swaps values in list around using temporary storage variables' 
    Private Sub Swap(ByRef list(,) As Integer, ByVal x As Integer, ByVal y As Integer) 
     Dim tempVal = list(x, 0) 
     Dim tempIndex = list(x, 1) 

     list(x, 0) = list(y, 0) 
     list(x, 1) = list(y, 1) 

     list(y, 0) = tempVal 
     list(y, 1) = tempIndex 
    End Sub 
#End Region