stack overflow exception in quicksort

Question

I am trying to make a quick sort however i am having trouble with a stack overflow exception in VB.net.

The sort works correctly when x = 3, intermittently when x = 5 and on one occasion sorted half of the list when x = 10.

Please advise, thanks

    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

This will not compile, have you tried debugging and stepping through? — Trevor
– Trevor, Commented Oct 18, 2017 at 11:09
Since its a stack overflow it will be in the nested calls to Quicksort, looking at partition I think you have a bounds error, as per this version of the algorithm en.wikipedia.org/wiki/Quicksort you should return count + 1 from partition, on your current implementation count can start below min and stay that way which would be an infinite regression as your nested call would have the same inputs (ie if you return count = min - 1 then you do a recursive call back to Quicksort(array, pivot + 1, max) == Quicksort(array, min, max) — tolanj
– tolanj, Commented Oct 18, 2017 at 11:19

tolanj · Accepted Answer · 2017-10-18 11:43:38Z

2

Since its a stack overflow it will be in the nested calls to Quicksort, looking at partition I think you have a bounds error, as per this version of the algorithm en.wikipedia.org/wiki/Quicksort you should return count + 1 from partition, on your current implementation count can start below min and stay that way which would be an infinite regression as your nested call would have the same inputs (ie if you return count = min - 1 then you do a recursive call back to Quicksort(array, pivot + 1, max) == Quicksort(array, min, max)

answered Oct 18, 2017 at 11:43

tolanj

3,74418 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

stack overflow exception in quicksort

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related