基本的なソート方法

配列ａのサイズｎが５で、その要素が、
　　　a[1]　a[2]　a[3]　a[4]　a[5]
　　　３０　２０　５０　１０　４０
であるとき、これを昇順（小さい順）に並べ変えること、すなわち
　　　a[1]　a[2]　a[3]　a[4]　a[5]
　　　１０　２０　３０　４０　５０
にすることを例にします。

選択ソート

選択ソートのアルゴリズムを検討することをとおして、プログラムの作成では、複雑な問題を単純な操作に分解し、それを組み立てることが有効であることを説明します。
　選択ソートでは、まず全体のうち最小値をもつ要素を探して先頭にもっていき（最小値をもつ要素と先頭の要素を入れ替えて）、次に２番目以降の最小値要素と２番目の要素を差し替えるという操作を繰り返せば、全体がソートされるという考え方です。わかりやすい考え方です。

スワップ

ソートをするには、２つの要素、例えばａ[１] と ａ[４] を入れ替える操作（スワップという）が必要であることがわかります。
　ここで、単純に、
　　　ａ[１] ＝ ａ[４]　・・・ア
　　　ａ[４] ＝ ａ[１]　・・・イ
としてはいけません。
　　　現在、ａ[１] は３０、ａ[４] は１０になっています。
　　　アを行うと、ａ[１] が１０になります。
　　　イを行うと、ａ[４] は１０になります。
　　　すなわち、両方が１０になってしまいます。
　それを避けるために、いったんａ[１] の値（３０）を他の変数ｗに退避させておき、
　　　ｗ ＝ ａ[１]
　　　ａ[１] ＝ ａ[４]
　　　ａ[４] ＝ ｗ
とする必要があります。
　これを一般化すれば、ａ[ｉ] と ａ[ｊ] をスワップするアルゴリズムは、
　　　ｗ ＝ ａ[ｉ]
　　　ａ[ｉ] ＝ ａ[ｊ]
　　　ａ[ｊ] ＝ ｗ
となります。

最小値

昇順にソートするのですから、配列のなかから最小値を探すプロセスが必要となりそうです。
　単に最小値を得るだけでしたら、そのアルゴリズムは、次のようになります。
　　　とりあえず、最小値＝ａ[１] とします。
　　　添字（要素番号）ｊを２からｎ（配列の大きさ）まで繰り返す。
　　　　　もし、最小値 ＞ ａ[ｊ] となる要素があったら、
　　　　　　　　最小値 ＝ ａ[ｊ] とする。
　　　繰り返し完了。
プログラムは次のようになります。
　　ア　　amin = a[1];
　　イ　　for (j=2; j<=n; j++) {
　　ウ　　　　if (a[j] < amin) {
　　エ　　　　　　amin = a[j];
　　オ　　　　}
　　カ　　}
（ウの < を > にすれば最大値になります。）

しかし、ソートをすることが目的ならば、ａ[１] と最小値である要素をスワップする必要があるため、最小値である要素の添字（要素番号）ｋ を知る必要があります。
　それで、プログラムを次のように変更します。
　　ア　　k = 1;
　　イ　　amin = a[1];
　　ウ　　for (j=2; j<=n; j++) {
　　エ　　　　if (a[j] < amin) {
　　オ　　　　　　amin = a[j];
　　カ　　　　　　k = j;
　　キ　　　　}
　　ク　　}
　　ケ　　if (k != 1) {
　　コ　　　　w = a[k];　　　/*　　　　　　*/
　　サ　　　　a[k] = a[1];　 /*　スワップ　*/
　　シ　　　　a[1] = w;　　　/*　　　　　　*/
　　ス　　}
（コ～シにおいて、a[k] の値は amin なので、あえて ｗ にせずに、
　　　　　　　a[k] = a[1];
　　　　　　　a[1] = amin;
　とすることができます。）

実際の数値で確かめましょう（このように、ヒューマンコンピュータの作業のことをトレースといいます）。
　ア：k = 1、イ：amin = a[1] = 30
　ウ：j = 2
　エ：a[j]=a[2]=(=20) < amin(=30) なのでオへ
　オ：amin = 20、カ：k = j = 2
　キ・クからウに戻り、j = 3
　エ：a[j]=a[3]=(=50) > amin(=20) なのでオ・カは行われない
　キ・クからウに戻り、j = 4
　エ：a[j]=a[4]=(=10) < amin(=20) なのでオへ
　オ：amin = 10、カ：k = j = 4
　キ・クからウに戻り、j = 5
　エ：a[j]=a[5]=(=40) > amin(=10) なのでオ・カは行われない
　キ・クからウに戻ろうとするが、ウの j<=n の条件により
　　　繰り返しが完了するのでケへ
　ケ：ここまでで、a[k]=a[4]=amin=10 が最小値であることが判明
　　　k≠1 なので、コ～シで、a[1]⇔a[4] を行う。
　この結果、
　　　a[1]　a[2]　a[3]　a[4]　a[5]
　　　１０　２０　５０　３０　４０
になります。

トレースをするのに、このような散文調ではわかりにくいので、次のような表にするのが適切です（プログラムに慣れると、表を作成する必要すらなくなるのですが）。
　　　　　　　ａ[ｊ]　　ｋ　ａ[ｋ] 　エの比較　amin　新ｋ
　　初期値　　　　　　　１　　３０
　　ｊ＝２　　　２０　　１　　３０　　　＜　　　２０　　２
　　　　３　　　５０　　２　　２０　　　＞
　　　　４　　　１０　　２　　２０　　　＜　　　１０　　４
　　　　５　　　４０　　４　　１０　　　＞
これから、ｋ＝４、最小値＝ａ[４]＝１０であることがわかります。

選択ソート

最小値を求める処理により、a[1] に最小値が入りました。同様にして、a[2]～a[n]の最小値を a[2]、a[3]～a[n]の最小値を a[3] へと入れていけば、a[n-1] を行った段階で、ソートが完了したことになります。
　それに対応させるために、上のプログラムを「a[i]～a[n] で最小の要素 a[k] を探す」ように書き変えると、次のようになります。
　ア　for (i=1; i<=n-1; i++) {
　イ　　k = i;
　ウ　　amin = a[i];
　エ　　for (j=i+1; j<=n; j++) {
　オ　　　if (a[j] < amin) {
　カ　　　　　amin = a[j];
　キ　　　　　k = j;
　ク　　　}
　コ　　}
　サ　　if (k != i) {
　シ　　　w = a[i];
　ス　　　　a[i] = a[k];
　セ　　　a[k] = w;
　ソ　　}
　タ　}

トレースした結果を示します。
　　　　　　　　　　　　　　　　　 a[1]　a[2]　a[3]　a[4]　a[5]
　　　初期値　　　　　　　　　　　　30　　20　　50　　10　　40
　　　最小値=a[4]=10：a[1]⇔a[4]　　10　　20　　50　　30　　40
　　　最小値=a[2]=20：変化なし　　　10　　20　　50　　30　　40
　　　最小値=a[4]=30：a[3]⇔a[4]　　10　　20　　30　　50　　40
　　　最小値=a[5]=40：a[4]⇔a[5]　　10　　20　　30　　40　　50
　　　ソート結果　　　　　　　　　　10　　20　　30　　40　　50

関数の考え方

関数（function）とは、プログラムを構成する部品のようなものです。
　スワップ処理を一般化して
　　　function swap(x, y) {
　　　　　w = x;
　　　　　x = y;
　　　　　y = w;
　　　}
という関数を作成しておきます。
　そうすれば、a[3]⇔a[4] を行いたいときは、
　　　swap(a[3], a[4])
と記述すればよいのです。

配列ａ[i]～ａ[ｎ]のなかで最小値の添字 ｋ を求める関数 findamin は次のようになります。
（配列ａとｎは外部変数で定義されているものとします。）
　　　function findamin(i,k) {
　　　　　k = i;
　　　　　amin = a[i];
　　　　　for (j=i+1; j<=n; j++) {
　　　　　　　if (a[j] < amin) {
　　　　　　　　　amin = a[j];
　　　　　　　　　k = j;
　　　　　　　}
　　　　　}
　　　}

そして、ソートのプログラムは、次のようになります。
　　　function sort();
　　　　　for (i=1; i<=n-1; i++) {
　　　　　　　findamin(i,k)；
　　　　　　　if (i != k) swap(a[i], a[k]);
　　　　　}
　　　}

このように、関数の考え方を導入すると、
　　　アルゴリズムが明確になり、ミスのないプログラムが作れる
　　　他人が読んでもわかりやすいので、保守・改訂が容易になる
　　　関数を部品として他のプログラムで再利用することができる
などのメリットがあります。

バブルソート

ソートのプログラムで最も単純なのはバブルソートです。バブルソートは、次の考え方によりソートします。このように、同じ問題でも多様なアルゴリズムが存在するのです。
　ａ[１] と ａ[２] を比較し、ａ[１] のほうが小さければそのまま、ａ[２] のほうが小さければ、ａ[１] と ａ[２] をスワップすれば、大きいほうが ａ[２] になります。次に、ａ[２] と ａ[３] を比較し、ａ[２] のほうが小さければそのまま、ａ[３] のほうが小さければ、ａ[２] と ａ[３] をスワップすることにより、ａ[１] ～ ａ[３] のうち最も大きい要素が ａ[３] になります。これを繰り返すことにより、最大値をもつ要素が配列の末尾 ａ[ｎ] になります。
　次に、末尾を除いた ａ[１] ～ ａ[ｎ－１] について、同じ操作を行えば、２番目に大きな要素が ａ[ｎ－１] に入ります。これを繰り返すことによりソートが完成します。
選択ソートと比較して、要素の添字 ｋ を知る必要がないので、プログラムが簡素になっています。

　ア　for (i=1; i<=n-1; i++) { 　　　　　　　　　　────┐
　イ　　　for (j=1; j<=n-i; j++) { 　　────┐　　　　　│
　ウ　　　　　if (a[j] > a[j+1]) {　　　　　　 │　　　　　│
　エ　　　　　　　w = a[j];　　　　┐　　　　　│　　　　　│
　オ　　　　　　　a[j] = a[j+1];　 ├スワップ　├最大値　　├ソート
　カ　　　　　　　a[j+1] = w;　　　┘　　　　　│を末尾に　│
　キ　　　　　}　　　　　　　　　　　　　　　　│　　　　　│
　ク　　　}　　　　　　　　　　　　　　────┘　　　　　│
　ケ　}　　　　　　　　　　　　　　　　　　　　　　────┘

トレースすると次のようになります。水の中の泡（バブル）のように、軽い（値の小さい）要素が上（左）へ、重い（大きい）要素が下（右）に移動していることがわかります。

　　　ｉ　ｊ　a[j] a[j+1]　比較　　 a[1]　a[2]　a[3]　a[4]　a[5]
　　　　　　　　　　　　　　　　　　３０　２０　５０　１０　４０
　　　１　１　３０　２０　　＞　　　２０　３０　　↓　　↓　　↓
　　　　　２　３０　５０　　＜　　　　↓　　↓　　↓　　↓　　↓
　　　　　３　５０　１０　　＞　　　　↓　　↓　１０　５０　　↓
　　　　　４　５０　４０　　＞　　　　↓　　↓　　↓　４０　５０
　　　２　１　２０　３０　　＜　　　　↓　　↓　　↓　　↓
　　　　　２　３０　１０　　＞　　　　↓　１０　３０　　↓
　　　　　３　３０　４０　　＜　　　　↓　　↓　　↓　　↓
　　　３　１　２０　１０　　＞　　　１０　２０　３０
　　　　　２　２０　３０　　＜　　　　↓　　↓　　↓
　　　４　１　１０　２０　　＜　　　　↓　　↓
　　　結果　　　　　　　　　　　　　１０　２０　３０　４０　５０

挿入ソート

ａ[２] を ａ[１] と比較して、ａ[１] ＜ ａ[２] ならば、ａ[２] をａ[１] の後におき（そのまま）、ａ[１] ＞ ａ[２] ならば、ａ[２] をａ[１] の前に挿入します。ａ[３] については、ａ[１] ～ａ[２] と比較して、適切な位置に挿入します。
　このようなことを ｉ－１回繰り返せば、ａ[１] ～ ａ[ｉ－１] までは昇順にソートされています。
　未ソートの最初の要素 ａ[ｉ] と ａ[１] ～ ａ[ｉ－１] を比較して、 　　　ａ[ｊ－１] ＜ ａ[ｉ] ＜ ａ[ｊ] となる個所に ａ[ｉ] を挿入します。
　このとき、挿入させるために ａ[ｊ] ～ ａ[ｉ－１] の部分を一つずらす必要があります。
　プログラムは、次のようになります。

　ア　for (i=2; i<=n; i++) {
　イ　　　x = a[i];
　ウ　　　if (x < a[i-1]) { 　　　────既ソート部分末尾より大ならば何もしない
　エ　　　　　　j = 1;　　　　　　────┐
　オ　　　　　　while ( (j <= i-1)　　　　│
　カ　　　　　　　　&& (x >= a[j]) ) {　　├ａ[ｉ] ＜ ａ[ｊ] となるｊを探す
　キ　　　　　　　　j = j+1;　　　　　　　│
　ク　　　　　　} 　　　　　　　　────┘
　コ　　　　　　for (k=i-1; k>=j; k--) {　┐
　サ　　　　　　　　a[k+1] = a[k];　　　　├挿入をするために１つ下げる
　シ　　　　　　} 　　　　　　　　　　　　┘
　ス　　　　　　a[j] = x;　　　　────挿入する
　セ　　　}
　ソ　}

ウは、ａ[ｉ－１] までがソートされており、その最大値を持つ要素が ａ[ｉ－１] なので、 ａ[ｉ－１] ≦ ａ[ｉ] であれば、ａ[ｉ] を含めてソートされていることになるため、何もする必要がないという意味です。
　エ～クでは、ａ[ｉ] を挿入する個所を調べ、その添字ｊを求めるプロセスです。もし、ａ[ｉ] がそれまでの最小値 ａ[１] よりも小さいときは、ｊ＝１になります。
　コ～シで、添字の大きいほうからずらしているのは、小さいほうから行うと、例えば、ａ[２] → ａ[３] の後で ａ[３] → ａ[４] を行うと、ａ[４] も ａ[２] と同じ値になってしまうからです。
　挿入ソートでは、「挿入をするために１つ下げる」ために、要素の移動回数が多くなるのが特徴です。
　配列ａの順序は次のように変化します。

　　　ｉ　　a[1]　a[2]　a[3]　a[4]　a[5]
　　　　　　３０　２０　５０　１０　４０
　　　２　　２０　３０
　　　３　　２０　３０　５０
　　　４　　１０　２０　３０　５０
　　　５　　１０　２０　３０　４０　５０

基本ソートの比較

計算オーダーはすべて Ｏ(ｎ²)

アルゴリズムを計算効率で評価するとき、最も特徴的な処理が何回行われるかを基準にします。ソートでは比較回数を用いるのが通常です。
　選択ソートもバブルソートも、２重の forループがあり、配列の２つの要素を比較しています。その組合せは、ｎ(ｎ－１)／２になります。挿入ソートもwhileの内容を調べると同じことになります。すなわち、これら３つのソートを行うとき、その平均比較回数は、ｎ(ｎ－１)／２回です。
　計算効率が問題になるのは、ｎが非常に大きいときですから、ｎ－１をｎとしても大した違いはありませんし、１／２のような係数も、ｎとｎ²の違いなどに比べれば大したことではありません。
　それで、式の最高次の項をもって、そのアルゴリズムの計算量（計算オーダー）といい、Ｏ( ｆ(ｎ) ) で表します。ここでの３つのソートの計算オーダーは、Ｏ(ｎ²) です。

スワップ回数はバブルソートが多い

トレースからわかるように、あるｉについて、ｊが変化するとき何回もスワップする場合があります。元の配列が逆順の場合には、ｊが変化するたびにスワップすることになります。それに対して、選択ソートでは、あるｉについてその範囲での最小値の要素だけがスワップの対象になるだけです。挿入ソートも、対象となる要素だけがスワップの対象になるので、選択ソートと同じです。

データ移動回数は挿入ソートが多い

これについては前述しました。

バブルソートと挿入ソートは安全ソート。選択ソートは安定ソートではない

同じ値をもつ複数の要素があるとき、ソートをしたときに元の順序が保たれるソートのことを安定ソートといいます。バブルソートと挿入ソートでは、元の配列の先頭から順に、前（添字が小さい）の要素と後（添字が小さい）の値が同じときは、その順序を変えないので安定ソートです。
　それに対して、選択ソートでは、最大値あるいは最小値を探すときに、見つかった値を入れ替えるときに、先頭近くにあった要素がスワップ対象になるので、安定性が失われます。例えば、「①２０　②３０　③２０　④１０」のとき、最小値が④なので、①と④がスワップされ「④１０　②３０　③２０　①２０」となり、①と③の順番が崩れてしまいまいます。

計算プログラム

上記３つの方法でソートします。経過の状況も出力されます。