Как реализовать связанный список quicksort? (большая часть кода завершена)

Question

У меня возникли трудности с реализацией связанного списка quicksort в visual basic, и проблема в том, что это классический переполнение стека. Поскольку это рекурсивный алгоритм, я предполагаю, что это что-то довольно простое, которого я пропускаю, но я смотрел на это часами, прослеживая его на бумаге - он будет работать только с тремя элементами или меньше, а иногда и с четырьмя. Любая помощь приветствуется.

Алгоритм Я Ниже

1. Выберите элемент, который называется стержнем, из списка.
2. Переупорядочить список, чтобы все элементы со значениями, меньшими, чем точка поворота, приходили перед точкой поворота, а все элементы со значениями, превышающими точку поворота, приходили после него (равные значения могут идти в любом случае). После этого разбиения стержень находится в своем последнем положении. Это называется операцией раздела.
3. Рекурсивно применяйте вышеуказанные шаги к под-списку элементов с меньшими значениями и отдельно под-список элементов с большими значениями.

Переменная "countABC" содержит количество элементов в списке.

Вот код класса узла:

Public Class Node 
    'Each node contains the values for one value and is stored 
    'in the dynamic linked list. 
    Public Name As String 
    Public NextNode As Node 
    Public PKey As Integer 
    Public Sub New() 
     'Initializes a new node 
     Name = "" 
     NextNode = Nothing 
     PKey = 0 
    End Sub 
End Class 
Public start As Node 
Public Sub New() 
    'Initializes a new linked list by setting start as the first node 
    start = New Node 
End Sub 

Для добавления подпрограммы:

Public Sub AddABC(ByVal Name As String, ByVal PKey As Integer) 
    'Adds items to a dynamic linked list ordered in alphabetical order 
    Dim NewNode As New Node 
    Dim ptr As Node = start.NextNode 
    Dim prev As Node = start 
    NewNode.PKey = PKey 
    While ptr IsNot Nothing AndAlso ptr.Name < NewNode.Name 
     prev = ptr 
     ptr = ptr.NextNode 
    End While 
    NewNode.Name = Name 
    NewNode.NextNode = ptr 
    prev.NextNode = NewNode 
    countABC += 1 
End Sub 

И эти две функции, необходимые для сортировки (в списках присоединиться для конкатенации)

Public Function SortAlphabetically() As AllColumns 
    'This is a quicksort routine that creates a new linked list 
    '(that is not saved) in alphabetical order 
    If countABC > 1 Then 
     Dim pivotPkey As Integer = Math.Ceiling(countABC/2) 
     Dim pivot As New Node 
     Dim ptr As Node = start.NextNode 

     While ptr IsNot Nothing 
      If ptr.PKey = pivotPkey Then 
       pivot = ptr 
      End If 
      ptr = ptr.NextNode 
     End While 

     Dim lower As New AllColumns 
     Dim higher As New AllColumns 

     ptr = start.NextNode 

     While ptr IsNot Nothing 
      If ptr.Name < pivot.Name Then 
       lower.AddABC(ptr.Name, ptr.PKey) 
      Else 
       higher.AddABC(ptr.Name, ptr.PKey) 
      End If 
      ptr = ptr.NextNode 
     End While 

     Return (Joinlists(lower.SortAlphabetically, pivot, 
             higher.SortAlphabetically)) 

    Else 
     Return Me 
    End If 
End Function 

Private Function Joinlists(ByVal lower As AllColumns, 
          ByVal pivot As Node, 
          ByVal higher As AllColumns) As AllColumns 
    'Joins two dynamic linked lists together with a pivot value 
    'separating them 
    Dim list As AllColumns = lower 
    list.AddABC(pivot.Name, pivot.PKey) 

    Dim ptr As Node = higher.start.NextNode 

    While ptr IsNot Nothing 
     list.AddABC(ptr.Name, ptr.PKey) 
     ptr = ptr.NextNode 
    End While 
    Return list 

End Function 

Спасибо за чтение, надеюсь, я достаточно хорошо объяснил проблему и ничего не пропустил (что возможно, потому что это часть более крупной программы).

Редактировать

Вот полное определение класса и первого суб, который, надеемся объяснить это лучше:

Public Class AllColumns 
Public countABC As Integer = 0 
Public Class Node 
    'Each node contains the values for one value and is stored in the dynamic linked list. 
    Public Name As String 
    Public NextNode As Node 
    Public PKey As Integer 
    Public Sub New() 
     'Initialises a new node 
     Name = "" 
     NextNode = Nothing 
     PKey = 0 
    End Sub 
End Class 

Public start As Node 

Public Sub New() 
    'Initialises a new linked list by setting start as the first node 
    start = New Node 
    countABC = 0 
End Sub 

Это не тот случай, когда ниже и выше объявляются как " Новые Allcolumns "у них будут свои собственные значения для countABC, которые увеличиваются, когда узлы помещаются в список?

Я не думаю, что процедура навигации к оси, а затем сортировать все значения после этого, эта часть подпрограммы является фактическая сортировка, и «PTR» установлен в положение «start.nextnode», то есть. первый элемент в списке заранее.

ptr = start.NextNode 

    While ptr IsNot Nothing 
     If ptr.Name < pivot.Name Then 
      lower.AddABC(ptr.Name, ptr.PKey) 
     Else 
      higher.AddABC(ptr.Name, ptr.PKey) 
     End If 
     ptr = ptr.NextNode 
    End While 

    Return (Joinlists(lower.SortAlphabetically, pivot, 
            higher.SortAlphabetically)) 

Я должен был сделать это более понятным для начала, извинения.

Answer 1

Public Function SortAlphabetically() As AllColumns 
    'This is a quicksort routine that creates a new linked list 
    '(that is not saved) in alphabetical order 
    If countABC > 1 Then 
     ... 
     Return (Joinlists(lower.SortAlphabetically, pivot, 
             higher.SortAlphabetically)) 

countABC, кажется, ваш глобальный счетчик узлов, а не количество узлов для части вы сейчас сортировочной, так что это условие всегда будет истинными, и поэтому вы будете иметь бесконечную рекурсию.

Кроме того, где именно находится start, исходящий из (где он обновляется)?

Наконец, он смотрит на меня, как вы перемещаетесь к узлу поворота, а оттуда на добавление к левым и правым подспискам на основе сравнения, но как узлы перед поворотом?