CODEWITHSUNDEEP
vb.netsortingrecursionstack-overflow
Alex McKinney
Alex McKinney

Reputation: 51

StackOverflowException in QuickSort

I need to use a quick sort to order some very large lists (thousands of items). However when I attempt this I get the exception System.StackOverflowException.

From some quick googling I know this is either from having a very large list, however I have ruled out this possibility by using the function on a small list) or from having a subroutine called recursively infinitely. Although the bit of code below does use recursion when I remove one calling of the subroutine Swap() the exception stops happening, despite Swap() not actually calling any other subroutines.

Can anyone spot anything immediately wrong with this code? It is my first time using recursion.

#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

Thanks, Alex.

EDIT: If it helps anyone, here is the psuedo code I based it off: here

Upvotes: 0

Views: 151

Answers (1)

Alex McKinney
Alex McKinney

Reputation: 51

This is the working solution:

#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

Upvotes: 3

Related Questions