今回は，前回の配列にしまわれた数字から最大値を見つけ出すプログラムを応用して，配列の中身を大きい順（または小さい順）に並べ替えよう。並べ替え（ソート）も，プログラミング学習に欠かせないアルゴリズムで，いろいろなアルゴリズムが考えられます。
先週の最後の課題は，要素数 10 個の整数型配列 {-4, 6, 7, 2, -7, 5, 3, 9, 0, 7}がある．
配列の最大値を表示するプログラムを作成せよ．（アルゴリズムをまず考えよう）
でした。アルゴリズムを，言葉で書き出すと，
(1) 最大値に，配列の最初の数を仮の最大値として代入する。
(2) 最大値と，２番目の数を比較し，最大値より大きな値だったら，その値を最大値に代入する。
(3) 10番目まで，繰り返す。
(4) 最大値に代入されている値が最大値。
というアルゴリズムが考えられます。このアルゴリズムを応用すれば，並べ替えもできそうです。
最大値を求めるプログラムを応用した，並べ替えプログラムのアルゴリズムを考えよう。（選択法）
(1) 最大値を求めたら，最大値が最初の要素になるように入れ替える。
(2) 最大値を求める範囲を2番目から最後までとして，(1) を実行する。
(3) 10番目まで，繰り返したら，並べ替え終了。
ここで，難しいのは，求めた最大値を，配列の先頭へ移動する（入れ替える）作業と，その最大値を除いて，次の最大値を求める作業です。それぞれについて，実際のプログラムではどのようにしたらよいでしょうか。
以下の配列の中身を入れ替える部分を作成し，結果を画面に表示せよ．
a[0] = 5;
a[2] = 6;
のとき，二つの要素を入れ替えて，
a[0] = 6;
a[2] = 5;
として，中身を画面に表示するプログラムを作成せよ．
ヒント：単純に一方の変数を他方に代入すると，代入されたほうの値が上書きされてしまうので，一時保存用の別の変数（通常はtmpと宣言する）をつくり，コピー（代入）しておく．
デジタル時計の表示について考えてみよう。12時59分の次は，13時00分になります。この表示をぷろぐらむで作成してみよう。
時間は，０から23まで1ずつ増えていく。このとき分は，1時間に一回0から59まで数える。繰り返しを二重にすることで，表示できる。
ここまで準備すれば，並べ替えのプログラムが作れるはずです。挑戦してみよう。
並べ替え（ソート，ソーティング）の考え方（アルゴリズム）は，いろいろ提案されている．ここでは，最大値を見つけるアルゴリズムを応用して，配列 int a[4] = { 5, 3, 6, 2 }; のソーティング例を以下に示す．
基準にする要素を黄色，比較する要素を水色で表示しています．
| a[0] | a[1] | a[2] | a[3] | 処理 |
| 5 | 3 | 6 | 2 | 最初の状態 |
| 5 | 3 | 6 | 2 | 最初の数と，2番目の数を比較し，大きい方を左へ（ここでは入替なし） |
| 5 | 3 | 6 | 2 | 最初の数と，3番目の数を比較し，大きい方を左へ（ここでは入替あり） |
| 6 | 3 | 5 | 2 | 最初の数と，4番目の数を比較し，大きい方を左へ |
| 6 | 3 | 5 | 2 | この時点で，一番大きい数が，左端（配列の先頭）へ来る． |
| 2巡目 | ||||
| 6 | 3 | 5 | 2 | 2番目の数と，3番目の数を比較し，大きい方を左へ |
| 6 | 5 | 3 | 2 | 2番目の数と，4番目の数を比較し，大きい方を左へ |
| 6 | 5 | 3 | 2 | この時点で，2番目に大きい数が左から2番目に来る． |
| 3巡目 | ||||
| 6 | 5 | 3 | 2 | 3番目の数と，4番目の数を比較し，大きい方を左へ |
| 6 | 5 | 3 | 2 | おしまい．この時点で大きい順に並べ替えが完了している． |
上記の方法は，もっとも単純な考え方であり，他にも20種類程のソートがある．
ここでは，他の基本的なアルゴリズムである「バブルソート」と「挿入ソート」について簡単に紹介する．
バブルソートは「隣り合う要素を比較して，右のほうが小さければ両者を入れ替える」という作業を左から順に行い，
大きな数を右側に寄せていくという考え方である．
例：数字を小さい順に並べる
挿入ソートは次の例のようにカードを取っていき，正しい位置に挿入しながら，小さい順に並び替えていくという考え方である．
この方法では，どこにカードを挿入するべきか判断する必要がある．
5を挿入する場合を例にして，もう少し詳しく見てみよう．
以上のソートは一例なので他の種類のソートも興味がある人は調べてみよう．
トランプのカード13枚を，小さい順に並べ替えるプログラムを，選択法で作成しよう。
（並べ替え前・並べ替え後の配列データをそれぞれ画面に表示し，うまく出来たかどうか比較しよう．）
（１）バブルソートか挿入ソートので小さい順に並べ替えるプログラムに挑戦しよう。
（２）前回の課題で，配列からある数を探す（サーチ）プログラムを作成しました。このプログラムでは，扱うデータ量が多くなると，検索に時間がかかります。時間がかかる理由は， 数字を一つ一つを検査し，かつ，配列の最後まで行っていない事を検査しているためです。何か良い工夫をして，検索時間を減らすプログラムに挑戦してみましょう。
授業終了時までのプログラムと完成した提出用プログラムをoh-meijiシステムを使って提出すること
授業終了時に送るのは出席の確認用である．完成した課題は提出用の回に送ること
（提出期限を厳守し，提出用の回に提出しないと採点を行わない）