「クイックソート」の編集履歴(バックアップ)一覧はこちら
「クイックソート」(2010/01/25 (月) 19:23:24) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
整列アルゴリズムのひとつ。
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]間の乱数をとる
なども考えられる。
プログラミング掲示板「ソートロジック大会」なども参照のこと
分割統治
データをいくつかに分割して、その一つ一つについて自分自身を再帰的に適用すること
#asciiart(blockquote){
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
}
下記は再起呼び出しを行わないクイックソートである。ほとんど整列した配列に対してクイックソートはあまり早くないため、適当なところで挿入ソートに切り替えている。
#asciiart(blockquote){
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
}