2007年度後期 情報数理概説 参考プログラム

ソーティング

前のページ

選択整列

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

void sort(int n, int array[]) {
    int i, j;
    int tmp;

    for (i = 0; i < n -1; i++) {
	for (j = i + 1; j < n; j++) {
	    if (array[i] > array[j]) {
		tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	    }
	}
    }
}

int main(int argc, char *argv[]) {
    int i, n, seed;
    int ar[MAX];

    if (argc <= 2) {
	printf("引数が足りません\n%s 配列の数 乱数の種\n", argv[0]);
	return 1;
    };
    n = strtol(argv[1], NULL, 10);
    if (n > MAX) {
	n = MAX;
    }
    seed = strtol(argv[2], NULL, 10);
    srandom(seed);
    for (i = 0; i < n; i++) {
	ar[i] = random();
    }
    printf("配列に乱数をセットしました。\n");
    for (i = 0; i < n; i++) {
	printf("% 11d ", ar[i]);
	if (i % 6 == 5) {
	    printf("\n");
	}
    }
    printf("\n");
    sort(n, ar);
    printf("配列をソートしました。\n");
    for (i = 0; i < n; i++) {
	printf("% 11d ", ar[i]);
	if (i % 6 == 5) {
	    printf("\n");
	}
    }
    printf("\n");
    return 0;
}

• ダウンロード： sort-a.c
• ダウンロード： sort-ap.c プリント文を入れたもの

マージソート

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

void merge(int array[], int s1, int e1, int s2, int e2) {
    int tmp[MAX / 2 + 1];
    int i, j, k;

    /* tmpにコピー */
    for (i = 0; i <= e1 - s1; i++) {
	tmp[i] = array[s1 + i];
    }
    for (i = 0, j = s2, k = s1; i <= e1 - s1 && j <= e2;) {
	if (tmp[i] < array[j]) {
	    array[k++] = tmp[i++];
	} else {
	    array[k++] = array[j++];
	}
    }
    /* 余りの処理 */
    while (i <= e1 - s1) {
	array[k++] = tmp[i++];
    }
}

void sort(int array[], int start, int end) {
    int half;
    
    if (start >= end) {
	return;
    }
    half = start + (end - start) / 2;
    sort(array, start, half);
    sort(array, half + 1, end);
    merge(array, start, half, half+1, end);
}

int main(int argc, char *argv[]) {
    int i, n, seed;
    int ar[MAX];

    if (argc <= 2) {
	printf("引数が足りません\n%s 配列の数 乱数の種\n", argv[0]);
	return 1;
    };
    n = strtol(argv[1], NULL, 10);
    if (n > MAX) {
	n = MAX;
    }
    seed = strtol(argv[2], NULL, 10);
    srandom(seed);
    for (i = 0; i < n; i++) {
	ar[i] = random();
    }
    printf("配列に乱数をセットしました。\n");
    for (i = 0; i < n; i++) {
	printf("% 11d ", ar[i]);
	if (i % 6 == 5) {
	    printf("\n");
	}
    }
    printf("\n");
    sort(ar, 0, n - 1);
    printf("配列をソートしました。\n");
    for (i = 0; i < n; i++) {
	printf("% 11d ", ar[i]);
	if (i % 6 == 5) {
	    printf("\n");
	}
    }
    printf("\n");
    return 0;
}

• ダウンロード： sort-b.c
• ダウンロード： sort-bp.c プリント文を入れたもの

構造体のソート

物足りない人のために、構造体を使ったソーティングプログラムを挙げておきます。 通常、ソートでは並べ替えの順番を決めるキーとなる部分と、それ以外のデータの まとまりをソートします。

この例は、乱数とマージソートを使ってトランプのシャフルを行うプログラムです。

ダウンロード： sort-c.c