何番煎じか知らないけどソート比較

大学の課題用。

----------------------------------------------

データ構造とアルゴリズム 最終課題
===========================

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
----

```c: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 
---------

```text: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]
```

```text: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]
```

```text: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]
```

```text: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]
```

```text:1000000
O(n^2) に比例していると結果から推察されるので、計算で求めると55～65分程度と思われる。
```



Shell Sort
========

Code
-------

```c: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
---------

```text: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]
```

```text: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]
```

```text: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]
```

```text: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]
```

```text: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
-------

```c: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
---------

```text: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]
```

```text: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]
```

```text: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]
```

```text: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]
```

```text: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
-------

```c: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
---------

```text: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]
```

```text: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]
```

```text: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]
```

```text: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]
```

```text: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
------

```c: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
---------

```text: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]
```

```text: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]
```

```text: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]
```

```text: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]
```

```text: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×データ数** だけ用意しておくのでは、カウンティングソートの完全劣化となるので、今回はやる意味が薄いと見込んで省略。
基数ソートが優れていると言えるのは、線形リストで同じ基数を持つ要素をつなぐように実装し、その<ins>要素の動的確保(malloc)にかかるコストがゼロであると仮定できるとき</ins>。
つまり理論上の話。

Comparison
=========

![graph.png](https://qiita-image-store.s3.amazonaws.com/0/25060/5bdb3f32-a7b8-4216-d1d2-77af208d2b3f.png)