質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

3回答

1966閲覧

C言語のqsort()は速いのでしょうか?

extremetriangle

総合スコア14

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2018/06/25 15:45

質問内容

下記の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));の箇所をコメントしていただく事をおすすめします。
分かりづらくてすみません。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

segavvy

2018/06/25 15:53

select_sort()の外側のiのループが10回で終わってしまうようです。ご確認ください。
extremetriangle

2018/06/25 16:01

本当でした!修正したところ、qsortよりもずっと処理に時間がかかりました!これは恥ずかしいですありがとうございます。
extremetriangle

2018/06/25 16:13

segavvyさん、お手数をおかけして申し訳ないのですが、ベストアンサーに選びたいので回答の方に投稿してはいただけないでしょうか?よろしくお願いします。
guest

回答3

0

ベストアンサー

select_sort()の外側のiのループが10回で終わってしまうようです。ご確認ください。

投稿2018/06/25 16:19

segavvy

総合スコア958

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

extremetriangle

2018/06/25 16:23

これは情けないミスをしてしまいました。 100行近くあるコードから間違いをご指摘下さり、ありがとうございました。
segavvy

2018/06/25 16:26

いえいえ、お役に立てたようで良かったです。
guest

0

qsort(array, length, sizeof(int), numcmp);

qsortでは汎用に使えるように、1要素のサイズを決め打ちせずに、引数で与えるようにしています
他のソートは、要素がintだという前提で、要素の入れ替えを行ってますが、
こいつの場合は、要素のサイズが不明なため、memcpy的な関数を使用して要素の入れ替えを行う必要が出てきます

ということで、この比較は公正なものとは言えない、ということになろうかと思われます


ああ、その上、他のソートは値の比較を単なる条件文としてますが、qsortの場合はコールバック関数の呼び出し、という形で比較してますね。
これじゃあとてもとても、その実行時間の比較は意味があるとは言えなくなってしまいますね

投稿2018/06/25 15:59

編集2018/06/25 16:10
y_waiwai

総合スコア87719

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

extremetriangle

2018/06/25 16:10

ご回答ありがとうございます、確かにその点は気になっていました。 比較関数で一度intへのポインタにキャストする必要もあるので、qsort()はいくつかハンデを抱えているのではないかと。要素の交換でも処理に違いが出てくるのには気づきませんでした。
guest

0

解決済みのようですが、かなり間違いがあります。

ランダウの記号で示される計算量は最悪の場合を基準にしています。ですのでクイックソートのオーダはn*nが正解です、誤ってnlognと書かれた資料をどれだけ見たことか。つまり、配列内のデータ分布次第ではバブルソートにすら劣る可能性があります。いうまでもなく、本課題では乱数パターンに大きく依存します。

また、オーダはアルゴリズムと対象データサイズとの関係性を示すものであり、単位のない指標に過ぎません。異なるアルゴリズムのものの結果同士を直接比較しても期待通りとは限りません。例えばデータサイズを動かして処理時間の増加具合を比較するとかならわかりますが、異なるアルゴリズムの処理時間同士を直接比較するというのは統計処理として不適切です。

ちなみに、クイックソートはピボットの選び方で最悪の場合が変わります。qsort関数の実装は存じませんが、ピボットを端とするならば最悪の場合は整列済みの場合です。配列に一要素追加するたびにクイックソートするという実装を見たことがありますが、これはかなり酷い実装です。

さらに余談ですが、計算量といえば時間だけだなくメモリ量の尺度にもなるので、こちらの比較もしてみると面白いですよ。

投稿2018/06/25 17:07

HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

extremetriangle

2018/06/26 02:40 編集

丁寧なご回答ありがとうございます。 ランダウの記号が何を意味しているか、理解が甘かったと実感しました。 クイックソートは確かに最悪時にO(n^2)ですが、最良時や平均時はO(nlogn)の振る舞いをすると聞いていたので、安直に記述してしまいました。配列を大きくして同じアルゴリズムの処理時間を比較する時などの指標で使うのですか、大変参考になります。 クイックソートはピボットで区切られたある程度小さな部分配列には、ヒープソートや挿入ソートを適用する事があるらしいですね。 また、整列済みの配列に一要素追加するだけなら、挿入ソートが適切でしょうか。 消費メモリの大きさも大事ですね、是非やってみたいと思います。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問