2 コンピューターができることとソートの問題

2.1 コンピューターは何ができるのか?

ソートの問題を考える前に，コンピューター--正確にはC言語の命令--ができることを 示しておく必要があるだろう．コンピューターが何ができて，何ができないかを決めない と，ソートについて議論しても仕方がない．これは，コンピューターのハードウェアーの 問題に関わり，相当難しい問題であるので，証明無しで結論だけ述べよう．整列の問題を 考えれるときに，コンピューターができることは次の処理だけである．

• [比較と分岐]大小関係の比較が可能である．比較の結果により処理を分岐できる．
• [代入]変数や配列に，値をコピーすることが可能である．
• [繰り返し]同じ処理を繰り返すことが可能である．

例えば，数列の中から最大値を探すことすらできないのである．最大値を探したければ， これら3 つの処理を組み合わせる必要がある．ソートも同様で，これらの処理を組み合わ せて，高速に整数を並び替えなくてはならない．

2.2 ここで解く問題

この講義で解く問題は，配列にランダムに格納された整数を並び替える問題である．図 1に示すように，配列a[0]〜a[9]には整数がランダムに格納されている とする．これを先に示した3つの処理を使って，昇順--小さい順--に並び替えるのであ る．

このプリントでは，並び替える整数の個数は10個としているが，実際にはずーと大きな個数 のソートが必要となる．例えば秋田県の人の統計処理をする場合でも，100万程度のデー タがある．

図 1: ソートのアルゴリズムで解く問題．ここでは配列に格納された整数を昇順に 並べる．

ホームページ: Yamamoto's laboratory
著者: 山本昌志