How to implement linked list quicksort? (most of code complete)

Question

I am having some difficulty implementing a linked list quicksort in visual basic, and the problem is the classic stack overflow. As it is a recursive algorithm I assume it is something fairly simple I am missing, but I have been staring at this for hours, tracing it on paper - it will only ever work with three items or less, sometimes four. Any help would be much appreciated.

The algorithm I am following is

Pick an element, called a pivot, from the list.
Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

The variable "countABC" holds the number of items in the list.

Here is the code for the node class:

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

For the add routine:

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

And the two functions needed to sort (the join lists is for concatenation)

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

Thanks for reading, I hope I've explained the problem well enough and haven't missed anything out (which is possible because it's part of a larger program).

Edit

Here is the complete class definition and first sub, which will hopefully explain it better:

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

Is it not the case that as lower and higher are being declared as "New Allcolumns" they will have their own values for countABC that are incremented when nodes are put into the list?

I don't think the routine is navigating to the pivot and then sorting all values after it, this part of the routine is the actual sorting, and "ptr" is set to "start.nextnode" ie. the first item in the list beforehand.

 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))

I should have made this more clear to begin with, apologies.

500 - Internal Server Error 500 - Internal Server Error · Accepted Answer · 2013-04-04T01:19:44

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 appears to be your global node count, not the node count for the subsection you are currently sorting, so this condition is always going to be true and so you'll have infinite recursion.

Also, where exactly is start coming from (where is it updated)?

Finally, it looks to me like you are navigating to the pivot node and from there on adding to the left and right sub-lists based on the comparison, but what about the nodes before the pivot?

How to implement linked list quicksort? (most of code complete)

1 Answers