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

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

ただいまの
回答率

90.52%

  • C

    3683questions

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

  • アルゴリズム

    408questions

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

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 343

 質問内容

下記のC言語で書いたコードを使って、3つのソートアルゴリズム間の速度を比較してみました。
(出力結果に表示される処理時間は精密なものではないかもしれませんが)

結果
1位:選択ソート
2位:C言語標準ライブラリのqsort()
3位:バブルソート

qsortが最速、選択ソートとバブルソートが同じくらい遅いと予想していました。
しかし、何度試しても選択ソートが最速だったのです。
このqsortの中身がクイックソートでもマージソートでも、速度はO(nlogn)だと思っていたので意外でした。

理由はどこにあるのでしょうか?
よろしくお願いします。

 該当のソースコード

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define FUNC_NAME(x) (#x)

void sort_counter(void (*sort)(int*, size_t), int* array, size_t length, const char* mes);
void bubble_sort(int* array, size_t length);
void select_sort(int* array, size_t length);
void quick_sort(int* array, size_t length);
int numcmp(const void* lhv, const void* rhv);

int main()
{

    const int Array_length = 100000;
    const int Sort_algorithms = 3;

    int* random_array;
    int* copy_array[Sort_algorithms];

    random_array = (int*)malloc(sizeof(int) * Array_length);
    for(int i = 0; i < Sort_algorithms; i++) {
        copy_array[i] = (int*)malloc(sizeof(int) * Array_length);
    }

    srand(time(NULL));
    for(int i = 0; i < Array_length; i++) {

        random_array[i] = rand();
        for(int j = 0; j < Sort_algorithms ; j++) {
            copy_array[j][i] = random_array[i];
        }
    }

    //***実際に比較を実行する関数***
    sort_counter(bubble_sort, copy_array[0], Array_length, FUNC_NAME(bubble_sort));
    sort_counter(select_sort, copy_array[1], Array_length, FUNC_NAME(select_sort));
    sort_counter(quick_sort, copy_array[2], Array_length, FUNC_NAME(quick_sort));
    //*****************************

    free(random_array);
    for(int i = 0; i < Sort_algorithms; i++) {
        free(copy_array[i]);
    }

    return 0;
}

void sort_counter(void (*sort)(int*, size_t), int* array, size_t length, const char* mes) {

    time_t start_time = time(NULL);

    puts(mes);
    sort(array, length);

    printf("経過時間: %.0lf秒\n\n", difftime(time(NULL), start_time));
}

void bubble_sort(int* array, size_t length) {

    int temp = 0;
    for(int i = 0; i < length -1; i++) {
        for(int j = length - 1; j > i; j--) {
            if(array[i] > array[j]) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

void select_sort(int* array, size_t length) {

    int temp = 0, index = 0;
    for(int i = 0; i < 10; i++) {
        index = i;

        for(int j = i + 1; j < length; j++) {
            if(array[index] >= array[j]) {
                index = j;
            }
        }

        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
}

void quick_sort(int* array, size_t length) {

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

int numcmp(const void* lhv, const void* rhv) {

    return *(int*)lhv - *(int*)rhv;
}

 実行環境

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • segavvy

    2018/06/26 00:53

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

    キャンセル

  • extremetriangle

    2018/06/26 01:01

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

    キャンセル

  • extremetriangle

    2018/06/26 01:13

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

    キャンセル

回答 3

checkベストアンサー

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/26 01:23

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

    キャンセル

  • 2018/06/26 01:26

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

    キャンセル

0

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

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

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


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/26 01:10

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

    キャンセル

0

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/26 11:40 編集

    丁寧なご回答ありがとうございます。

    ランダウの記号が何を意味しているか、理解が甘かったと実感しました。
    クイックソートは確かに最悪時にO(n^2)ですが、最良時や平均時はO(nlogn)の振る舞いをすると聞いていたので、安直に記述してしまいました。配列を大きくして同じアルゴリズムの処理時間を比較する時などの指標で使うのですか、大変参考になります。

    クイックソートはピボットで区切られたある程度小さな部分配列には、ヒープソートや挿入ソートを適用する事があるらしいですね。
    また、整列済みの配列に一要素追加するだけなら、挿入ソートが適切でしょうか。

    消費メモリの大きさも大事ですね、是非やってみたいと思います。

    キャンセル

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

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    特定の配列のみシャッフルする方法を教えてほしいです。

    こんにちは 私は現在カードゲームを作成しています。 作成したいゲームの基本的な処理は作成できたのですが一か所どうすれば実現できるのかわからない処理があり困っています。 【ルー

  • 解決済

    配列の要素間の和を全パターン求めるプログラムを作成したい。

    皆様ありがとうございました。 前提・実現したいこと <CもしくはC++> 配列の要素間の和を全パターン求めるプログラムを作成したい。 【例】 /*-------------

  • 解決済

    バブルソートについて

    10個の整数を入力して、それを昇順に並べるプログラムを自分なりに作ってみたのですが、データを入力してもソートされず入力したデータそのものが返ってきてしまい、うまく機能しません。どの

  • 受付中

    プログラムを見やすく改良したい

    正常に動くプルグラムを見やすく改良したい。 具体的に教えていただければありがたいです。セグメンテーションフォルトでベスト7まで表示して停止します。173行あたりだと思うのですが、よ

  • 解決済

    2次元配列の値を関数の引数として渡したい

    タイトルの通り2次元配列で作ったものを関数の引数として渡したいです。また、2次元配列の大きさは固定ではありません。 私が書いたコードは、以下のようになります。 #inclu

  • 解決済

    実行時間の表示がおかしい

    ラックナンバーリサーチの時間が過去の履歴は正常に表示されますが、 短い順に並べるところの年と月が2017年が3917年、10月が9月と表示され、そのほかの 時間は正常です。コードの

  • 解決済

    【vector】vector.erase()を高速化したい

     解決済みですが、まだまだこんなのあるよ!という方のコメントを随時募集してます! 前提・実現したいこと タイトルの通り、C++のSTLコンテナの一つvectorクラスの"vecto

  • 解決済

    c言語 入門レベル問題 配列の数字を並び替え

    配列要素1,2,3,4,5 を5,4,3,2,1に出せたいですが、何故か5,4,4,4,4になってしまいましたか? #define N 5 //配列の要素数 int main

同じタグがついた質問を見る

  • C

    3683questions

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

  • アルゴリズム

    408questions

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