Memo-10.ソートとマージ（6）クイックソート

2026.08.28

ソートとマージについて（6）クイックソート
- ６.クイックソート

ソートとマージについて（6）クイックソート

６.クイックソート

配列の中のある要素を基準値とし、基準値より小さいグループと大きいグループ分割する作業を再帰的に繰り返すことによるソート方法です。

6.1　ソートされていく様子

6.2　フローチャート

このロジックもMergeSortと同様に再帰的アルゴリズムなので、ステップを順に追うようなプログラムフローを書くのは難しいです。下図は概略フローチャートです。
サンプルデータが整列されていく様子と併せて御覧下さい。

サンプルデータがソートされていく様子です。配列はゼロ起算です。

１回目の分割ロジックの説明です。
①検索範囲は、Left＝０，Right＝７です。
②基準値は、Data((left+right)\2)=51です。
③ix1=0 から右へ基準値以上の値を検索します。Data(3)=51を検出、ix1=3です。
④ix2=7 から左へ基準値以下の値を検索します。Data(7)=9を検出、ix2=7です。
⑤左側が基準値より小さい値、右側が大きい値になるように入替えます。
⑥まだ未検索の要素が残っているので、検索位置を進めます。ix1+1=4、ix2-1=6
⑦ix1=4 から右へ基準値以上の値を検索します。Data(6)=66を検出、ix1=6です。
⑧ix2=6 から左へ基準値以下の値を検索します。Data(5)=14を検出、ix2=5です。
⑨ix1>ix2 となり、互いの検索位置が交差したので終了、ここが分岐点です。
この処理を再帰的に実行していきます。

コードで書くと下記のようになります。
赤文字はPivot（基準点）、〇はix1の位置、□はix2の位置、⇔はデータ内容の交換です。
□Ａ、□Ｂは上記のフローチャートの※A、※Bに該当しています。
6.3　VＢＡのコードも参考にしてください。

6.3　ＶＢＡコード

クイックソートを呼び出すメイン処理です。
サンプルデータを用意して、実行後にソート結果を印刷しています。

'******************************************
'　　　クイックソート (main)
'******************************************
Public Sub TestQuickSort()
Dim data As Variant
Dim i As Long
Dim result As String
data = Array(44, 13, 21, 51, 8, 14, 66, 9)　　　　　　　’サンプルデータ
’
     Call QuickSort(data, LBound(data), UBound(data))
’ソート結果の印刷
     result=""
     For i = LBound(data) To UBound(data)
         result = result & Str$(data(i))　　　　　　　　　　　
     Next i
     Debug.Print ("result= " & result)
     End Sub

基準値以下の要素を左側、基準値以上の要素を右側に入替えながら分岐点を検索しています。
左右に分割していく処理を、各グループ内の要素がなくなるまで再帰的に繰り返しています。

Public Sub QuickSort(ByRef arr As Variant, ByVal left As Long, ByVal right As Long)
Dim ix1 As Long, ix2 As Long
Dim pivot As Variant, temp As Variant
'
ix1 = left
ix2 = right
     pivot = arr((left + right) \ 2) 　　' 配列の中央値を基準値とする
’
     Do While ix1 <= ix2                 ' 左右の検索位置が交差したら終了
         Do While (arr(ix1) < pivot)     ' 左側から基準値以上を探す
             ix1 = ix1 + 1
         Loop
         Do While (arr(ix2) > pivot)     ' 右側から基準値以下を探す
             ix2 = ix2 - 1
         Loop
         If ix1 <= ix2 Then              ' 左側が基準値以下、右側が基準値以上に
      　     temp = arr(ix1)             '         なるように値を入替える
             arr(ix1) = arr(ix2)
             arr(ix2) = temp
             ix1 = ix1 + 1               '左側の検索位置を次へ移動
             ix2 = ix2 - 1               '右側の検索位置を次へ移動
         End If
     Loop
 '左側に分割されたグループを再帰的処理
     If left < ix2 Then
A:      Call QuickSort(arr, left, ix2)
     End If
'右側に分割されたグループを再帰的処理
     If ix1 < right Then
B:      Call QuickSort(arr, ix1, right)
     End If
     End Sub