Selection Sort - Stack Overflow

Question

Hi I am trying to implement Selection Sort in vb.net using recursion. Problem is that I keep getting stackoverflow if the array I want to sort is 1000 elements. I can't find the problem. I don't know much about stack overflow or how to check it. From my research the problem could be infinite recursion but I check for that and exit the sub.Here is the main code:

Public Class SelectionSort
Inherits DefaultSort


Public Sub New(ByVal num As Integer)
    Me.CreateArray(num)
    Me.ShowArray()
    Me.StartWatch()
    Me.Sort(Arr.Length - 1, 0, 1)
    Me.StopWatch()
    Me.ShowArray()
    Me.ShowExecutionTime()
End Sub





Private IsSorted As Boolean = False
Public Overridable Sub Sort(ByVal arrLen As Integer, ByVal pos As Integer, ByVal minval As Integer)



    If pos >= arrLen Then
        IsSorted = True
    End If

    If IsSorted = True Then
        Exit Sub
    End If



    Dim minKey As Integer = Array.IndexOf(Arr, minval + pos)
    Dim temp As Integer = Arr(minKey)


    Arr(minKey) = Arr(pos)
    Arr(pos) = temp
    pos += 1

    Sort(arrLen, pos, minval)
    If pos >= arrLen Then
        IsSorted = True
    End If

    If IsSorted = True Then
        Exit Sub
    End If

End Sub

End Class

Everything inside the constructor is set in the base class "DefaultSort", except for the Sort(). The array is set using properties:

Public Overridable Property Arr() As Integer()

    Get
        Return _array
    End Get

    Set(ByVal value() As Integer)
        _array = value
    End Set

End Property
Private _array() As Integer

Everything should work as far as I know. It works on an array of 10 elements and an array of 100 elements.

Any ideas, stuck!!! :)

Answer 1

Don't use a recursion for this. Use an iterative solution instead

Update: If you look at doc for StackOverflowExectpion it says

The exception that is thrown when the execution stack overflows because it contains too many nested method calls.

The way this sort is written each element is visited with a recursive method call. e.g. the first element calls sort for the second element which calls sort for the third element and so on. This means that the recursion depth is equal to the number of member (I might be off by +/- 1).

This means that if you have enough elements you'll get a StackOverflow.

I copied your code and ran it and below is the truncated Call Stack thats shows that the sort gets called on each pos recursively and that it dies when there's more than 8,314 elements.

MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8314, Integer minval = 1) Line 67 + 0xb bytes  Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8314, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8313, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8312, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8311, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8310, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8309, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8308, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8307, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8306, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8305, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8304, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8303, Integer minval = 1) Line 75 + 0x14 bytes Basic
MyApp.exe!MyApp.SelectionSort.Sort(Integer arrLen = 10000, Integer pos = 8302, Integer minval = 1) Line 75 + 0x14 bytes Basic