『STLソース剖析』Sortソート分析

全体的に言えば、sortアルゴリズムはデータ量が大きい場合にQuick Sort(クイックソート)を採用し、セグメント化されたデータ量がある敷居より小さいと、Quick Sortの再帰呼び出しに大きな負担をかけないようにInsertion Sort(挿入ソート)に変更し、再帰階層が深すぎる場合はHeap Sort(スタックソート)に変更し、Quick Sortをそれぞれ簡単に紹介する
Insertion Sort挿入ソート
Insertion sortは2層サイクルの形式で行われ、外サイクルはシーケンス全体を便利にし、反復ごとに1つの自己区間を決定し、内サイクルは自己区間を遍歴し、自己区間内の1つの「逆転対」を逆転させる.「逆転対」とは、任意の2つの反復器i,j,iを指す.

template
void __insertion_sort(RandomAccessIterator first,RandomAccessIterator last){
    if(first==last) return;
    for(RandomAccessIterator i=first+1;i!=last;++i)//   
        __linear_insert(first,i,value_type(first));
        //  [first,i)       
}

template 
inline void__linear_insert(RandomAccessIterator first,Random AccessIterator last,T*){
    T value=*last;//     
    if(value<*first){
    copy_backward(first,last,last+1);//       
    *first=value;
    }
    else//     
    __unguarded_linear_insert(last,value);
}

template
void __unguarded_linear_insert(RandomAccessIterator first,Random AccessIterator last,T value){
    RandomAccessIterator next=last;
    --next;
    //insertion sort    
    //  ，         ，        
    while(value<*next){//     
    *last==*next;
    last=nex;
    --next;
    }
    *last=value;
}

Quick Sortクイックソート
Quick Sortは現在知られている最も速いソート法であり,平均複雑度はO(Nlogn)であり,最悪の場合はO(N)に達する²).しかしIntroSort(median-of-three QuickSortに非常に類似したソートアルゴリズム)は、最悪の場合をO(Nlogn)に進めることができる.初期のSTLsortアルゴリズムはQuickSortを採用し、SGI STLはIntroSortに変更された.median-of-three(3点の中値):いずれの要素もピボットとして送られる(pivot)が、適切かどうかはQuickSortの効率に影響し、「要素が最初に入力されたときにランダムではない」ことを避けるために悪化効果をもたらす最も理想的な最も安定した方法は、シーケンス全体のヘッド、テール、中央の3つの位置の要素を取り、その値をピボットとして、median-of-three partitioning、またはmedian-of-QuickSortとなり、中央の位置の要素を迅速に取り出すためには、反復器が中央の位置の要素を迅速に取り出す必要があることは明らかである.反復器はランダムに読み取ることができる、すなわちRandomAccessIteratorsであることは明らかである.
final insertion sort
sortが採用した最適化案、すなわち、前のすべてのソートステップはQuickSOrtを採用し、最後にinsertionSortを採用したのは、insertionSortが「ほぼソート」のシーケンスに直面したときに、良い表現を持つことができるからである.
Inrtosort(Introspective sorting、内省式ソート)
その行為はほとんどの場合median-of-three Quick Sortと全く同じである(もちろん同じ速さであるが,分割行為が二次行為に悪化する傾向がある場合には自己検出が可能となり,HeapSortに転用して効率をHeapSortのO(Nlogn)に維持し,最初からHeapSortを用いるよりもよい.