配列に格納された数を,大きい順(または小さい順)に並べかえて表示するプログラムについて,順に考えてみよう.
並べ替え(ソート,ソーティング)の考え方(アルゴリズム)は,いろいろ提案されている.
ここでは,最も基本的な考え方で,配列 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 | おしまい.この時点で大きい順に並べ替えが完了している. |
ソーティングのプログラムを組む上でのポイントは,
です.
まずは,準備として 4 個の要素を持つ配列 a[4]={5,3,6,2} を宣言し,中身を画面に表示するプログラムを作成せよ.
以下の配列の中身を入れ替える部分を作成し,結果を画面に表示せよ.
a[0] = 5;
a[2] = 6;
のとき,二つの要素を入れ替えて,
a[0] = 6;
a[2] = 5;
として,中身を画面に表示するプログラムを作成せよ.
ヒント:単純に一方の変数を他方に代入すると,代入されたほうの値が上書きされてしまうので,一時保存用の別の変数(通常はtmpと宣言する)をつくり,コピー(代入)しておく.
上記入れ替えるプログラムを応用し,配列を大きい順に並べ替え,画面に表示するプログラムを完成させよ.
ヒント:上の値の入れ替えを参考に,while文またはfor文のループの範囲を考えよう.繰り返し文を二重に用います.
int i,j; /* カウンタ変数 */
for ( i = ? ; i ?? ; i++ ) { /*i:基準にする要素の番号*/
for ( j = ? ; j ?? ; j++ ) { /*j:比較する要素の番号*/
if ( ... ) { /* 数値の比較 */
「値の入れ替え(演習課題2)」...
}
}
}
上記の方法は,もっとも単純な考え方であり,他にも20種類程のソートがある.
ここでは,他の基本的なアルゴリズムである「バブルソート」と「挿入ソート」について簡単に紹介する.
バブルソートは「隣り合う要素を比較して,右のほうが小さければ両者を入れ替える」という作業を左から順に行い,
大きな数を右側に寄せていくという考え方である.
例:数字を小さい順に並べる
挿入ソートは次の例のようにカードを取っていき,正しい位置に挿入しながら,小さい順に並び替えていくという考え方である.
この方法では,どこにカードを挿入するべきか判断する必要がある.
5を挿入する場合を例にして,もう少し詳しく見てみよう.
以上のソートは一例なので他の種類のソートも興味がある人は調べてみよう.
10 個の数字の並び { 5, 3, 8, 6, 4, 9, 2, 7, 5, 1 } をバブルソートの方法で小さい順に並べ替えよ.
(並べ替え前・並べ替え後の配列データをそれぞれ画面に表示し,うまく出来たかどうか比較しよう.)
課題4の数字の並びを挿入ソートの方法で小さい順に並べ替えよ.
授業終了時までのプログラムと完成した提出用プログラムをoh-meijiシステムを使って提出すること
授業終了時に送るのは出席の確認用である.完成した課題は提出用の回に送ること
(提出期限を厳守し,提出用の回に提出しないと採点を行わない)