質問内容
下記のC言語で書いたコードを使って、3つのソートアルゴリズム間の速度を比較してみました。
(出力結果に表示される処理時間は精密なものではないかもしれませんが)
結果
1位:選択ソート
2位:C言語標準ライブラリのqsort()
3位:バブルソート
qsortが最速、選択ソートとバブルソートが同じくらい遅いと予想していました。
しかし、何度試しても選択ソートが最速だったのです。
このqsortの中身がクイックソートでもマージソートでも、速度はO(nlogn)だと思っていたので意外でした。
理由はどこにあるのでしょうか?
よろしくお願いします。
該当のソースコード
C
1#include<stdio.h> 2#include<stdlib.h> 3#include<time.h> 4 5#define FUNC_NAME(x) (#x) 6 7void sort_counter(void (*sort)(int*, size_t), int* array, size_t length, const char* mes); 8void bubble_sort(int* array, size_t length); 9void select_sort(int* array, size_t length); 10void quick_sort(int* array, size_t length); 11int numcmp(const void* lhv, const void* rhv); 12 13int main() 14{ 15 16 const int Array_length = 100000; 17 const int Sort_algorithms = 3; 18 19 int* random_array; 20 int* copy_array[Sort_algorithms]; 21 22 random_array = (int*)malloc(sizeof(int) * Array_length); 23 for(int i = 0; i < Sort_algorithms; i++) { 24 copy_array[i] = (int*)malloc(sizeof(int) * Array_length); 25 } 26 27 srand(time(NULL)); 28 for(int i = 0; i < Array_length; i++) { 29 30 random_array[i] = rand(); 31 for(int j = 0; j < Sort_algorithms ; j++) { 32 copy_array[j][i] = random_array[i]; 33 } 34 } 35 36 //***実際に比較を実行する関数*** 37 sort_counter(bubble_sort, copy_array[0], Array_length, FUNC_NAME(bubble_sort)); 38 sort_counter(select_sort, copy_array[1], Array_length, FUNC_NAME(select_sort)); 39 sort_counter(quick_sort, copy_array[2], Array_length, FUNC_NAME(quick_sort)); 40 //***************************** 41 42 free(random_array); 43 for(int i = 0; i < Sort_algorithms; i++) { 44 free(copy_array[i]); 45 } 46 47 return 0; 48} 49 50void sort_counter(void (*sort)(int*, size_t), int* array, size_t length, const char* mes) { 51 52 time_t start_time = time(NULL); 53 54 puts(mes); 55 sort(array, length); 56 57 printf("経過時間: %.0lf秒\n\n", difftime(time(NULL), start_time)); 58} 59 60void bubble_sort(int* array, size_t length) { 61 62 int temp = 0; 63 for(int i = 0; i < length -1; i++) { 64 for(int j = length - 1; j > i; j--) { 65 if(array[i] > array[j]) { 66 temp = array[i]; 67 array[i] = array[j]; 68 array[j] = temp; 69 } 70 } 71 } 72} 73 74void select_sort(int* array, size_t length) { 75 76 int temp = 0, index = 0; 77 for(int i = 0; i < 10; i++) { 78 index = i; 79 80 for(int j = i + 1; j < length; j++) { 81 if(array[index] >= array[j]) { 82 index = j; 83 } 84 } 85 86 temp = array[i]; 87 array[i] = array[index]; 88 array[index] = temp; 89 } 90} 91 92void quick_sort(int* array, size_t length) { 93 94 qsort(array, length, sizeof(int), numcmp); 95} 96 97int numcmp(const void* lhv, const void* rhv) { 98 99 return *(int*)lhv - *(int*)rhv; 100}
実行環境
OS:Ubuntu18.04
Cコンパイラ:gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0
補足、実際に実行される方へ
実際に実行すると、bubble_sortのところで22秒ほど時間がかかってCPU使用率が100%になりました、ご注意下さい。
また、select_sortとquick_sortを細かく比較するときは、main()内の定数Array_lengthを大きくしてください。
その時にbubble_sortの処理時間が爆発的に大きくなりますので、main()内のsort_counter(bubble_sort, copy_array[0], Array_length, FUNC_NAME(bubble_sort));の箇所をコメントしていただく事をおすすめします。
分かりづらくてすみません。
回答3件
あなたの回答
tips
プレビュー