Top | INDEX | UP

コンピュータ概論 第11回


前回のQA


クイックソート

整列したい配列を a ( a[0]a[n-1] ) とします。 もし n=1 ならば配列の要素は1個ですから、すでに整列されています。 n>1 の場合、てきとうな i に対して

となっていれば a[i] はすでに「正しい位置」にあるので することにより配列 a 全体が整列されることとなります。

したがって、配列 aa[left] から a[right] まで を整列する関数を

def qsort(a, left, right)
  if left < right
    ある i に対して
      a[left] から a[i-1] までが ≦ a[i]
      a[i+1] から a[right] までが ≧ a[i]
    となるよう a を並べ替える(「a[i] を軸として分割」)
    qsort(a, left, i-1)
    qsort(a, i+1, right)
  end
end
と定義すれば qsort(a, 0, n-1) を実行することにより 配列 a 全体が整列されることとなります。

このような整列アルゴリズムをクイックソートといいます。 実用的には最速の整列法(たいていの場合は n log n に比例する程度の比較回数でよい)と考えられています。

require 'lib1' # おまじない

def swap(a, i, j) # a[i] と a[j] を交換する
  t = a[i]
  a[i] = a[j]
  a[j] = t
end

def qsort(a, left, right) # クイックソートの本体
  if left < right
    v = a[right]   # この要素を left〜right の間の正しい位置へ移動
    i = left-1
    j = right
    while true
      # このループ内の条件は微妙なため単純に < を <= に
      # 変更したりすると動作が正しくなくなるので注意
      i+=1; while a[i] < v do; i+=1; end
      j-=1; while a[j] > v do; j-=1; end
      if i >= j; break; end  # while ループを終了
      swap(a, i, j)
    end
    swap(a, i, right)
    # この時点で a[i] を軸として分割終了
    qsort(a, left, i-1)
    qsort(a, i+1, right)
  end
end

def quick_sort(a) # 配列 a をクイックソート・アルゴリズムで整列する
  n = a.length
  qsort(a, 0, n-1)
end

n = 10                   # いろいろ変更してみる
array = sample_array(n)  # ランダムに長さnの配列を生成
print_array(array)       # n が大きいときはコメントアウトする
quick_sort(array)
print_array(array)       # n が大きいときはコメントアウトする
is_sorted(array)         # この表示が OK とならなければ動作がおかしい
例
----------------------------------------------------------------------
      0  1  2  3  4  5  6  7  8 (添字/インデックス)
 a = [66 77 56 66 74 44 90 89 58]

qsort(a,0,8)
 0  1  2  3  4  5  6  7  8
66 77 56 66 74 44 90 89 58 -> swap(a,0,5) -> swap(a,1,2) -> swap(a,2,8)
44 56 58 66 74 66 90 89 77 -> i=2 -> qsort(a,0,1) , qsort(a,3,8)

qsort(a,0,1)
 0  1  2  3  4  5  6  7  8
44 56 58 66 74 66 90 89 77 -> swap(a,1,1)
44 56 58 66 74 66 90 89 77 -> i=1 -> qsort(a,0,0), qsort(a,1,1)

qsort(a,3,8)
 0  1  2  3  4  5  6  7  8
44 56 58 66 74 66 90 89 77 -> swap(a,6,8)
44 56 58 66 74 66 77 89 90 -> i=6 -> qsort(a,3,5), qsort(a,7,8)

qsort(a,3,5)
 0  1  2  3  4  5  6  7  8
44 56 58 66 74 66 77 89 90 -> swap(a,3,5)
44 56 58 66 74 66 77 89 90 -> i=3 -> qsort(a,3,2), qsort(a,4,5)

qsort(a,4,5)
 0  1  2  3  4  5  6  7  8
44 56 58 66 74 66 77 89 90 -> swap(a,4,5)
44 56 58 66 66 74 77 89 90 -> i=4 -> qsort(a,4,3), qsort(a,5,5)

qsort(a,7,8)
 0  1  2  3  4  5  6  7  8
44 56 58 66 66 74 77 89 90 -> swap(a,8,8)
44 56 58 66 66 74 77 89 90 -> i=8 -> qsort(a,7,7), qsort(a,9,8)
----------------------------------------------------------------------

問35: 以下の配列をクイックソートプログラムで整列してみましょう。

問36: n を 50, 100, 500, 1000, 2000, 5000, 10000 と大きくしたとき のクイックソートプログラムの実行時間はどのようになるでしょうか。

時間計測の例:


整列についてのおさらい

問37: 以下の配列を{選択整列・挿入整列・クイックソート} で整列してみましょう。


期末レポート

配布資料(PDF) を参照のこと。


その他

私は非常勤のため、学内にはいません。したがって、質問などありましたらメール (nagoya@u-gakugei.ac.jp)でお願いします。