qソート

qsort は、ユーザーが提供する比較関数に従って任意のオブジェクトの配列をソートするアルゴリズムを実装するC 標準ライブラリ 関数です。この関数は、もともとUnix C ライブラリで実装するために使用された「quicker sort」アルゴリズム^[1] ( RS Scowen によるクイックソートの変種) にちなんで名付けられましたが、C 標準ではクイックソートの実装を要求していません。^[2]

異なる種類のデータ（多態性）を操作する機能は、3方向比較関数への関数ポインタと、個々の入力オブジェクトのサイズを指定するパラメータを取ることで実現されます。C標準では、比較関数が入力配列内の項目に対して完全な順序付けを実装する必要があります。 ^[3]

qsort関数は、 1972年にUnixバージョン2でライブラリアセンブリ言語サブルーチンとして登場しました。そのインターフェースは、範囲[ start、end )からqsort(void * start, void * end, unsigned length)連続して格納されたlength長のバイト文字列をソートする、という疑似プロトタイプ化ができる点で、現在のバージョンとは異なります。 ^[1]このことと、置き換え可能な比較関数がないこととにより、システムのリトルエンディアン整数やその他のデータ構造を適切にソートするのには適していません。

バージョン3 Unixでは、compar(III)を呼び出すことでインタフェースが拡張され、現在のmemcmpcomparと同じインタフェースを持つようになりました。この関数は、標準のqsortの引数と同等の方法で、ユーザープログラムによってオーバーライドされ、あらゆる種類の順序付けを実装できます（もちろんプログラムグローバルですが）。^[4]

バージョン4 Unixでは、標準と同等のインターフェースを持つC実装が追加されました。^[5] これは1983年にBerkeley Software Distribution用に書き直されました。^{[2]この関数は}ANSI C （1989）で標準化されました。アセンブリ実装はバージョン6 Unixで削除されました。^[6]

1991年、ベル研究所の従業員は、AT&T版とBSD版のqsortが単純な入力に対して2乗の時間がかかることに気づいた。そこで、ジョン・ベントレーとダグラス・マキロイは、より高速で堅牢な新しい実装を開発した。^{[2]マキロイは1998年に、より複雑な2乗時間入力である}AntiQuicksortを開発した。この関数は、敵対的なデータをオンザフライで構築する。^[7]

次の C コードは、qsort を使用して整数のリストをソートする方法を示しています。

#include <stdlib.h> 

/* 比較関数。比較対象の項目への 2 つの汎用 (void) ポインターを受け取ります。 */ 
int compare_ints ( const void * p , const void * q ) { int x = * ( const int * ) p ; int y = * ( const int * ) q ;       
         
         

    
       /*符号付き整数のオーバーフローが原因で
未定義の動作を引き起こす可能性がある return x - y は避けてください。 */ if ( x < y ) return -1 ; // 昇順の場合は -1 を返し、降順の場合は 1 を返します。else if ( x > y ) return 1 ; // 昇順の場合は 1 を返し、降順の場合は -1 を返します。       
          
        
          

    return 0 ; // すべてのロジックは、次のようにも記述されます: return ( x > y ) - ( x < y ); } 
    
           


/* a が指す n 個の整数の配列をソートします。 */ 
void sort_ints ( int * a , size_t n ) { qsort ( a , n , sizeof ( * a ), compare_ints ); }     
       

オリジナルの の比較関数はqsort2 つのポインタしか受け入れないため、追加のパラメータを渡す (たとえば、2 つの値の差を別の値と比較する比較関数を作成する)には、グローバル変数を使用する必要があります。この問題は、BSDおよびGNU Unix 系システムによって、qsort_r比較関数に追加のパラメータを渡すことができる 関数を導入することで解決されました。 の 2 つのバージョンは、引数qsort_rの順序が異なります。C11 Annex K は、GNUqsort_sの と本質的に同一の を定義していますqsort_r。macOSおよびFreeBSD のlibcs​​ には、同じ問題に対する代替ソリューションとして、クロージャに類似したブロックを使用するバリアントである も含まれています。^[8]qsort_b