クイックソート
クイックソートは以下の手順で行われる。
ピボットの選択:適当な値(ピボット(英語版)という)を境界値として選択する
配列の分割:ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
再帰:分割された区間に対し、再びピボットの選択と分割を行う
ソート終了:分割区間が整列済みなら再帰を打ち切る
配列の分割方法の一例として、以下のようなものが考えられる:
配列要素からピボット P を選ぶ(ピボットの選び方については#最悪計算量の回避で詳述)
配列の先頭(左側)から順に、値が P 以上の要素を探索してその位置 LO を記憶する
配列の終端(右側)から逆順に、値が P 未満の要素を探索してその位置 HI を記憶する
LO, HI について: LO が HI より左にあるなら、LO にある要素と HI にある要素の位置を入れ替え、それぞれ LO, HI の次の要素から手順 2, 3 の探索を再開する そうでない場合(LO が HI より右か同じ位置にあるなら)、HI を境界として配列を分割する
分割後の要素数が一定の閾値を下回ったら挿入ソートのような「少数の要素に対してより効率的なソート」に切り替える、という手法がある。また、配列の分割方法自体にも様々な変種がある(同時に2つのピボットを選択して3分割する Dual-pivot Quicksort など)。