第10回 並べ替え (7/1)


第8回演習の解答例


小テストの解答例


今週は,配列を使ってデータの並べ替え(ソート,ソーティング)に挑戦しよう.

配列に格納された数を,大きい順(または小さい順)に並べかえて表示するプログラムについて,順に考えてみよう.


並べ替え(ソート,ソーティング)の考え方(アルゴリズム)は,いろいろ提案されている.

ここでは,最も基本的な考え方で,配列 int a[4] = { 5, 3, 6, 2 }; のソーティング例を以下に示す.

基準にする要素を黄色,比較する要素を水色で表示しています.

a[0]a[1]a[2]a[3]処理
5362最初の状態
5362最初の数と,2番目の数を比較し,大きい方を左へ(ここでは入替なし)
5362最初の数と,3番目の数を比較し,大きい方を左へ(ここでは入替あり)
6352最初の数と,4番目の数を比較し,大きい方を左へ
6352この時点で,一番大きい数が,左端(配列の先頭)へ来る.
2巡目
63522番目の数と,3番目の数を比較し,大きい方を左へ
65322番目の数と,4番目の数を比較し,大きい方を左へ
6532この時点で,2番目に大きい数が左から2番目に来る.
3巡目
65323番目の数と,4番目の数を比較し,大きい方を左へ
6532おしまい.この時点で大きい順に並べ替えが完了している.

ソーティングのプログラムを組む上でのポイントは,

です.



プログラムの作成

演習課題1

まずは,準備として 4 個の要素を持つ配列 a[4]={5,3,6,2} を宣言し,中身を画面に表示するプログラムを作成せよ.



演習課題2

以下の配列の中身を入れ替える部分を作成し,結果を画面に表示せよ.


a[0] = 5;
a[2] = 6;

のとき,二つの要素を入れ替えて,


a[0] = 6;
a[2] = 5;

として,中身を画面に表示するプログラムを作成せよ.

ヒント:単純に一方の変数を他方に代入すると,代入されたほうの値が上書きされてしまうので,一時保存用の別の変数(通常はtmpと宣言する)をつくり,コピー(代入)しておく.


演習課題3

上記入れ替えるプログラムを応用し,配列を大きい順に並べ替え,画面に表示するプログラムを完成させよ.

ヒント:上の値の入れ替えを参考に,while文またはfor文のループの範囲を考えよう.繰り返し文を二重に用います.


int i,j;  /* カウンタ変数 */
  
for ( i = ? ; i ?? ; i++ ) {		/*i:基準にする要素の番号*/
 
    for ( j = ? ; j ?? ; j++ ) {	/*j:比較する要素の番号*/
 
        if ( ... )  {  /* 数値の比較 */
 
            「値の入れ替え(演習課題2)」...
 
        }
    }
}

その他のソート

上記の方法は,もっとも単純な考え方であり,他にも20種類程のソートがある.
ここでは,他の基本的なアルゴリズムである「バブルソート」と「挿入ソート」について簡単に紹介する.

・バブルソート

バブルソートは「隣り合う要素を比較して,右のほうが小さければ両者を入れ替える」という作業を左から順に行い,
大きな数を右側に寄せていくという考え方である.

例:数字を小さい順に並べる



・挿入ソート

挿入ソートは次の例のようにカードを取っていき,正しい位置に挿入しながら,小さい順に並び替えていくという考え方である.

この方法では,どこにカードを挿入するべきか判断する必要がある.
5を挿入する場合を例にして,もう少し詳しく見てみよう.



以上のソートは一例なので他の種類のソートも興味がある人は調べてみよう.


演習課題4

10 個の数字の並び { 5, 3, 8, 6, 4, 9, 2, 7, 5, 1 } をバブルソートの方法で小さい順に並べ替えよ.

(並べ替え前・並べ替え後の配列データをそれぞれ画面に表示し,うまく出来たかどうか比較しよう.)



演習課題5

課題4の数字の並びを挿入ソートの方法で小さい順に並べ替えよ.


授業終了時までのプログラムと完成した提出用プログラムをoh-meijiシステムを使って提出すること
授業終了時に送るのは出席の確認用である.完成した課題は提出用の回に送ること
(提出期限を厳守し,提出用の回に提出しないと採点を行わない)