愚者の経験

「また今度」はほとんどこない

クイックソートと挿入ソートのハイブリッド

前回の投稿:配列をソート(並び替え)で挙げていた改善案の
「2.ある程度並べ替えできたら挿入ソートに移行」
を適用したクイックソートです。

実行時間が6割ほどになりました。

Public Sub QuickSort2(Data As Variant)
‘クイックソートと挿入ソートのハイブリッド
    Dim Stack As Dictionary
    Set Stack = New Dictionary
‘    Dim Stack As Object
‘    Set Stack = CreateObject(“Scripting.Dictionary”)
‘    Dim Stack As Collection
‘    Set Stack = New Collection
   
    Dim LeftIdx As Long
    Dim RightIdx As Long
    Dim Pivot As Variant
    Dim tPivot(2) As Variant
    Dim Temp As Variant
   
    Dim i As Long
    Dim j As Long
    Stack.Add Stack.Count + 1, LBound(Data)
    Stack.Add Stack.Count + 1, UBound(Data)
‘    Stack.Add LBound(Data), CStr(Stack.Count + 1)
‘    Stack.Add UBound(Data), CStr(Stack.Count + 1)
    Do While Stack.Count > 0
               
        LeftIdx = Stack(Stack.Count – 1)
        RightIdx = Stack(Stack.Count)
‘        LeftIdx = Stack(CStr(Stack.Count – 1))
‘        RightIdx = Stack(CStr(Stack.Count))
       
        Stack.Remove Stack.Count
        Stack.Remove Stack.Count
        ‘クイックソート
        If LeftIdx < RightIdx Then
       
            Pivot = Data((LeftIdx + RightIdx) / 2)
           
            i = LeftIdx
            j = RightIdx
           
            Do While i <= j
           
                Do While Data(i) < Pivot
                    i = i + 1
                Loop
           
                Do While Data(j) > Pivot
                    j = j – 1
                Loop
           
                If i <= j Then
                    Temp = Data(i)
                    Data(i) = Data(j)
                    Data(j) = Temp
                   
                    i = i + 1
                    j = j – 1
                End If
           
            Loop
           
            If RightIdx – i >= 0 Then
                If RightIdx – i <= 10 Then '分割した要素の数によって挿入ソートに移行
                    ComboInsertionSort Data, i, RightIdx
                Else
                    Stack.Add Stack.Count + 1, i
                    Stack.Add Stack.Count + 1, RightIdx
        ‘            Stack.Add i, CStr(Stack.Count + 1)
        ‘            Stack.Add RightIdx, CStr(Stack.Count + 1)
                End If
            End If
           
            If j – LeftIdx >= 0 Then
                If j – LeftIdx <= 10 Then '分割した要素の数によって挿入ソートに移行
                    ComboInsertionSort Data, LeftIdx, j
                Else
                    Stack.Add Stack.Count + 1, LeftIdx
                    Stack.Add Stack.Count + 1, j
        ‘            Stack.Add LeftIdx, CStr(Stack.Count + 1)
        ‘            Stack.Add j, CStr(Stack.Count + 1)
                End If
            End If
        End If
   
    Loop
   
‘    ArrayTest Data
End Sub

Public Sub ComboInsertionSort(Data As Variant, MinIdx As Long, MaxIdx As Long)
‘挿入ソート(別のソートとセットで利用)
    Dim i As Long, j As Long
    Dim Temp As Variant
    j = 1
    For j = MinIdx To MaxIdx
        i = j – 1
        Do While i >= 0
            If Data(i + 1) < Data(i) Then
                Temp = Data(i + 1)
                Data(i + 1) = Data(i)
                Data(i) = Temp
            Else
                Exit Do
            End If
            i = i – 1
        Loop
    Next
   
End Sub

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。