整列アルゴリズムを比較する(クイックソート編)

どうも、寝起きではないポテト君です。
冬休み2nd(?)中ですが生活リズムは正常です。

前回は改良挿入法編をしました。

ということで今回は、クイックソートです。

まずはクイックソートの説明をしていきます。
クイックソートは、クイックというぐらいなので大体の場合で他の整列アルゴリズムと比べ高速で整列を行うことができます。
具体的には、ピボットという基準点を選び、それよりも大きいグループと小さいグループに分けます。その分けたグループの中でもピボットを選んで分けるということを繰り返して整列を行います。
例えば{3,4,6,2,1,8,5}は
1. 2をピボットとしてグループ分けをする
{1, 2 ,3,4,6,8,5}
2. 残りのグループ(3,4,6,8,5)でグループ分けをする
{1,2,  3,4,5  ,6,  8}
3. 3,4,5をグループ分けをする
{1,2, 3 ,4 ,5 ,6,8}

ということでこれをC++プログラムにしていきます。
省略部分は交換法編へ

void quick(int array[],int array_size){
    struct func{
        int *array,array_size;
        void sort(int st,int en){
            int sw,pi,pip;
            if(st<en){
                pip=st;
                pi=array[(st+en)/2];
                array[(st+en)/2]=array[st];
                for(int i=st+1;i<=en;i++){
                    if(array[i]<pi){
                        pip++;
                        sw=array[pip];
                        array[pip]=array[i];
                        array[i]=sw;
                    }
                }
  　            array[st]=array[pip];
                array[pip]=pi;
                sort(st,pip-1);
                sort(pip+1,en);
            }
        }
    };
    struct func a;
    a.array=array;
    a.array_size=array_size;
    a.sort(0,a.array_size-1);
}

C++では、関数内にローカル関数を作成することができないので、構造体に関数を作って代用します。
構造体は、色々な型の複数のデータをまとめて管理するためのもので、
struct 構造体名{宣言};
で宣言します。
struct 構造体名 変数名;
でインスタンスを作成し、
変数名.メンバ名
でメンバを扱います。
func構造体内のsort関数がメインの部分です。
(グループが始まるインデックス、グループが終わるインデックス)
を引数に渡します。
piはピボット、pipはピボットのインデックスを表します。
ピボットはpiに保存して置き、ピボットがあった場所にはグループの始まりの場所の値を入れておきます。
pipはグループの始まりのインデックスで初期化をし、最初の要素は飛ばして順に要素を調べてピボットより小さい値であったらpipをインクリメントしてインデックスpipの要素とその要素をスワッピングします。
最初の要素は飛ばしたので最終的にピボットはインデックスpipとその次の要素の間になります。
最初の要素の部分にインデックスpipの要素を代入し、インデックスpipにピボットを代入すればグループ分けが完了します。
そして、分けたグループをそれぞれsort関数に渡して、再帰処理を行います。

これで、クイックソートが完成しました!
次回はヒープソート編です。また次回!