マージソートでスタックオーバーフローが発生する

Question

このマージソートがスタックオーバーフローを引き起こす理由を理解できません。それは基本的なケースがないからです。それがあれば、どうすれば追加することができますか？ また、配列を再帰的に分割すると、データがどこに格納されているかを理解できないという問題があります。元の配列を分割すると分割されることが分かりますダウン個々の要素に、しかしどここれらの個々の要素は、このコードで問題の

Sub Main() 
    Dim Array() As Integer = {5, 4, 3, 1, 2, 6} 
    Dim right As Integer = Array.Length - 1 'find right index 
    Dim left As Integer = 0 'set left index 
    mergeSort(Array, left, right) 
End Sub 

Sub mergeSort(Array, left, right) 
    Dim middle As Integer 
    If left < right Then 
     middle = (left + right)/2 

     'recursively split both halves of the array 
     mergeSort(Array, left, middle) 
     mergeSort(Array, middle + 1, right) 

     'sort individual elements 
     mergeSortedArray(Array, left, middle, middle + 1, right) 
    End If 
End Sub 

Sub mergeSortedArray(ByRef Array, left, middle, rbeg, right) 
    Dim pt As Integer = 0 
    Dim TempArray(6) 

    While (left <= middle) And (rbeg <= right) 'sort every element 
     If Array(left) < Array(rbeg) Then 
      TempArray(pt) = Array(left) 
      left += 1 
     Else 
      TempArray(pt) = Array(rbeg) 
      rbeg += 1 
     End If 
     pt += 1 
    End While 

    If left > middle Then 
     While rbeg <= right 'left sub array exhausted 
      TempArray(pt) = Array(rbeg) 
      rbeg += 1 
      pt += 1 
     End While 
    Else 
     While left <= middle 'right sub array exhausted 
      TempArray(pt) = Array(left) 
      left += 1 
      pt += 1 
     End While 
    End If 

    For Each element In TempArray 
     Console.WriteLine(element & " ") 
    Next 
End Sub 

Answer 1

たくさんVBでマージソートがより次のようになります??格納されています。あなたが思い出すので

Sub Main() 
    Dim Array() As Integer = {5, 33, 3, 10, 2} 'make the array 

    'Split Array: you need the leftmost index & rightmost index 
    Split(Array, 0, 4) 
    Console.ReadKey() 

End Sub 

Sub Split(Array, left, right) 
    If left < right Then 'if the array has elements.. 
     Dim middle As Integer = (left + right) \ 2 'find halfway point 

     Split(Array, left, middle) 'split left array 

     Split(Array, middle + 1, right) 'split right array 
     'recursion keeps on splitting the two arrays until we have a bunch of single elements 

     'now sort and merge 
     Merge(Array, left, middle, right) 
    End If 
End Sub 
Sub Merge(ByRef Array, left, middle, right) 

    Dim SizeA As Integer = middle - left + 1 
    Dim SizeB As Integer = right - middle 
    Dim LeftArray(SizeA) As Integer 'set size of left array. 
    Dim RightArray(SizeB) As Integer 'set size of right array 

    'Left & Right pointers to keep track of what elements in the array we are referring to 
    Dim LP As Integer 
    Dim RP As Integer 

    For LP = 0 To SizeA - 1 
     LeftArray(LP) = Array(left + LP) 'assign 0 index of original array to left hand array (5) 
    Next 

    For RP = 0 To SizeB - 1 
     RightArray(RP) = Array(middle + 1 + RP) 'assign 1 index of original array to right hand array (33) 
    Next 

    'reset pointers 
    LP = 0 
    RP = 0 
    Dim i = left 'set a pointer for the original array 

    'swap elements if need be: 
    While LP < SizeA And RP < SizeB 
     If LeftArray(LP) <= RightArray(RP) Then 'if element in left array is smaller that the one in the right 
      Array(i) = LeftArray(LP) 'assign the left value to the original array 
      LP += 1 ' increment the left array's pointer 
     Else 
      Array(i) = RightArray(RP) 'otherwise the original array gets the right element 
      RP += 1 'increment the right array's pointer 
     End If 
     i += 1 'now increment the counter for our new array 
    End While 

    'Hang on...what if there are still elements in the left array 
    While LP < SizeA 
     Array(i) = LeftArray(LP) 'assign these elements to the new array 
     LP += 1 'increment the left pointer 
     i += 1 'increment the new array's pointer 
    End While 

    'Hang on...what if there are still elements in the right array 
    While RP < SizeB 
     Array(i) = RightArray(RP) 'assign these elements to the new array 
     RP += 1 'increment the right pointer 
     i += 1 'increment the new array's pointer 
    End While 

    'write out the new array 
    For Each element In Array 
     Console.Write(element & " ") 
    Next 
    Console.WriteLine("") 
    'start the second pass 
End Sub