LoginSignup
23
21

More than 5 years have passed since last update.

@mpyw(mpyw)

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

Posted at

大学の課題用。

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

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)にかかるコストがゼロであると仮定できるとき。
つまり理論上の話。

Comparison

graph.png

23
21
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
23
21