アルゴリズムと計算量 (3): ソート
今日の内容
乱数
- 乱数とはランダムに現れる数の事で，それ以前に現れた数に依存せず，予想出来ない数である．
- ある領域の数が均一の確率で現れるものを一様乱数という．
- サイコロの目の出現が一様乱数の例となる．
- 正規分布に乱数の分布が従う正規乱数もある．
- Ruby では，関数 rand() で区間 [0,1) の一様実数乱数が，rand(n) で区間 [0,n) の一様整数乱数が生成される．
- 以下のような Ruby のプログラムで，配列 a に区間 [0,n) の m 個の乱数を代入する事が出来る．
a = Array.new(m)
for i in 0..a.length()-1
a[i] = rand(n)
end
- プログラムが生成する乱数は，本当の乱数ではなく，多くのパラメータを用いて本当の乱数に近付けた疑似乱数である．
単純ソートのアルゴリズムとその評価
[演習 9.1]
- 先週の授業で説明した単純ソートの関数 simplesort(a) を作りなさい．
関数の引数には，各要素に数の入った配列が渡されるものとする．
- 配列 a の各要素を乱数で埋めて，関数 simplesort(a) を実行し，配列の要素が小さい順に並び換えられる事を確認しなさい．
[問題 9.1]
- 単純ソートでの数の比較回数を値に持つ関数 simplesort_bench(a) を作りなさい．
- ソートする配列の長さをいろいろ変えて関数 simplesort_bench(a) の実験を行い，配列の長さ n に対する計算量を実験的に求めなさい．
- 関数 simplesort_bench(a) のプログラムと計算量の考察をメイルで授業時間内に提出すること．
- メイルの件名: CS入門 問題9.1
- メイルの本文に氏名と学籍番号を必ず書くこと．
- プログラムは添付ファイルにすること．
- 考察はメイル本文に書くこと．
- 東工大のアカウント以外から出されたメイルは受取らない．
マージソートのアルゴリズムとその評価
マージのプログラム
- 2つの配列をマージする関数 merge は以下のようなプログラムになる．
ただし，一部が抜けていて完成していない．
def merge(a, b)
c = Array.new(a.length + b.length)
ia = 0
ib = 0
ic = 0
while ia < a.length && ib < b.length
if a[ia] < b[ib]
c[ic] = a[ia]
ia = ia + 1
ic = ic + 1
else
c[ic] = b[ib]
ib = ib + 1
ic = ic + 1
end
end
while ia < a.length
c[ic] = a[ia]
ia = ia + 1
ic = ic + 1
end
c
end
[問題 9.2]
- 上記の関数 merge(a, b) をファイル mergesort.rb に保存しなさい．
- 関数 merge(a, b) を完成させなさい．
マージソートのプログラム
- 関数 merge を使ったマージソートの関数 mergesort は以下のようになる．
def mergesort(a)
n = a.length
from = Array.new(n)
for i in 0..n-1
from[i] = [ (a[i]) ]
end
while n > 1
to = Array.new((n+1)/2)
for i in 0..n/2-1
# 配列 from にある2つの列を，配列 to にマージする．
end
if n%2 != 0
to[n/2] = from[n-1]
end
from = to
n = (n+1)/2
end
from[0]
end
[問題 9.3]
- 上記の関数 mergesort(a) をファイル mergesort.rb に保存しなさい．
- 関数 mergesort(a) を完成させなさい．
Ruby の配列
- Ruby の配列では，配列の各要素に違う形のデータを保存する事が出来る．
- 例えば，単純ソートの関数 simplesort をソートした配列と要素の比較回数を同時に返す事も出来る．
def simplesort(a)
count = 0
for i in 0..a.length-2
for j in i+1..a.length-1
if a[i] > a[j]
a[i], a[j] = a[j], a[i]
end
count = count + 1
end
end
[a, count]
end
[問題 9.4]
- マージ関数 merge_bench(a,b) の返す値を配列とし，配列の第0要素がマージした結果の配列で，第1要素が要素の比較回数となるようにしなさい．
例えば，
c = merge_bench(a,b)
の場合には，c[0] に配列 a と配列 b をマージした配列，c[1] にマージの際に行われた要素の比較回数が入る．
- マージソートの関数 mergesort_bench(a) の返す値を配列とし，配列の第0要素がソートした結果の配列で，第1要素が要素の比較回数となるようにしなさい．
- ソートする配列の長さをいろいろ変えて，マージソートの関数 mergesort_bench(a) の実験を行い，配列の長さ n に対する計算量を実験的に求めなさい．
- プログラムをメイルで授業時間内に提出すること．
- メイルの件名: CS入門 問題9.4
- メイルの本文に氏名と学籍番号を必ず書くこと．
- プログラムは添付ファイルにすること．
- 計算量の考察はメイル本文に書きなさい．
- 東工大のアカウント以外から出されたメイルは受取らない．
来週の予告
- 来週の授業は教室で行います．
- 教科書を使いますので忘れずに持って来て下さい．
- 来週の授業の主な内容 (予定)
2012年11月17日作成
伊知地 宏
Copyright (C) Hiroshi Ichiji, 2012. All rights reserved.