c - qsort はどのソートアルゴリズムを使用しますか?

Question

qsortC関数が使用するソートアルゴリズムに関する情報が見つかりません。

クイックソートですか？男には言われません。

Answer 1

の実装qsortは指定されていません。実装では、任意のソート アルゴリズムを使用できます。興味深いことに、並べ替えは安定している必要はなく、複雑さの要件もありません。

(C11 §7.22.5.2)の仕様全体qsortは次のとおりです。

qsort機能_

あらすじ

#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
     int (*compar)(const void *, const void *));

説明

このqsort関数は、オブジェクトの配列をソートしnmembます。その最初の要素は によってポイントされbaseます。各オブジェクトのサイズは で指定されsizeます。

配列の内容は、compar が指す比較関数に従って昇順にソートされます。この比較関数は、比較対象のオブジェクトを指す 2 つの引数で呼び出されます。最初の引数が 2 番目の引数より小さい、等しい、または大きいと見なされる場合、関数はゼロより小さい、等しい、または大きい整数を返します。

2 つの要素が等しいと比較された場合、結果の並べ替えられた配列での順序は指定されません。

戻り値

qsort関数は値を返しません。

Answer 2

理論的には、qsort は と の戻り値と呼び出し値のポイントまでしか定義されていませqsortんbsort。ISO規格の参考文献はこちらです。

実際には、通常はクイックソートを使用します。

Answer 3

James McNellis の標準の引用を補完するために、GNU の libc ドキュメントが次のように述べていることは注目に値します。

このqsort関数の名前は、もともと「クイック ソート」アルゴリズムを使用して実装されていたことに由来しています。

そして、明らかにマージソートである代替アルゴリズムを使用することにしました。