クイックソート

クイックソートは対象となる配列を分割していきながら整列を行います。

ポイントとしては、

• 基準をもとに分割をしてくこと

• それが再帰的であること

手順

1. 基準値を決定
2. 基準値より小さな要素と大きな要素をそれぞれ分割する
3. 分割してできた２つの配列に対し1.の操作を配列の長さが１になるまで繰り返す

基本はこの順番な気がしますが、基準値の選び方は様々で、配列の一番右側を基準としたり真ん中を基準としたりするなどがあった気がします。

また、小さな要素と大きな要素の選別も両サイドから探し始めて要素を入れ替えていくパターンと、新たな配列を用意してそこに移していくパターンもあります。前者の方法をする場合、再帰処理の前に基準値を配列の真ん中に持ってくること、再帰の際に配列を参照渡ししその小さい要素の開始点と終了点を引数に渡してあげることで実現します。

正直なところ、ソートをコーディングする際の条件式の書き方によって多少やり方も変わりますが、基本的にやっていることは変わらないと思います。以下、疑似コード。両サイドから入れ替えていくパターンです。

function qsort(Data, left, right)                 //Dataは参照渡しでleftとrightは整列する配列の両端
    int pivot, lp, rp
    pivot = Data[right]                                //基準を右端にとる
    lp = left
    rp = right
    while(lpがrpに等しくない)                   //このwhileで基準より小を左側に基準以上を右に写す
        while(Data[lp]がpivotより小さい)
            lp++
        endwhile
        while(lpがrpより小さい & Data[rp-1]がpivot以上)
            rp--
        endwhile
        if(lpがrpより小さい)
            Dataのlpとrp-1要素を入れ替え
        endif
    endwhile                                     //ここまでで大小が左右に別れる

    Dataのlpとright要素を入れ替え     //基準を真ん中に持ってくる
    if(lp-1がleftより小さい)                //次に整列させる配列の要素が1個なら終了
        qsort(Data, left, lp-1)
    endif
    if(rp+1がrightより小さい)            //次に整列させる配列の要素が1個なら終了
        qsort(Data, rp+1, right)
    endif
endfunction