ソートとサーチ¶
クイックソート¶
qsort.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | /*
stdlib.h [qsort]
書式: void qsort(
void *base,
size_t n,
size_t size,
int (*comp)(const void *c1, const void *c2)
)
機能: クリックソート (配列要素の並び替え) を行う
引数: void *base: 並び替えを行う配列
size_t n: 配列要素の個数
size_t size: 配列要素のサイズ
int (*comp)(const void *c1, const void *c2): 比較関数
戻り値: なし
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 30
int comp(const void *c1, const void *c2);
int main(void){
int i;
int base[SIZE];
/* 乱数の生成 */
srand( (unsigned int)time(NULL) );
for(i = 0; i < SIZE; i++){
if(i % 4 == 0) printf("\n");
base[i] = rand() % 100; /* 0 ~ 99 の乱数 */
printf("%2d ", base[i]);
}
/* クイックソート */
printf("\n\n--クイックソート実行--\n");
qsort(base, SIZE, sizeof(int), comp);
/* ソート後のデータを表示 */
for(i = 0; i < SIZE; i++){
if(i % 4 == 0) printf("\n");
printf("%2d ", base[i]);
}
printf("\n");
return EXIT_SUCCESS;
}
/* 比較関数 */
/*
比較関数 (comp) の戻り値 (昇順)
c1 < c2 負の値 (-1)
c1 == c2 0
c1 > c2 正の値 (1)
*/
/*
比較関数 (comp) の戻り値 (降順)
c1 > c2 負の値 (-1)
c1 == c2 0
c1 < c2 正の値 (1)
*/
int comp(const void *c1, const void *c2){
int tmp1 = *(int *)c1;
int tmp2 = *(int *)c2;
if(tmp1 < tmp2)
return -1;
if(tmp1 == tmp2)
return 0;
if(tmp1 > tmp2)
return 1;
return EXIT_SUCCESS;
}
|
qsort.c の実行結果は:
[cactus:~/code_c/refer]% ./qsort
55 55 50 68
68 63 49 45
81 82 99 97
66 34 78 54
69 22 48 22
58 45 62 68
43 70 4 98
81 77
--クイックソート実行--
4 22 22 34
43 45 45 48
49 50 54 55
55 58 62 63
66 68 68 68
69 70 77 78
81 81 82 97
98 99
バイナリサーチ¶
bsearch.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | /*
stdlib.h [bsearch]
書式: void* bsearch(
const void *key,
const void *base,
size_t n,
size_t size,
int (*comp)(const void *c1, const void *c2)
)
機能: バイナリサーチ (二分探索) を行う
引数: const void *key: 検索する値
const void *base: 検索する配列
size_t n: 配列要素の個数
size_t size: 配列要素のサイズ
int (*comp)(const void *c1, const void *c2): 比較関数
戻り値: 検索が成功した場合は, 要素のポインタを返し,
発見できなかった場合は, NULL を返す.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 30
int comp(const void *c1, const void *c2);
int main(void){
int i;
int key = 25;
int *result;
int base[SIZE];
/* 乱数の生成 */
srand( (unsigned int)time(NULL) );
for(i = 0; i < SIZE; i++){
if(i % 10 == 0) printf("\n");
base[i] = rand() % 100; /* 0 ~ 99 の乱数 */
printf("%2d ", base[i]);
}
/* クイックソート */
printf("\n\n--クイックソート実行--\n");
qsort(base, SIZE, sizeof(int), comp);
/* ソート後のデータを表示 */
for(i = 0; i < SIZE; i++){
if(i % 10 == 0) printf("\n");
printf("%2d ", base[i]);
}
printf("\n");
/* バイナリサーチで [25] を検索 */
printf("\n%d を検索\n", key);
result = (int *)bsearch(&key, base, SIZE, sizeof(int), comp);
if(result == NULL)
printf("%d は見つからなかった\n", key);
else
printf("%d が %d 番目の要素として見つかった\n", key, (int)(result - base) );
return EXIT_SUCCESS;
}
/* 比較関数 */
/*
比較関数 (comp) の戻り値 (昇順)
c1 < c2 負の値 (-1)
c1 == c2 0
c1 > c2 正の値 (1)
*/
/*
比較関数 (comp) の戻り値 (降順)
c1 > c2 負の値 (-1)
c1 == c2 0
c1 < c2 正の値 (1)
*/
int comp(const void *c1, const void *c2){
int tmp1 = *(int *)c1;
int tmp2 = *(int *)c2;
if(tmp1 < tmp2)
return -1;
if(tmp1 == tmp2)
return 0;
if(tmp1 > tmp2)
return 1;
return EXIT_SUCCESS;
}
|
bsearch.c の実行結果は:
[cactus:~/code_c/refer]% ./bsearch
20 46 1 10 21 16 41 47 58 1
60 22 93 36 8 42 26 77 56 80
63 98 85 47 83 55 86 94 68 53
--クイックソート実行--
1 1 8 10 16 20 21 22 26 36
41 42 46 47 47 53 55 56 58 60
63 68 77 80 83 85 86 93 94 98
25 を検索
25 は見つからなかった
[cactus:~/code_c/refer]% ./bsearch
27 48 27 68 51 88 85 78 34 63
0 87 38 78 95 45 53 6 96 92
66 67 47 57 96 88 85 25 37 41
--クイックソート実行--
0 6 25 27 27 34 37 38 41 45
47 48 51 53 57 63 66 67 68 78
78 85 85 87 88 88 92 95 96 96
25 を検索
25 が 2 番目の要素として見つかった
構造体のクイックソート¶
qsort-struct.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | /*
stdlib.h [qsort]
書式: void qsort(
void *base,
size_t n,
size_t size,
int (*comp)(const void *c1, const void *c2)
)
機能: クリックソート (配列要素の並び替え) を行う
引数: void *base: 並び替えを行う配列
size_t n: 配列要素の個数
size_t size: 配列要素のサイズ
int (*comp)(const void *c1, const void *c2): 比較関数
戻り値: なし
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 8
typedef struct{
int a;
int b;
int c;
int d;
}TEST;
int comp(const void *c1, const void *c2);
int main(void){
int i;
TEST base[SIZE];
/* 乱数の生成 */
srand( (unsigned int)time(NULL) );
for(i = 0; i < SIZE; i++){
base[i].a = rand() % 100; /* 0 ~ 99 の乱数 */
base[i].b = rand() % 100;
base[i].c = rand() % 100;
base[i].d = rand() % 100;
printf("%2d ", base[i].a);
printf("%2d ", base[i].b);
printf("%2d ", base[i].c);
printf("%2d ", base[i].d);
printf("\n");
}
/* TEST 構造体の b を基準にソート */
/* クイックソート */
printf("\n\n--TEST構造体の b を基準にソート--\n\n");
qsort(base, SIZE, sizeof(TEST), comp);
/* ソート後のデータを表示 */
for(i = 0; i < SIZE; i++){
printf("%2d ", base[i].a);
printf("%2d ", base[i].b);
printf("%2d ", base[i].c);
printf("%2d ", base[i].d);
printf("\n");
}
return EXIT_SUCCESS;
}
/* 比較関数 */
int comp(const void *c1, const void *c2){
TEST test1 = *(TEST *)c1;
TEST test2 = *(TEST *)c2;
/* b を基準とする */
int tmp1 = test1.b;
int tmp2 = test2.b;
/* [a < b: 負の値, a == b: 0, a > b: 正の値] */
/* tmp1 - tmp2: 昇順 */
/* tmp2 - tmp1: 降順 */
return tmp1 - tmp2;
}
|
qsort-struct.c の実行結果は:
[cactus:~/code_c/refer]% ./qsort-struct
5 30 54 76
86 87 81 77
16 43 44 29
36 83 31 16
33 43 40 61
49 4 92 70
55 20 18 11
16 25 18 98
--TEST構造体の b を基準にソート--
49 4 92 70
55 20 18 11
16 25 18 98
5 30 54 76
33 43 40 61
16 43 44 29
36 83 31 16
86 87 81 77
構造体のバイナリサーチ¶
bsearch-struct.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | /*
stdlib.h [bsearch]
書式: void* bsearch(
const void *key,
const void *base,
size_t n,
size_t size,
int (*comp)(const void *c1, const void *c2)
)
機能: バイナリサーチ (二分探索) を行う
引数: const void *key: 検索する値
const void *base: 検索する配列
size_t n: 配列要素の個数
size_t size: 配列要素のサイズ
int (*comp)(const void *c1, const void *c2): 比較関数
戻り値: 検索が成功した場合は, 要素のポインタを返し,
発見できなかった場合は, NULL を返す.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 5
typedef struct{
int a;
int b;
int c;
int d;
}TEST;
int comp_sort(const void *c1, const void *c2);
int comp_search(const void *c1, const void *c2);
int main(void){
int i;
int key = 25;
TEST *result;
TEST base[SIZE];
/* 乱数の生成 */
srand( (unsigned int)time(NULL) );
for(i = 0; i < SIZE; i++){
if(i % 10 == 0) printf("\n");
base[i].a = rand() % 100; /* 0 ~ 99 の乱数 */
base[i].b = rand() % 100;
base[i].c = rand() % 100;
base[i].d = rand() % 100;
printf("%2d ", base[i].a);
printf("%2d ", base[i].b);
printf("%2d ", base[i].c);
printf("%2d ", base[i].d);
printf("\n");
}
/* クイックソート */
printf("\n\n--クイックソート実行--\n");
qsort(base, SIZE, sizeof(TEST), comp_sort);
/* ソート後のデータを表示 */
for(i = 0; i < SIZE; i++){
printf("%2d ", base[i].a);
printf("%2d ", base[i].b);
printf("%2d ", base[i].c);
printf("%2d ", base[i].d);
printf("\n");
}
/* バイナリサーチで [25] を検索 */
printf("\n%d を検索\n", key);
result = (TEST *)bsearch(&key, base, SIZE, sizeof(TEST), comp_search);
if(result == NULL)
printf("%d は見つからなかった\n", key);
else
printf("%d が %d 番目の要素として見つかった\n", key, (int)(result - base) );
return EXIT_SUCCESS;
}
/* 比較関数 クイックソート用 */
int comp_sort(const void *c1, const void *c2){
TEST test1 = *(TEST *)c1;
TEST test2 = *(TEST *)c2;
int tmp1 = test1.b;
int tmp2 = test2.b;
return tmp1 - tmp2;
}
/* 比較関数バイナリサーチ用 */
int comp_search(const void *c1, const void *c2){
TEST test2 = *(TEST *)c2;
/* c1 は bsearch() の第一引数 (=key) */
int tmp1 = *(int *)c1;
int tmp2 = test2.b;
return tmp1 - tmp2;
}
|
bsearch-struct.c の実行結果は:
[cactus:~/code_c/refer]% ./bsearch-struct
74 72 83 54
26 78 27 62
63 41 78 91
70 72 93 0
66 68 27 68
--クイックソート実行--
63 41 78 91
66 68 27 68
74 72 83 54
70 72 93 0
26 78 27 62
25 を検索
25 は見つからなかった
[cactus:~/code_c/refer]% ./bsearch-struct
12 92 18 59
9 16 41 37
68 25 94 11
34 65 22 65
54 7 90 53
--クイックソート実行--
54 7 90 53
9 16 41 37
68 25 94 11
34 65 22 65
12 92 18 59
25 を検索
25 が 2 番目の要素として見つかった
