クイックソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。

C.A.R.Horeにより開発された（The Computer Journal, 5:10-15, 1962）整列法で、分割統治法の一種。平均的には最も早くO(nlogn)程度の実行時間であるが、最悪の場合はO(n^2)にまで落ちる。安定ではない。

クイックソートのアルゴリズムは、以下のとおり。
適当な値xを選ぶ（この時、x未満の要素数とx以下の要素数を同程度にする）
x未満の要素を前半に、x以上の要素を後半に集める
前半の要素数が2以上であれば前半をクイックソートする
後半の要素数が2以上であれば後半をクイックソートする

このように配列を約二分割して、自分自身を再帰的に整列する（分割統治）。しかしながら、うまく二分割できない場合（例えば、一方に1個、もう一方に残り全て）は実行時間がn^2に比例する。よって、実行速度は入力データに対する分け目の値xの選び方に左右される。a[first]やa[last]などはほとんど整列したデータに弱い。下で示した中央の値をとる方法以外に、
a[first]、a[last]、a[(first+last)/2]の中央値をとる
a[first]、a[last]間の乱数をとる
なども考えられる。

プログラミング掲示板「ソートロジック大会」なども参照のこと

分割統治
データをいくつかに分割して、その一つ一つについて自分自身を再帰的に適用すること

TypeDef keytype = Integer '
Sub quicksort(a As *keytype, first As Integer, last As Integer)
Dim i As Integer, j As Integer
Dim x As keytype, tmp As keytype
x = a[(first + last) / 2] '境界値として中間値をとる
i = first
j = last
While 1
While a[i] < x
i = i + 1
Wend
While x < a[j]
j = j - 1
Wend
If i >= j Then Exit While
tmp = a[i]
a[i] = a[j]
a[j] = tmp
i = i + 1
j = j - 1
Wend
'再帰呼び出し
If first < i - 1 Then quicksort(a, first, i - 1)
If j + 1 < last Then quicksort(a, j + 1, last)
End Sub

下記は再起呼び出しを行わないクイックソートである。ほとんど整列した配列に対してクイックソートはあまり早くないため、適当なところで挿入ソートに切り替えている。

TypeDef keytype = Integer
Const THRESHOLD = 10 '挿入ソートに切り替える境界値
Const STACKSIZE = 32 'たかだか Integer のビット数程度(>log2Nの数であること)
Sub quicksort(n As Integer, a As *keytype)
Dim i As Integer, j As Integer, left As Integer, right As Integer, p As Integer
Dim leftstack[STACKSIZE] As Integer
Dim rightstack[STACKSIZE] As Integer
Dim x As keytype '中間値
Dim tmp As Integer '入れ替え用
left = 0
right = n - 1
p = 0
While 1
If right - left <= THRESHOLD Then
If p = 0 Then Exit While
p = p - 1
left = leftstack[p]
right = rightstack[p]
End If
'境界地を中間値にする
x = a[(left + right) / 2]
i = left
j = right

While 1
While a[i] < x
i = i + 1
Wend
While x < a[j]
j = j - 1
Wend
If i >= j Then Exit While
tmp = a[i]
a[i] = a[j]
a[j] = tmp
i = i + 1
j = j - 1
Wend
If i - left > right - j Then
If i - left > THRESHOLD Then
leftstack[p] = left
rightstack[p] = i - 1
p = p + 1
End If
left = j + 1
Else
If right - j > THRESHOLD Then
leftstack[p] = j + 1
rightstack[p] = right
p = p + 1
End If
right = i - 1
End If
Wend
insertsort(n, a)
End Sub

'挿入ソート
Sub insertsort(n As Integer, a As *keytype)
Dim i As Integer, j As Integer
Dim x As keytype

For i = 1 To n
'整列の比較要素を定める
x = a[i]
'xよりも大きいものを右に寄せる
j = i - 1
While j >= 0
If a[j] <= x Then Exit While
a[j + 1] = a[j]
j = j - 1
Wend
a[j + 1] = x
Next i
End Sub