大学の課題用。
データ構造とアルゴリズム 最終課題
Profile
(限定公開から全体公開にしたので伏せます)
System Environment
Items | Details |
---|---|
CPU | Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz (8 CPUs), ~3.4GHz |
RAM | 16384 MB |
OS | Windows 7 Ultimate 64-bit |
Bubble Sort
Code
BubbleSort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(long *a, long *b) {
long tmp = *a;
*a = *b;
*b = tmp;
}
void print_r(const long x[], const long n) {
long i;
for (i = 0; i < 10 && i < n; i++) {
printf("%ld\n", x[i]);
}
if (n <= 10) {
return;
} else if (n < 20) {
i = 10;
} else {
i = n - 10;
}
printf("...\n");
for (; i < n; i++) {
printf("%ld\n", x[i]);
}
}
void set_array(long array[], const long count, const int index) {
FILE *fp;
char filename[50];
long i;
long tmp;
sprintf(filename, "data/%ld/%ld-%d", count, count, index);
fp = fopen(filename, "r");
if (fp == NULL) {
printf("Can't open \"%s\"\n", filename);
exit(1);
}
for (i = 0; i < count; i++) {
if (fscanf(fp, "%ld", &tmp) == -1) {
printf("Error occurred on fscanf()\n");
exit(1);
}
array[i] = tmp;
}
}
void bubble_sort(long x[], const long n) {
long i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (x[j] > x[j + 1]) {
swap(&x[j], &x[j + 1]);
}
}
}
}
int main(void) {
long *array;
long count;
int i;
long start, end, score[10], sum = 0;
printf("count = ");
scanf("%ld", &count);
printf("\n");
array = (long *)malloc(sizeof(long) * count);
for (i = 0; i < 10; i++) {
set_array(array, count, i);
if (i == 0) {
printf("[Before]:\n");
print_r(array, count);
printf("\n");
}
start = clock();
bubble_sort(array, count);
end = clock();
if (i == 0) {
printf("[After]:\n");
print_r(array, count);
printf("\n");
}
score[i] = end - start;
sum += score[i];
printf("Time[%d]: %ld[msec]\n", i, score[i]);
}
printf("\nAverage: %ld[msec]\n\n", sum / 10);
free(array);
return 0;
}
Results
10000
Time[0]: 310[msec]
Time[1]: 308[msec]
Time[2]: 306[msec]
Time[3]: 303[msec]
Time[4]: 304[msec]
Time[5]: 317[msec]
Time[6]: 308[msec]
Time[7]: 307[msec]
Time[8]: 306[msec]
Time[9]: 307[msec]
Average: 307[msec]
50000
Time[0]: 8220[msec]
Time[1]: 8210[msec]
Time[2]: 8223[msec]
Time[3]: 8180[msec]
Time[4]: 8265[msec]
Time[5]: 8345[msec]
Time[6]: 8269[msec]
Time[7]: 8232[msec]
Time[8]: 8227[msec]
Time[9]: 8304[msec]
Average: 8247[msec]
100000
Time[0]: 33514[msec]
Time[1]: 33537[msec]
Time[2]: 33404[msec]
Time[3]: 33431[msec]
Time[4]: 33601[msec]
Time[5]: 33428[msec]
Time[6]: 33344[msec]
Time[7]: 33352[msec]
Time[8]: 33335[msec]
Time[9]: 33355[msec]
Average: 33430[msec]
500000
Time[0]: 841646[msec]
Time[1]: 844127[msec]
Time[2]: 841467[msec]
Time[3]: 841070[msec]
Time[4]: 842152[msec]
Time[5]: 842417[msec]
Time[6]: 839184[msec]
Time[7]: 839047[msec]
Time[8]: 837693[msec]
Time[9]: 839578[msec]
Average: 840838[msec]
1000000
O(n^2) に比例していると結果から推察されるので、計算で求めると55~65分程度と思われる。
Shell Sort
Code
ShellSort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(long *a, long *b) {
long tmp = *a;
*a = *b;
*b = tmp;
}
void print_r(const long x[], const long n) {
long i;
for (i = 0; i < 10 && i < n; i++) {
printf("%ld\n", x[i]);
}
if (n <= 10) {
return;
} else if (n < 20) {
i = 10;
} else {
i = n - 10;
}
printf("...\n");
for (; i < n; i++) {
printf("%ld\n", x[i]);
}
}
void set_array(long array[], const long count, const int index) {
FILE *fp;
char filename[50];
long i;
long tmp;
sprintf(filename, "data/%ld/%ld-%d", count, count, index);
fp = fopen(filename, "r");
if (fp == NULL) {
printf("Can't open \"%s\"\n", filename);
exit(1);
}
for (i = 0; i < count; i++) {
if (fscanf(fp, "%ld", &tmp) == -1) {
printf("Error occurred on fscanf()\n");
exit(1);
}
array[i] = tmp;
}
}
void shell_sort(long x[], const long n) {
long i, j, k, m;
for (m = n / 2; m > 0; m /= 2) {
for (i = m; i < n; i++) {
for (j = i - m; j >= 0; j -= m) {
if (x[j] <= x[j + m]) {
break;
} else {
swap(&x[j], &x[j + m]);
}
}
}
}
}
int main(void) {
long *array;
long count;
int i;
long start, end, score[10], sum = 0;
printf("count = ");
scanf("%ld", &count);
printf("\n");
array = (long *)malloc(sizeof(long) * count);
for (i = 0; i < 10; i++) {
set_array(array, count, i);
if (i == 0) {
printf("[Before]:\n");
print_r(array, count);
printf("\n");
}
start = clock();
shell_sort(array, count);
end = clock();
if (i == 0) {
printf("[After]:\n");
print_r(array, count);
printf("\n");
}
score[i] = end - start;
sum += score[i];
printf("Time[%d]: %ld[msec]\n", i, score[i]);
}
printf("\nAverage: %ld[msec]\n\n", sum / 10);
free(array);
return 0;
}
Results
10000
Time[0]: 2[msec]
Time[1]: 3[msec]
Time[2]: 3[msec]
Time[3]: 2[msec]
Time[4]: 3[msec]
Time[5]: 2[msec]
Time[6]: 3[msec]
Time[7]: 2[msec]
Time[8]: 3[msec]
Time[9]: 2[msec]
Average: 2[msec]
50000
Time[0]: 16[msec]
Time[1]: 17[msec]
Time[2]: 17[msec]
Time[3]: 16[msec]
Time[4]: 17[msec]
Time[5]: 17[msec]
Time[6]: 17[msec]
Time[7]: 17[msec]
Time[8]: 17[msec]
Time[9]: 17[msec]
Average: 16[msec]
100000
Time[0]: 38[msec]
Time[1]: 39[msec]
Time[2]: 38[msec]
Time[3]: 39[msec]
Time[4]: 39[msec]
Time[5]: 38[msec]
Time[6]: 37[msec]
Time[7]: 37[msec]
Time[8]: 38[msec]
Time[9]: 37[msec]
Average: 38[msec]
500000
Time[0]: 248[msec]
Time[1]: 262[msec]
Time[2]: 246[msec]
Time[3]: 253[msec]
Time[4]: 256[msec]
Time[5]: 271[msec]
Time[6]: 249[msec]
Time[7]: 254[msec]
Time[8]: 251[msec]
Time[9]: 254[msec]
Average: 254[msec]
1000000
Time[0]: 578[msec]
Time[1]: 561[msec]
Time[2]: 567[msec]
Time[3]: 585[msec]
Time[4]: 594[msec]
Time[5]: 575[msec]
Time[6]: 568[msec]
Time[7]: 567[msec]
Time[8]: 628[msec]
Time[9]: 576[msec]
Average: 579[msec]
Quick Sort
Code
QuickSort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(long *a, long *b) {
long tmp = *a;
*a = *b;
*b = tmp;
}
void print_r(const long x[], const long n) {
long i;
for (i = 0; i < 10 && i < n; i++) {
printf("%ld\n", x[i]);
}
if (n <= 10) {
return;
} else if (n < 20) {
i = 10;
} else {
i = n - 10;
}
printf("...\n");
for (; i < n; i++) {
printf("%ld\n", x[i]);
}
}
void set_array(long array[], const long count, const int index) {
FILE *fp;
char filename[50];
long i;
long tmp;
sprintf(filename, "data/%ld/%ld-%d", count, count, index);
fp = fopen(filename, "r");
if (fp == NULL) {
printf("Can't open \"%s\"\n", filename);
exit(1);
}
for (i = 0; i < count; i++) {
if (fscanf(fp, "%ld", &tmp) == -1) {
printf("Error occurred on fscanf()\n");
exit(1);
}
array[i] = tmp;
}
}
void quick_sort(long x[], const long left, const long right) {
long pivot, i, j;
pivot = x[(left + right) / 2];
for (i = left, j = right; ; i++, j--) {
while (x[i] < pivot) {
i++;
}
while (pivot < x[j]) {
j--;
}
if (i >= j) {
break;
}
swap(&x[i], &x[j]);
}
if (left < i - 1) {
quick_sort(x, left, i - 1);
}
if (j + 1 < right) {
quick_sort(x, j + 1, right);
}
}
int main(void) {
long *array;
long count;
int i;
long start, end, score[10], sum = 0;
printf("count = ");
scanf("%ld", &count);
printf("\n");
array = (long *)malloc(sizeof(long) * count);
for (i = 0; i < 10; i++) {
set_array(array, count, i);
if (i == 0) {
printf("[Before]:\n");
print_r(array, count);
printf("\n");
}
start = clock();
quick_sort(array, 0, count - 1);
end = clock();
if (i == 0) {
printf("[After]:\n");
print_r(array, count);
printf("\n");
}
score[i] = end - start;
sum += score[i];
printf("Time[%d]: %ld[msec]\n", i, score[i]);
}
printf("\nAverage: %ld[msec]\n\n", sum / 10);
free(array);
return 0;
}
Results
10000
Time[0]: 1[msec]
Time[1]: 1[msec]
Time[2]: 1[msec]
Time[3]: 1[msec]
Time[4]: 1[msec]
Time[5]: 1[msec]
Time[6]: 1[msec]
Time[7]: 1[msec]
Time[8]: 1[msec]
Time[9]: 2[msec]
Average: 1[msec]
50000
Time[0]: 9[msec]
Time[1]: 7[msec]
Time[2]: 6[msec]
Time[3]: 6[msec]
Time[4]: 6[msec]
Time[5]: 6[msec]
Time[6]: 6[msec]
Time[7]: 6[msec]
Time[8]: 6[msec]
Time[9]: 6[msec]
Average: 6[msec]
100000
Time[0]: 13[msec]
Time[1]: 12[msec]
Time[2]: 12[msec]
Time[3]: 13[msec]
Time[4]: 12[msec]
Time[5]: 12[msec]
Time[6]: 12[msec]
Time[7]: 12[msec]
Time[8]: 12[msec]
Time[9]: 12[msec]
Average: 12[msec]
500000
Time[0]: 70[msec]
Time[1]: 71[msec]
Time[2]: 72[msec]
Time[3]: 72[msec]
Time[4]: 71[msec]
Time[5]: 75[msec]
Time[6]: 72[msec]
Time[7]: 71[msec]
Time[8]: 71[msec]
Time[9]: 72[msec]
Average: 71[msec]
1000000
Time[0]: 148[msec]
Time[1]: 148[msec]
Time[2]: 151[msec]
Time[3]: 149[msec]
Time[4]: 149[msec]
Time[5]: 148[msec]
Time[6]: 152[msec]
Time[7]: 149[msec]
Time[8]: 150[msec]
Time[9]: 150[msec]
Average: 149[msec]
Merge Sort
Code
MergeSort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void print_r(const long x[], const long n) {
long i;
for (i = 0; i < 10 && i < n; i++) {
printf("%ld\n", x[i]);
}
if (n <= 10) {
return;
} else if (n < 20) {
i = 10;
} else {
i = n - 10;
}
printf("...\n");
for (; i < n; i++) {
printf("%ld\n", x[i]);
}
}
void set_array(long array[], const long count, const int index) {
FILE *fp;
char filename[50];
long i;
long tmp;
sprintf(filename, "data/%ld/%ld-%d", count, count, index);
fp = fopen(filename, "r");
if (fp == NULL) {
printf("Can't open \"%s\"\n", filename);
exit(1);
}
for (i = 0; i < count; i++) {
if (fscanf(fp, "%ld", &tmp) == -1) {
printf("Error occurred on fscanf()\n");
exit(1);
}
array[i] = tmp;
}
}
void merge_sort(long x[], long y[], const long left, const long right) {
int mid, i, j, k;
if (left >= right) {
return;
}
mid = (left + right) / 2;
merge_sort(x, y, left, mid);
merge_sort(x, y, mid + 1, right);
for (i = left; i <= mid; i++) {
y[i] = x[i];
}
for (i = mid + 1, j = right; i <= right; i++, j--) {
y[i] = x[j];
}
i = left;
j = right;
for (k = left; k <= right; k++) {
if (y[i] <= y[j]) {
x[k] = y[i++];
} else {
x[k] = y[j--];
}
}
}
int main(void) {
long *array;
long *copy;
long count;
int i;
long start, end, score[10], sum = 0;
printf("count = ");
scanf("%ld", &count);
printf("\n");
array = (long *)malloc(sizeof(long) * count);
copy = (long *)malloc(sizeof(long) * count);
for (i = 0; i < 10; i++) {
set_array(array, count, i);
if (i == 0) {
printf("[Before]:\n");
print_r(array, count);
printf("\n");
}
start = clock();
merge_sort(array, copy, 0, count - 1);
end = clock();
if (i == 0) {
printf("[After]:\n");
print_r(array, count);
printf("\n");
}
score[i] = end - start;
sum += score[i];
printf("Time[%d]: %ld[msec]\n", i, score[i]);
}
printf("\nAverage: %ld[msec]\n\n", sum / 10);
free(array);
free(copy);
return 0;
}
Results
10000
Time[0]: 1[msec]
Time[1]: 1[msec]
Time[2]: 2[msec]
Time[3]: 1[msec]
Time[4]: 1[msec]
Time[5]: 2[msec]
Time[6]: 1[msec]
Time[7]: 1[msec]
Time[8]: 1[msec]
Time[9]: 2[msec]
Average: 1[msec]
50000
Time[0]: 8[msec]
Time[1]: 8[msec]
Time[2]: 8[msec]
Time[3]: 7[msec]
Time[4]: 8[msec]
Time[5]: 9[msec]
Time[6]: 8[msec]
Time[7]: 7[msec]
Time[8]: 8[msec]
Time[9]: 7[msec]
Average: 7[msec]
100000
Time[0]: 17[msec]
Time[1]: 16[msec]
Time[2]: 16[msec]
Time[3]: 16[msec]
Time[4]: 16[msec]
Time[5]: 16[msec]
Time[6]: 16[msec]
Time[7]: 16[msec]
Time[8]: 16[msec]
Time[9]: 16[msec]
Average: 16[msec]
500000
Time[0]: 93[msec]
Time[1]: 93[msec]
Time[2]: 92[msec]
Time[3]: 93[msec]
Time[4]: 93[msec]
Time[5]: 92[msec]
Time[6]: 93[msec]
Time[7]: 93[msec]
Time[8]: 93[msec]
Time[9]: 92[msec]
Average: 92[msec]
1000000
Time[0]: 195[msec]
Time[1]: 195[msec]
Time[2]: 194[msec]
Time[3]: 199[msec]
Time[4]: 198[msec]
Time[5]: 195[msec]
Time[6]: 198[msec]
Time[7]: 201[msec]
Time[8]: 194[msec]
Time[9]: 193[msec]
Average: 196[msec]
Counting Sort
Code
CountingSort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 999999
void print_r(const long x[], const long n) {
long i;
for (i = 0; i < 10 && i < n; i++) {
printf("%ld\n", x[i]);
}
if (n <= 10) {
return;
} else if (n < 20) {
i = 10;
} else {
i = n - 10;
}
printf("...\n");
for (; i < n; i++) {
printf("%ld\n", x[i]);
}
}
void set_array(long array[], const long count, const int index) {
FILE *fp;
char filename[50];
long i;
long tmp;
sprintf(filename, "data/%ld/%ld-%d", count, count, index);
fp = fopen(filename, "r");
if (fp == NULL) {
printf("Can't open \"%s\"\n", filename);
exit(1);
}
for (i = 0; i < count; i++) {
if (fscanf(fp, "%ld", &tmp) == -1) {
printf("Error occurred on fscanf()\n");
exit(1);
}
array[i] = tmp;
}
}
void counting_sort(long x[], long y[], long counts[], long n) {
long i;
for (i = 0; i < n; i++) {
counts[x[i]]++;
}
for (i = 0; i < MAX; i++) {
counts[i+1] += counts[i];
}
for (i = n - 1; i >= 0; i--) {
y[--counts[x[i]]] = x[i];
}
}
int main(void) {
long *before;
long *after;
long *counts;
long count;
int i;
long j;
long start, end, score[10], sum = 0;
printf("count = ");
scanf("%ld", &count);
printf("\n");
before = (long *)malloc(sizeof(long) * count);
after = (long *)malloc(sizeof(long) * (count - 1));
counts = (long *)malloc(sizeof(long) * (MAX + 1));
for (i = 0; i < 9; i++) {
set_array(before, count, i);
for (j = 0; j <= MAX; j++) {
counts[j] = 0;
}
if (i == 0) {
printf("[Before]:\n");
print_r(before, count);
printf("\n");
}
start = clock();
counting_sort(before, after, counts, count);
end = clock();
if (i == 0) {
printf("[After]:\n");
print_r(after, count);
printf("\n");
}
score[i] = end - start;
sum += score[i];
printf("Time[%d]: %ld[msec]\n", i, score[i]);
}
printf("\nAverage: %ld[msec]\n\n", sum / 10);
free(before);
free(after);
free(counts);
return 0;
}
Results
10000
Time[0]: 4[msec]
Time[1]: 4[msec]
Time[2]: 2[msec]
Time[3]: 2[msec]
Time[4]: 3[msec]
Time[5]: 3[msec]
Time[6]: 3[msec]
Time[7]: 3[msec]
Time[8]: 3[msec]
Average: 2[msec]
50000
Time[0]: 4[msec]
Time[1]: 3[msec]
Time[2]: 4[msec]
Time[3]: 4[msec]
Time[4]: 4[msec]
Time[5]: 3[msec]
Time[6]: 3[msec]
Time[7]: 3[msec]
Time[8]: 3[msec]
Average: 3[msec]
100000
Time[0]: 5[msec]
Time[1]: 4[msec]
Time[2]: 4[msec]
Time[3]: 4[msec]
Time[4]: 5[msec]
Time[5]: 4[msec]
Time[6]: 4[msec]
Time[7]: 4[msec]
Time[8]: 4[msec]
Average: 3[msec]
500000
Time[0]: 20[msec]
Time[1]: 19[msec]
Time[2]: 19[msec]
Time[3]: 18[msec]
Time[4]: 20[msec]
Time[5]: 20[msec]
Time[6]: 18[msec]
Time[7]: 18[msec]
Time[8]: 18[msec]
Average: 17[msec]
1000000
Time[0]: 44[msec]
Time[1]: 43[msec]
Time[2]: 43[msec]
Time[3]: 42[msec]
Time[4]: 41[msec]
Time[5]: 59[msec]
Time[6]: 42[msec]
Time[7]: 44[msec]
Time[8]: 42[msec]
Average: 40[msec]
Radix Sort
テーブルのセルをあらかじめ 10×データ数 だけ用意しておくのでは、カウンティングソートの完全劣化となるので、今回はやる意味が薄いと見込んで省略。
基数ソートが優れていると言えるのは、線形リストで同じ基数を持つ要素をつなぐように実装し、その要素の動的確保(malloc)にかかるコストがゼロであると仮定できるとき。
つまり理論上の話。