「クイックソート」の編集履歴(バックアップ)一覧はこちら

クイックソート」(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 }

表示オプション

横に並べて表示:
変化行の前後のみ表示: