画像(logo)

HOME/[C言語]サンプルプログラム集 目次/基本選択法

広告

[C言語 サンプルプログラム集]
基本選択法

広告

↓2016年02月29日発売↓

12歳からはじめる ゼロからのC言語 ゲームプログラミング教室

目次へ戻る

基本選択法

今回はソート(並べ替え)プログラムの基本、基本選択法についてやっていきます。

わかりやすくシンプルな並べ替えの方法ですが、ソートする対象がほとんど整列されているような状態でも必ず同じ手順を繰り返さなくてはいけないのでムダの多い方法でもあります。

普通に基本選択法

#include <stdio.h>

int main(){
	int ary[10] = {1,5,7,2,9,8,6,4,3,0};
	int i, j;
	int w;

	for (i = 0; i < 9; i++){
		for (j = 1 + i; j < 10; j++){
			if (ary[i] > ary[j]){
				w = ary[i];
				ary[i] = ary[j];
				ary[j] = w;
			}
		}
	}

	for (i = 0; i < 10; i++){
		printf("%d ", ary[i]);
	}
	printf("\n");

	return 0;
}

■実行結果■

画像(cs_6_1)

配列「ary」の全ての要素を

int ary[10] = {1,5,7,2,9,8,6,4,3,0};

普通に小さい順に並べ替えます。

基本選択法は入れ子になった2重のループの中でひたすら入れ替えを繰り返すようなプログラムになりますのでループ用の変数と入れ替え用の変数を用意します。

/*ループ用*/
int i,j;
/*入れ替え用*/
int w;

そして並べ替えていく手順ですが、まず配列の最初の要素とその後の全ての要素を比べます。

そしてその最初の要素より小さい要素があれば、その要素と最初の要素を入れ替えます。

for (j = 1; j < 10; j++){
	if (ary[0] > ary[j]){
		w = ary[0];
		ary[0] = ary[j];
		ary[j] = w;
	}
}

こんな感じですね。

その結果、最初の要素「ary[0]」にはこの配列の中で一番小さい数が入る事になります。

あとは同じ方法を一つずつずらしながらその後の要素にも繰り返す事で結果小さい順に並べ替えられるというワケです。

for (i = 0; i < 9; i++){
	for (j = 1 + i; j < 10; j++){
		if (ary[i] > ary[j]){
			w = ary[i];
			ary[i] = ary[j];
			ary[j] = w;
		}
	}
}

もし大きい順に並べ替えたい場合は途中の符号を

if (ary[i] > ary[j])

if (ary[i] < ary[j])

逆にすれば大きい順に並べ替えられます。

基本選択法関数

#include <stdio.h>

void my_sort(int *, int);

int main(){
	int ary[10] = {1,5,7,2,9,8,6,4,3,0};
	int i;
	
	my_sort(ary, sizeof(ary) / sizeof(int));

	for (i = 0; i < 10; i++){
		printf("%d ", ary[i]);
	}
	printf("\n");

	return 0;
}

void my_sort(int *ary,int size){
	int i, j, tmp;
	for (i = 0; i < size - 1; i++){
		for (j = i + 1; j < size; j++){
			if (*(ary + i) > *(ary + j)){
				tmp = *(ary + i);
				*(ary + i) = *(ary + j);
				*(ary + j) = tmp;
			}
		}
	}
}

■実行結果■

画像(cs_6_2)

基本選択法の関数を作ります。

void my_sort(int *ary,int size){
	int i, j, tmp;
	for (i = 0; i < size - 1; i++){
		for (j = i + 1; j < size; j++){
			if (*(ary + i) > *(ary + j)){
				tmp = *(ary + i);
				*(ary + i) = *(ary + j);
				*(ary + j) = tmp;
			}
		}
	}
}

ここで必要な情報は並べ替える配列とそのサイズなので

void my_sort(int *ary,int size)

引数はこちらになります。

あとは同じようにループ用、並べ替え用の変数を用意してそれぞれを比べて入れ替えていくだけです。

配列が引数の場合はその先頭アドレスが渡されるのでそのまま

*ary

こちらが最初の要素となり、その後の要素はそこにアドレス演算をするようなカタチで求めます。

ary[2]

*(ary + 2)

配列などを渡している時はバッファオーバーしないように配列サイズの監視も重要です。

構造体に基本選択法

#include <stdio.h>

struct PLAYER{
	char *name;
	int num;
};

struct PLAYER set_data(char *, int);
void my_sort2(struct PLAYER *, int);

int main(){
	struct PLAYER player[5];
	int i;

	player[0] = set_data("田中", 5);
	player[1] = set_data("鈴木", 1);
	player[2] = set_data("佐藤", 3);
	player[3] = set_data("斎藤", 4);
	player[4] = set_data("渡辺", 2);

	for (i = 0; i < 5; i++){
		printf("%s %d\n", player[i].name, player[i].num);
	}

	printf("\n");

	my_sort2(player, sizeof(player) / sizeof(struct PLAYER));

	for (i = 0; i < 5; i++){
		printf("%s %d\n", player[i].name, player[i].num);
	}

	return 0;
}

struct PLAYER set_data(char *name, int num){
	struct PLAYER tmp;
	tmp.name = name;
	tmp.num = num;
	return tmp;
}

void my_sort2(struct PLAYER *ary, int size){
	struct PLAYER tmp;
	int i, j;
	for (i = 0; i < size - 1; i++){
		for (j = i + 1; j < size; j++){
			if ((ary + i)->num >(ary + j)->num){
				tmp = *(ary + i);
				*(ary + i) = *(ary + j);
				*(ary + j) = tmp;
			}
		}
	}
}

■実行結果■

画像(cs_6_3)

より実用的なプログラムにおいては構造体の特定の要素を基準に並べ替えをする事もあるかもしれません。

struct PLAYER{
	char *name;
	int num;
};

それぞれのプレイヤーに割り振られたナンバーをもとに並べ替えを行います。

void my_sort2(struct PLAYER *ary, int size){
	struct PLAYER tmp;
	int i, j;
	for (i = 0; i < size - 1; i++){
		for (j = i + 1; j < size; j++){
			if ((ary + i)->num >(ary + j)->num){
				tmp = *(ary + i);
				*(ary + i) = *(ary + j);
				*(ary + j) = tmp;
			}
		}
	}
}

今回は構造体の配列を渡すので引数は

void my_sort2(struct PLAYER *ary, int size)

構造体のポインタとその配列のサイズになりますね。

あとは同じようにループ用、並べ替え用の構造体変数を用意してそれぞれを比べて入れ替えていくだけです。

それぞれの要素を知りたい時はポインタで受け取っているので

ary[2].num

(ary + 2)->num

のようにアドレス演算をした上でアロー演算子を使う事と、今回の入れ替えは構造体まるごと入れ替えるので

tmp = ary[2]

tmp = *(ary + 2)

のようにします。

□ページの先頭へ□

□目次へ戻る□

□HOME□

広告

↓2017年06月16日発売↓

やさしいC 第5版 (「やさしい」シリーズ)

新品価格
¥2,700から
(2017/5/1 13:05時点)

↓2014年08月09日発売↓

新・明解C言語 入門編 (明解シリーズ)

新品価格
¥2,484から
(2017/5/1 13:08時点)

↓2016年02月20日発売↓

新・解きながら学ぶC言語

新品価格
¥2,160から
(2017/5/1 13:10時点)

↓2017年02月11日発売↓

C言語プログラミング基本例題88 88

新品価格
¥3,024から
(2017/5/1 13:12時点)

↓2016年12月15日発売↓

Cの絵本 第2版 C言語が好きになる新しい9つの扉

新品価格
¥1,490から
(2017/5/1 13:13時点)

↓2017年02月08日発売↓

新・明解C言語で学ぶアルゴリズムとデータ構造 (明解シリーズ)

新品価格
¥2,700から
(2017/5/1 13:15時点)