１ ソートの原理

２ 実験手順

まず、各アルゴリズムのプログラムを作成・実行し、動作の原理を理解する。

時間は含まない）。数列ファイルの大きさは、500、1000、5000、10000を使った。

（ファイルの大きさは、2倍10倍の要素が考えやすいので、この大きさにした）

数列ファイルの大きさは時間計測と同じ、500、1000、5000、10000を使った。

３ 各アルゴリズムの実験結果と考察

計測された時間は、少数点以下は「…000」「…333」「…667」のどれかで、（プログラムを工夫しないと）細かい時間は計測しきれないので少数点以下4桁目を四捨五入している。

compare++; /* 比較のカウント */

exchange++; /* 交換のカウント */

｝

｝

比較回数は、外側のfor文と内側のfor文の回数を掛けた値になる。

外側のfor文はm−１回行われ、内側のfor文は（最初はm−１回、最後が1回なので）平均m/2になる。

（m-1） × m/2 ＝ �u／２−ｍ／２

また、比較回数の最大次数の項が�u なのでバブルソートのオーダーは�u になる。

図１−１ バブルソートの比較回数／交換回数

（m−１）×m／２

• 昇順の交換回数は要素数が増えても交換する必要がないので0回である。
• 降順の交換回数は比較するたびに交換するため、比較回数と同じになっている。

図１−２ バブルソートの実行時間と実行時間の理論値

・実行時間の理論値はデータファイル毎に実行時間÷各要素数の�u の値を加算し、４で割り、その値を各要素数の�u を掛けた値とした。

（例えば、昇順では、0.017÷250000 ＋ 0.067÷1000000 ＋ 1.617÷25000000 ＋ 6.517÷100000000 の値を４で割った値を基準として、要素数が500なら、250000を掛けた値が実行時間の理論値となる。）

実験に使用したワークステーションの処理速度が速いことと、プログラムで計測できる時間の最小が0.0166… であったため、要素数500の実行時間は不正確である。（バブルソート以外のアルゴリズムでも不正確になってしまっている。）要素数５００以外の3つは、実行時間÷�u の値が近い値になっても、要素数500だけ、他とずれてしまうことがあり、その実行時間の理論値は、ずれてしまう。（バブルソートの場合、降順理論値は、要素数500だけ、理論値が大きくなってしまい、他３つは理論値の方が小さくなってしまう。）

• 実行時間は要素数が増えると�u に比例して増加し，昇順・ランダム・ランダム（重複なし）において比較回数・交換回数とも要素数が10倍になると，交換回数は100倍になった。
• バブルソートのオーダーは、比較回数が一番手間がかかり、�u が最大の項になるので
• オーダー�u になり、参考文献と一致する。
• バブルソートは，繰り返すための２つのカウンタ（プログラムの例ではｊとｉ）と交換の待避ためのデータ（プログラムの例では ｔ）の3つしかメモリを使わず，配列の大きさに合わせた配列を宣言する必要が無いのでメモリ効率は良い。
• アルゴリズムの理解がしやすく，プログラミングが容易である。
• バブルソートは隣同士しか交換しないのを改良して、離れた要素を比較交換すると実行時間が早くなると考えられる。

compare++; /* 比較回数のカウント */

exchange++; /* 交換回数のカウント */

・交換回数は外側のfor文のループ回数なので、（m−１）になる。

・比較回数はif文の実行回数なので内側のfor文のループ回数 m/2

と外側のfor文のループ回数m-1を掛けた値

（m−１）×m／２ ＝ �u／２− ｍ／２

図２−１ 選択ソートの比較回数／交換以外の代入回数（if文内でlowkeyに代入された回数）

比較・交換回数は理論値と一致した。（要素数が10倍になれば，比較交換回数は100倍になる）

（図２では交換回数ではなく、if文の中で最小値の添え字（lowest）と最小値（lowkey）に代入が行われた回数を載せる。）

・降順では、要素数が2倍になれば、if文内でlowkeyに代入された回数は４倍になることが解る。

・降順でのif文内での代入回数は比較回数の半分に近い。これは、未整列部分の先頭（降順なら

・降順以外の実行時間は比較・交換回数が同じなためあまり違いが出なかった。降順はif文の中のlowkeyとlowestへの代入がたくさん発生するので他よりも時間が掛かる。（lowkeyには一番左側の値を最初代入するので降順では未整列部分の最小値を代入することになり、比較する度にlowkeyへの代入が発生する。）

図２−２ 選択ソートの実行時間／実行時間の理論値

• 実行時間の理論値はデータファイル毎に実行時間÷各要素数の�u の値を加算し、４で割り、その値を各要素数の�u を掛けた値とした。

実験に使用したワークステーションの処理速度が速いことと、プログラムで計測できる時間の最小が0.0166… であったため、要素数500の実行時間は不正確である。要素数５００以外の3つは、実行時間÷�u の値が近い値になっても、要素数500だけ、他とずれてしまうことがあり、その実行時間の理論値は、ずれてしまう。降順以外は実行時間とその理論値は少し離れてしまった。

• 実行時間は，�u に比例して，要素数が10倍になれば，実行時間は100倍近い値になっている。
• 選択ソートは比較回数の（m−１）×m／２が一番手間が掛かり、最大次数の項に�u があるのでオーダー�u となり、参考文献と一致する。
• 選択ソートは，繰り返すための２つのカウンタ（ｊとｉ）と交換の待避ためのデータ（ｔ）と最小値と最小値の添え字（lowkeyとlowest）の５つしかメモリを使わず，配列の大きさに合わせた配列を宣言する必要が無いのでメモリ効率は良い。
• アルゴリズムの理解がしやすく，プログラミングが容易である。

・選択ソートを改善するには、最小値のlowkeyとlowestだけでなく、最大値もスキャン時に探すことによって、配列の両側から整列済みになり、実行時間が早くなると考えられる。

・スキャンする前のlowkeyへの代入を、左端・中央・右端の中の最小値を選べば、降順だけ少し実行時間が掛かるのを防ぐことができると考えられる。

compare++; /* 比較回数 :/

exchange++; /* 交換回数 */

・挿入ソートはfor文がm−１回実行され，while文は平均ｉ／２回実行されるため，挿入ソートのオーダーは�u となり、参考文献と一致する。

図３−１ 挿入ソートの比較回数／交換回数

・昇順では、交換回数が０で、比較回数もm−１のため、時間が掛からず、要素数1万でも

・ランダムの比較交換回数は降順の比較交換回数の半分に近い値になっている。乱数なので、バラつきがちょうど、降順（1番手間が掛かる）と昇順（1番手間が掛からない）の間の数であるとも言える。

図３−２ 挿入ソートの実行時間と実行時間の理論値

・実行時間の理論値はデータファイル毎に実行時間÷各要素数の�u の値を加算し、４で割り、その値を各要素数の�u を掛けた値とした。

実験に使用したワークステーションの処理速度が速いことと、プログラムで計測できる時間の最小が0.0166… であったため、要素数500の実行時間は不正確である。要素数５００以外の3つは、実行時間÷�u の値が近い値になっても、要素数500だけ、他とずれてしまうことがあり、その実行時間の理論値はずれてしまう。

• 昇順以外の実行時間は，�u に比例して，要素数が10倍になれば，実行時間は100倍近い値になっている。

• 挿入ソートは，繰り返すための２つのカウンタ（プログラムの例ではｊとｉ）と交換の待避ためのデータ（プログラムの例では ｔ）の3つしかメモリを使わず，配列の大きさに合わせた配列を宣言する必要が無いのでメモリ効率は良い。
• アルゴリズムの理解がしやすく，プログラミングが容易である。

クイックソートのプログラムの一部（交換・比較回数のカウントを表す。compare++;が比較回数のカウントで，exchange++;が交換回数のカウント）

i=l-1; j=r; /* ポインタiとjを初期化する */

pivot=a[r]; /* 一番右端の要素を枢軸にする */

for(;;){ /* ポインタiとjがぶつかるまで繰り返す */

while(a[++i] < pivot){ compare++; /* ポインタiを右へ進める */

while(i < --j && pivot <a[j]){ compare++; /* ポインタjを左へ進める */

if(i >= j) break; /* ポインタiとjがぶつかったらループを抜ける */

t=a[i]; a[i]=a[r]; a[r]=t; exchange++; /* iの指す要素とjの指す要素を交換する */

t=a[i]; a[i]=a[r]; a[r]=t; exchange++; /* a[i]と枢軸を交換する */

上のプログラムのように、whileでは真でも偽でも比較としてカウントし、交換回数はポインタ同士を交換しても、ｉと枢軸を交換してもカウントした。

図４−１ クイックソート比較回数／交換回数

・ランダムのファイルでは要素数が500から5000になれば、交換・比較回数は13倍近くになり、m logmに比例していることが解る（5000 log5000 ÷ 500 log500＝13.3…）。

・昇順の１ ２ ３ ４ の数列をクイックソートする場合、最大値が枢軸になると、枢軸より大きな値が無く、最大値である４だけの整列が終了し、１ ２ ３ の数列をソートしなければならず、1回のソートで整列が完了するのは１つだけなので手間が掛かる。

図４−２ クイックソートの実行時間と実行時間の理論値（ランダムの２つは理論値が出せなかった）

• 昇順・降順では、要素数が10倍になれば、実行時間も、比較・交換回数も100倍近くになり、

�u に比例していて、最悪の状態になっていることがわかる。

• 昇順の比較回数の理論値は

（�u ＋ ３ｍ −４）／２

a[6]＝｛１ ２ ３ ４ ５ ６｝ の数列をクイックソートすると考える

関数partition内で１回目のスキャンでは、左から右に進めるポインタｉは６回（A[0]、A[1]、A[2]、A[3]、a[4]、a[5]）、右から左に進めるポインタｊは１回（A[5]）、枢軸と比較する。そして、ｉが指すA[5]と枢軸A[5]（自分同士）を交換し、要素が1つになったA[5]は整列終了。この手順を繰り返す。

１ ２ ３ ４ ５ �E （�Eは枢軸）ポインタｉの比較回数は６回、ポインタｊの比較回数は1回

１ ２ ３ ４ �D ｉは５回、ｊは1回

１ ２ ３ �C ｉは４回、ｊは1回

１ ２ �B ｉは３回、ｊは1回

１ �A ｉは２回、ｊは1回

数列Aでは、比較回数が７＋６＋５＋４＋３のように等差数列の和になっている。

よって、昇順で要素数mのクイックソートの比較回数は初項m＋１、末項が３で項数がm−１の等差数列の和となり、

（m＋１＋３）／２×（m−１）

になるので （�u ＋ ３ｍ −４）／２ が求まる。

• 降順の比較回数の理論値は

m／２＋m−２

ｂ[6]＝｛６ ５ ４ ３ ２ １｝の数列をクイックソートすると考える。

６ ５ ４ ３ ２ �@ ｉは1回、ｊは5回（１と６が交換され、１は整列終了）

５ ４ ３ ２ �E ｉは５回、ｊは１回

５ ４ ３ �A ｉは１回、ｊは３回

２ ４ �B ｉは２回、ｊは１回

２ �B ｉは２回、ｊは１回

1回目、3回目、4回目では昇順の比較回数−１になっている。スキャンのうち約半分は、昇順−１回比較している。よって昇順の理論値から、項数／２を引くと

（m＋１＋３）／２×（m−１）−m／２

∴ m／２＋m−２

昇順と降順の比較／交換回数を比べてみると、どの要素数でも交換回数は同じで、比較回数は昇順の方が多かった。昇順は並び換えしなくてもいいのに比較回数が降順より多くなるのはおかしいように思える。これは、昇順の場合必ず、ポインタｉが右端の枢軸まで比較するが、降順の場合は2回に1回最大値が左端にあり、その時は、ポインタｉもポインタｊも枢軸を比較しない（ポインタｊはプログラム上枢軸と比較することはない）ので、同じ要素数でも降順の方が、比較回数が少ないか同じになって比較回数は昇順の方が多くなる。

しかし、交換回数は同じで比較回数は昇順の方が少ないのに実行時間では、昇順方が早くなっている。これは関数partitionの中のポインタｉとポインタｊの比較回数の違いである。

ポインタｉを比較しているwhile(a[++i] < pivot)とポインタｊを比較しているwhile(i < --j && pivot <a[j])では、ｊを比較している文の方が、ループの条件が複雑である。ループの条件が複雑な方が少し時間が掛かる。ｉの比較回数とｊの比較回数に差がたくさんあれば、実行時間に差が出て来るはずである。上に示した、昇順と降順の比較回数の理論値を説明する例において、ｉとｊは図４−３のように比較回数が増える。

図４−３ 要素数６の昇順と降順におけるポインタｉとポインタｊの比較回数

図４−３で解ることは、降順では、ｊが1回多いだけで、ｉとｊの比較回数はあまり変わらないが、昇順では、条件が複雑でないｉの方がかなり多くなる。

理論値を計算すると、昇順のｉは（m＋２）／２×（m−１）＝（�u＋ｍ−２）／２になり、

昇順のｊはm−１になる。降順はｉもｊも比較回数の半分になる。

ところで、要素数10000で理論値を考えると昇順のｉの比較回数は50004999回、昇順のｊは9999回、降順のｉとｊは25004999回となる。これは、計測した値（ｉとｊを別々にカウントするプログラム）と一致し理論値が正しいことが解った。

仮に条件が複雑になると、２倍実行速度が遅くなるとすると、要素数６の例では、昇順は２０＋５×２＝30、降順は１１＋11×２＝33で降順の方が３多くなる。また、倍率では、1.1倍の違いがある。比較回数だけでは降順の方が３回多いのに、条件文の実行速度の違いを考えると、昇順の方が、実行速度が早くなったのが説明できる。

要素数10000では、昇順は50004999＋9999×２＝50024997、降順25004999＋25004999×２＝75014997で1.5倍近い違いが出ることになるので、要素数が多ければ多い程違いが出やすい。

適当に選んで２倍で計算してみたが、参考文献によると、「ループ条件が複雑になっても、実行時間にさほど違いは出ない」とあるので、実験値で実行時間を計算してみる（交換回数は比較回数に比べて小さいので無視した）。要素数10000では、昇順／降順は1.05倍近く降順が遅くなっている。昇順のｉ＋ｊ×倍率／降順のｉ＋ｊ×倍率＝1.05で倍率を計算すると、1.12になった。

この条件文の複雑さの倍率を、要素数６で考えると、昇順は25.6降順は23.32になる。

要素数10000で考えると、昇順は、50016198降順は、53010598になる。要素数が小さいと、

• 昇順と降順の交換回数が等しくなっている。昇順では、枢軸と、枢軸の元になっている要素（つまり自分同士）を交換しているため、交換回数はm−１になる。降順では最小値がまず枢軸になった後、最大値と交換し、その最大値が枢軸になり、未整列部分の最小値と交換し、それが枢軸になる、というのを繰り返し、ポインタｉとポインタｊで繰り返すことが無く１スキャン毎に要素数が１つずつ減っている。だから、降順の交換回数はｍ−１になる。よって、昇順と降順の交換回数は同じになる。

・ランダムとランダム（重複なし）は実行時間が小さくて理論値が出せないので、m logmに比例しているかどうかわからなかった。要素数を増やすか、プログラムを工夫すべきだった。

昇順と降順の実行時間の理論値はデータファイル毎に実行時間÷各要素数の�u の値を加算し、４で割り、その値を各要素数の�u を掛けた値とした。

実験に使用したワークステーションの処理速度が速いことと、プログラムで計測できる時間の最小が0.0166… であったため、要素数500の実行時間は不正確である。要素数５００以外の3つは、実行時間÷�u の値が近い値になっても、要素数500だけ、他とずれてしまうことがあり、その実行時間の理論値は、ずれてしまう。

• 比較回数の理論値は分割を行う関数partition中のポインタｉの比較回数 ＋ ポインタｊの比較回数はm＋１もしくはm＋２掛ける、関数partitionを呼び出す回数logm（一番順調な場合）になる。そして、クイックソートのオーダーはm logmとなるので、参考文献と理論値では一致する。

実験では、比較回数はm logmよりもかなり多い数になっている。これは、枢軸がちょうど中央値になっていないため、分割の作業の効率が悪いためである。

・クイックソートの作業用メモリは参考文献によると「平均でオーダー log m 」必要とあるので他の単純なソートアルゴリズム（使用メモリはオーダー １）よりも使用するメモリが多い

マージソートのプログラムの一部（交換・比較回数のカウントを表す。compare++;が比較回数のカウントで，exchange++;が交換回数のカウント）

/* 作業用配列bの両端から取り出したデータをマージして配列aに入れる */

・比較回数はif文の実行回数なので要素数m掛ける、マージの実行回数（関数を呼び出す回数）logmになる。よってマージソートのオーダーはm logmになる。

・代入は、マージの時の比較を実行する度に行い、また、マージと同じ回数分だけ、分割時に代入を行っているため、比較回数の2倍の回数が代入回数である。

図５ マージソートの実行時間／比較回数（比較回数の理論値）

・図５の理論値はm logmの小数点以下を四捨五入した。比較回数に少数点以下の数値はありえないので（要素数が３なら ３log３＝4.75… だが、比較回数は５になり、理論値より少し大きくなる）実験値では、理論値よりも多い値になっている。

• 他のソートでは、交換する度に、3回代入をやっているがマージソートでは2回の代入なので、その分実行速度の点では効率が良い。ただし、マージソートでは、整列する配列と同じ大きさで待避するための作業用配列を宣言しなければならない。常に同じ大きさのファイルを整列するわけではないので、十分大きなメモリを宣言しておかなければならないので、メモリ効率はかなり悪い。

• マージソートのオーダーは比較回数の m logmになり、参考文献と一致した。
• マージソートを改良するには再帰呼び出しをやめることが考えられる。（関数を呼び出すと呼び出す度に、データの待避をしてしまうので時間がかかってしまう。）

また、作業用配列を大き目に宣言しておくのではなく、整列する配列と同じ大きさの領域を確保する（malloc関数を使う）ことによって無駄なメモリ消費を抑えることができると思われる。

まず、３つの基本的なソートアルゴリズムを比較してみる。

図 ６ 要素数1万における基本ソートアルグリズムの比較回数／交換回数／実行時間

• ３つ共昇順では、交換回数は０で、無駄な交換は行われていない。（クイックソートとマージソートでは、必ず交換（代入）が発生する。挿入ソートではlowkeyへの代入は発生する。）
• 挿入ソートは、昇順では一番速いが、降順では一番遅く、実行速度が、データの並びによってかなり左右されることがわかる。
• バブルソートと選択ソートの比較回数は同じで、交換回数はバブルソートの方が多い。また、バブルソートと挿入ソートの交換回数が同じで、比較回数はバブルソートの方が多い。これよりバブルソートは、選択ソートや挿入ソートよりも実行時間が掛かってしまうことが解る（降順の挿入ソートを除く）。
• ランダムのデータでは、比較回数＋交換回数が一番少ない挿入ソートが実行時間は一番速い。

図 ７ ランダムデータの各アルゴリズムにおける整列時間（秒）

（改善するには、要素数をもっと増やすか、プログラム上で10回ソートを行い、実行に掛かった時間を１０で割る、のようなことで他のアルゴリズムと比べやすいデータが取れたと考えられる）

５ 結論

今までの研究から図８のようなことがわかった。

図８ 各アルゴリズムの長所・短所

近藤 嘉雪 著 『Ｃプログラマのためのアルゴリズムとデータ構造』