0

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

そして、ソートに必要な 2 つの関数 (結合リストは連結用です)

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

下位および上位が「New 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))

最初にこれをもっと明確にするべきでした、申し訳ありません。

4

1 に答える 1