前回のQA

クイックソート

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

• a[0] から a[i-1] までの要素は a[i] の値以下
• a[i+1] から a[n-1] までの要素は a[i] の値以上

• a[0] から a[i-1] までを整列
• a[i+1] から a[n-1] までを整列

したがって、配列 a の a[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

このような整列アルゴリズムをクイックソートといいます。 実用的には最速の整列法(たいていの場合は 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: 以下の配列をクイックソートプログラムで整列してみましょう。

• [5,4,3,2,1]
• [0,1,0,1,0,1,0,1]
• [11,31,71,91,32,92,13,73,14,34,74,35,95,16,76]
• [701,901,311,721,131,731,931,941,101,301]

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

時間計測の例:

整列についてのおさらい

• 配列の要素を(ここでは昇順のみに限ります)並べ替える操作を整列(ソート)といいます。
• 選択整列、挿入整列、クイックソートという3種類の整列アルゴリズムがあります。
• 選択整列・挿入整列アルゴリズムでは、たいていの場合、配列の長さの2乗に比例した回数の比較が必要です。
• クイックソートアルゴリズムでは、たいていの場合、n log n (n は配列の長さ)に比例した回数の比較で十分です。
• プログラム例

  lib1.rb

  テスト環境用、おまじない require 'lib1' を書くことにより

  • is_sorted(array) … 配列 array が昇順に整列されているかどうかをコンソールに表示
  • sample_array(n) … 各要素を 0〜n-1 からランダム(でたらめ)に選んだ、長さ n の配列を生成
  • print_array(array) … 配列 array の内容をコンソールに表示

  という3つの関数が使えるようになります。

  lib2.rb

  共通の操作をまとめてある、保存後、おまじない require 'lib2' を書くことにより利用可能。

  sort.rb

  整列プログラムの本体(例)。

  sorttest.rb

  テストプログラム(例)。

  require 'lib1'
  require 'sort'
  
  n = 10	  
  a = sample_array(n)
  print_array(a)	  
  # insertion_sort(a)  # どれか1つの 
  # selection_sort(a)  # コメントを
  # quick_sort(a)      # 外して実行
  print_array(a)
  is_sorted(a)
  

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

• [9,8,7,6,5,4,3,2,1]
• [0,1,0,-1,0,1,0,-1,0]
• [299,548,869,744,756,975,766,364,768,508,842,85,862]

期末レポート

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

その他

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