Top | INDEX | UP

コンピュータ概論 第10回


前回のQA


冬季レポート解説


整列(続)

選択整列アルゴリズム

前回の続き

挿入整列アルゴリズム

整列したい配列を a[0] … a[n-1] とします。 a[0] … a[i-1] までが整列していると仮定します。 そうしますと a[0] … a[i-1] の中で a[i] より 大きい 要素を順に1つずつ後ろにずらして、空いた要素に a[i] を 移動すると a[0] … a[i] までが整列していることになります。 この操作を(i=0 の場合は必ず成立しているので何もしなくてよい) 繰り返すことにより最終的には a[0] … a[n-1] まで整列することになります。

require 'lib1'  # おまじない

def sort_n(a)
  n = a.length
  for i in 0 ... n do        # i: 0 -> n-1
    v = a[i]
    j = i-1                  
    while j>=0 and a[j] > v  # j: i-1 -> ...
      a[j+1] = a[j]          
      j -= 1                 
    end
    a[j+1] = v
  end
end

n = 9                    # いろいろ変更してみる
array = sample_array(n)   # ランダムに長さnの配列を生成
print_array(array)
sort_n(array)
print_array(array)
is_sorted(array)          # この表示が OK となるように
0  1  2  3  4  5  6  7  8 (インデックス)
 9  8  7  6  5  4  3  2  1

 [i=0]
 9  8  7  6  5  4  3  2  1  [v=9]
 9  8  7  6  5  4  3  2  1

 [i=1]
 9  8  7  6  5  4  3  2  1  [v=8]
 8  9  7  6  5  4  3  2  1

 [i=2]
 8  9  7  6  5  4  3  2  1  [v=7]
 7  8  9  6  5  4  3  2  1

 [i=3]
 7  8  9  6  5  4  3  2  1  [v=6]
 6  7  8  9  5  4  3  2  1

 [i=4]
 6  7  8  9  5  4  3  2  1  [v=5]
 5  6  7  8  9  4  3  2  1

 [i=5]
 5  6  7  8  9  4  3  2  1  [v=4]
 4  5  6  7  8  9  3  2  1

 [i=6]
 4  5  6  7  8  9  3  2  1  [v=3]
 3  4  5  6  7  8  9  2  1

 [i=7]
 3  4  5  6  7  8  9  2  1  [v=2]
 2  3  4  5  6  7  8  9  1

 [i=8]
 2  3  4  5  6  7  8  9  1  [v=1]
 1  2  3  4  5  6  7  8  9

配列の大きさを n とすると外側の for 文で変数 i が動く範囲は 0 から n-1 まで、そのとき内側の while 文は最大 i 回実行されます。 したがって最悪の場合、比較・代入操作が

0 + 1 + 2 + ... (n-1) = n(n-1)/2
くらい実行されることになります。したがって、 挿入整列アルゴリズムの計算時間は大雑把なところ n2 に比例して増大することがわかります。

問33: 配列の長さが不定の場合(4)

n の値を 5,10,15,20,25,30 と変更して上記のプログラムを実行してみましょう。

問34: 配列の長さが不定の場合(5)

上記のプログラムで print_array の呼出しを削除した上で n の値を 100,500,1000,2000,5000 と変更して実行してみましょう。 n の値がどのあたりから目に見えてプログラムが遅くなるでしょうか。