整列したい配列を 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 回実行されます。 したがって最悪の場合、比較・代入操作が
n の値を 5,10,15,20,25,30 と変更して上記のプログラムを実行してみましょう。
上記のプログラムで print_array の呼出しを削除した上で n の値を 100,500,1000,2000,5000 と変更して実行してみましょう。 n の値がどのあたりから目に見えてプログラムが遅くなるでしょうか。