12月10日・ポインタ

プログラミング応用課題（ポインタ＋バブルソート）資料
課題提出期限：12 月 16 日（１７時）
１．課題
３．バブルソートのアルゴリズム
ポインタによる swap 関数（データ交換関数）を使って、整数の配列のデータを並べ替えるソート(並べ
ｎ個
先の例は５つのデータの並べ替えでし
替え）関数を作成する。
たが、ｎ個のデータの場合はどのようにな
15
100 20
30
...... ...... 3
5
15
100 20
30
...... ...... 3
5
15
20
100 30
...... ...... 3
：
5
るでしょうか。
２．バブルソートとは
先の例では a[4]に最大値が入るまでに４
バブルソートは配列内の隣り合うデータを比較して（必要なら）並べ替えるという単純な作業の繰り返
回の比較・交換を行いました。また、a[3]
しで、データの並べ替えを行うソートアルゴリズム（並べ替えのアルゴリズム）です。今回は「配列内の
に２番目に大きい値が入るまでに３回の
任意の２つのデータを引数として渡すと、データを交換する」という機能を持った関数を「ポインタ」を
比較・交換を行いました。次に、a[2]に３
用いて作成します。
番目に大きい値が入るまでに２回の比
バブルソートのアルゴリズムは下記の例のようなものです。
（例は昇順（小さい方から大きい方へ）の並べ替えです。整数
と a[1]の比較・交換を１回行いました。
で交換する）
20
30
15
20
30
50
...... ...... 5
100
15
20
30
50
...... ...... 5
：
100
このことから、ｎ個のデータの場合には、
①交換
a[0] a[1] a[2] a[3] a[4]
8
15 10
3
5
最初に最大値を取り出すためにｎ−１回
の比較・交換を行い、次に２番目に大きい
①まず最初の２つのデータを比較し、最初のデータが次のデー
タよりも大きければデータを交換する。（15 は 8 より大きいの
15
：
50 ...... ...... 100 5
較・交換を行いました。そして最後に a[0]
a[0] a[1] a[2] a[3] a[4]
15
8
10
3
5
型の配列 a[0]∼a[4]に 15, 10, 1, 8, 5 のデータが入っているもの
とします。）
ｎ−１回
：
値を取り出すためにｎ−２回の比較・交換
を行い、・・・・・・、最後に１回の比較
②交換
a[0] a[1] a[2] a[3] a[4]
8
10 15
3
5
交換を行うことになります。これを図で表
15
20
30
40
ｎ−２回
...... ...... 50
100
すと右図のようになります。
ｎ−２回
②次に２番目と３番目のデータ（ a[1]と a[2]）を比較し、２番目
のデータが３番目のデータよりも大きければデータを交換する。
③以下同じ要領で最後まで、比較と交換を繰り返す。ここまで
交換
a[0] a[1] a[2] a[3] a[4]
8
10 3
15 5
：
：
：
：
１回
並べ替え終了
の操作で、一番右端のデータ（例では a[4]）が最大になること
が保証される。
④a[4]が最大であることは決まったので、a[4]を除いた a[0]∼
交換
a[0] a[1] a[2] a[3] a[4]
8
10 3
5
15
③この時点で a[4]が最大
また、このアルゴリズムをプログラムの構造として書くと下記のようになります。
（２つのどちらも同じ）
a[3]で同じことを繰り返す。こうすることで、a[3]が２番目に大
きい値になる。
⑤これまでと同じ要領で a[0]∼a[2]の中で最大の値を a[2]に移
動し、最後に a[0]と a[1]について比較・交換を実行すると、配
列は昇順に並べ替えられたことになる。
交換しない
a[0] a[1] a[2] a[3] a[4]
8
10 3
5
15
（ｎ個のデータ data[0]∼data[n-1]があるとする）
（ｎ個のデータ data[0]∼data[n-1]があるとする）
ｎ−１回の繰り返し：ｉ＝１∼ｎ−１まで {
ｎ−１回の繰り返し：end＝ｎ−１∼１まで {
ｎ−ｉ回の繰り返し：ｊ＝０∼ｎ−ｉ−１まで {
交換
a[0] a[1] a[2] a[3] a[4]
8
3
10
5
15
end 回の繰り返し：ｊ＝０∼ end-1 まで {
data[j]と data[j+1]を比較して
data[j]と data[j+1]を比較して
もし、data[j]>data[j+1]
もし、data[j]>data[j+1]
なら {
data[j]と data[j+1]を交換
data[j]と data[j+1]を交換
}
sort
/sﾅ :rt/ 慥
1
種類,タイプ;
2
〔コンピュータ〕（データの）ソート
,並べ換え.
交換
a[0] a[1] a[2] a[3] a[4]
8
3
5
10 15
④この時点で a[4]が最大、a[3]が２
番目に大きい値になる
}
}
}
なら {
}
}
４．配列の２つの要素を交換する関数をポインタを使って作る（教科書 p117）
５．関数 swap を使用して、関数 bsort を作成する。（関数 bsort には配列のデータを引き渡す）
普通の引数への引渡し
main 関数
swap(int x , int y)関数
bsort が受け取るデータは（配列へのポインタと配列内のデータ数ｎ）とする
●bsort の定義
int a[10];で宣言
void bsort(int *v, int n)
アドレス
データ
12ff00(a[0]) 15
12ff04(a[1]) 10
12ff08(a[2]) 3
swap(a[0], a[1])
{
アドレス
データ
12ff50(x)
15
内部では、v[i]として配列データにアクセスできる。
12ff54(y)
10
v[i]に行った変更は、呼び出しもとに反映される
}
で関数を呼び出し
●bsort の呼び出し
int x[100];
/* 配列 x の宣言 */
：
swap 関数の中でデータを交換しても、main 関数の中の配列のデータは変化しない。
：
bsort( x, n);
：
のようにして呼び出す。
ポインタを使った引数への引渡しと、ポインタを用いた間接参照
●配列をランダムに初期化（乱数関数
main 関数
swap(int *x , int *y)関数
例：
#include <stdlib.h>
int a[10];で宣言
rand , srand を使う。教科書 p205,p317）
/*
rand を使うためのヘッダ */
#include <stdio.h>
アドレス
データ
アドレス
データ
12ff00(a[0]) 15
12ff50(x)
12ff00
12ff04(a[1]) 10
12ff54(y)
12ff04
12ff08(a[2]) 3
swap(&a[0], &a[1])
main(){
int x[100];
int i, s;
で関数を呼び出し
scanf("%d", &s);
*x と*y を交換
srand(s);
for(i=0 ; i<100 ; i++)
x[i] = rand();
swap 関数の中で＊ｘと＊ｙのデータを交換すると、main 関数の中の配列のデータ（アドレス１２ｆｆ０
for(i=0 ; i<100 ; i++)
０と１２ｆｆ０４のデータ）が交換される。
printf("x[%d]=%d¥n", i, x[i]);
}
○関数呼び出しで &をつけると、アドレスを引き渡す。
この初期化された配列 x を bsort 関数に渡して、並べ替えを行う。結果も表示する。
○ポインタ型の変数 x は、*x と書くと間接参照（x のデータをアドレスとみなして、そのアドレスの指すデ
ータを間接的に取り扱う）する