ソートの基礎

配列ａのサイズｎが５で、その要素が、
　　　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]);
　　　　　}
　　　}

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

発展

ソートの方法には、多様な方法があります（→参照：「ソートの種類」）。選択ソートに類似した有名な方法にバブルソートや挿入ソート（→参照：「基本的なソート方法」）、高速なソート方法では、クイックソートやシェルソートなど（→参照：「高速ソート」）があります。