第08回の Q & A

整列

たとえば 3,4,1,2,5 という5個の数字の並びを小さい順(昇順)に 1,2,3,4,5 と 並べかえるような操作を整列(ソート)といいます。整列のアルゴリズムについては 古来から様々な研究がなされてきていますが、その初歩的な部分について簡単に触れます。

テスト環境

おまじない require 'lib1' をプログラムの先頭へ 書くことにより

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

配列についての復習

問27: 配列の長さが2の場合

require 'lib1'  # おまじない

def sort2(a)
  # ここを考える
end

array = [2,1]       # [] の中はいろいろ変更してみる
print_array(array)
sort2(array)
print_array(array)
is_sorted(array)    # この表示が OK となるように

require 'lib1'  # おまじない

def sort2(a)     # 逆順ならば昇順に並べ変える
  if a[0] > a[1]
    t = a[0]; a[0] = a[1];  a[1] = t
  end
end

array = [2,1]       # [] の中はいろいろ変更してみる
print_array(array)
sort2(array)
print_array(array)
is_sorted(array)    # この表示が OK となるように

問28: 配列の長さが3の場合(1)

require 'lib1'  # おまじない

array = sample_array(3)   # ランダムに長さ3の配列を生成
print_array(array)
is_sorted(array)          

問29: 配列の長さが3の場合(2)

require 'lib1'  # おまじない

def sort3(a)
  # ここを考える、必要に応じて別の名前の(補助的な)関数を定義してもよい
end

array = sample_array(3)   # ランダムに長さ3の配列を生成
print_array(array)
sort3(array)              # array を整列   
print_array(array)
is_sorted(array)          # この表示が OK となるように

require 'lib1'  # おまじない

def sort3(a)
  if a[1] <= a[0]                     # (0)
    t = a[0]; a[0] = a[1]; a[1] = t   # a[0] と a[1] を交換
  end
  if a[2] <= a[0]                     # (1)
    t = a[0]; a[0] = a[2]; a[2] = t   # a[0] と a[2] を交換
  end
  # この時点で a[0] < a[1] かつ a[0] < a[2] となっている
  if a[2] <= a[1]                     # (2)
    t = a[1]; a[1] = a[2]; a[2] = t   # a[1] と a[2] を交換
  end
end

array = sample_array(3)
print_array(array)
sort3(array)
print_array(array)
is_sorted(array)

例

2 3 1
2 3 1 ... (0)
1 3 2 ... (1)
1 2 3 ... (2)

3 1 2
1 3 2 ... (0)
1 3 2 ... (1)
1 2 3 ... (2)

問30: 配列の長さが不定の場合(1)

require 'lib1'  # おまじない

def sort_n(a)
  # ここを考える、必要に応じて別の名前の(補助的な)関数を定義してもよい
end

n = 10                    # いろいろ変更してみる
array = sample_array(n)   # ランダムに長さnの配列を生成
print_array(array)
sort_n(array)             # array を整列 
print_array(array)
is_sorted(array)          # この表示が OK となるように

# いわゆる選択整列アルゴリズム
require 'lib1'  # おまじない

def sort_n(a)
  n = a.length
  for i in 0 ... n do     
    min = i 
    for j in i+1 ... n do
      if a[j] < a[min]
        min = j
      end
    end
    # この時点では、インデックスが i から n-1 の範囲で
    # 一番 a[min] が小さい値である
    t = a[i]; a[i] = a[min]; a[min] = t
  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  [min=8]
 1  8  7  6  5  4  3  2  9

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

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

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

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

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

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

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

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

問31: 配列の長さが不定の場合(2)

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

問32: 配列の長さが不定の場合(3)

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

require 'lib1'  # おまじない

def sort_n(a)
  n = a.length
  for i in 0 ... n do     
    min = i 
    for j in i+1 ... n do
      if a[j] < a[min]
        min = j
      end
    end
    t = a[i]; a[i] = a[min]; a[min] = t
  end
end


n = 10                    # いろいろ変更してみる
array = sample_array(n)
sort_n(array)
is_sorted(array)          

配列の大きさを n とすると内側の for 文で変数 j が動く範囲は i+1 から n-1 までの n-i 個、したがってプログラム全体での if 文の実行回数は

冬季レポートの提出