quickmd-compressor
クイックソート(quick sort)は、事実上最も高速であると知られ、広く利用されている。

マージソートと同様に、与えられた数列を2つに分割しながら動作する整列アルゴリズム


クイックソート図解


分割の手順
  1. 数列からある要素(ピボット)を選ぶ
  2. ピボット以下の要素からなる部分列とピボット以上から成る部分列に分割する
quick2
①配列hから枢軸(ピボット)として6を選択して分割する
ここで、左端と右端それぞれの要素にカーソルをセットする

②分割を行う際、ピボット以下の要素を配列の先頭、ピボット以下の要素を配列の末尾に移動させる

その際、次のように分割する
  • h[left] >= (ピボット)が成立する要素が見つかるまでleftカーソルを右方向に走査する
  • h[right] <=(ピボット)が成立する要素が見つかるまでrightカーソルを左方向に走査する
この走査により、leftとrightは次のようになる
quick3
上記条件を満たす要素同士h[left]とh[right]を交換するとこのようになった

③再び操作を続けると左右のカーソルが交差する。これで1度目の分割は終了
  • ピボット以下のグループ:h[0]~h[left-1]
  • ピボット以上のグループ:h[right+1]~h[h.length-1]
  • ピボットと一致するグループ:h[right+1]~h[left-1]
同じように再帰的にグループごとに分割を進める
quick4
以下の条件を満たすとき、要素数1のグループとなっていない
  • rightカーソルが先頭より右側に位置する(先頭<right)とき、左グループを分割
  • leftカーソルが末尾より左側に位置する(left<末尾)とき、右グループを分割
要素数1のグループになるまで分割を繰り返す。
以上で整列完了


特徴


  • クイックソートの性能を向上させるには、数列の中央値をピボットとして選択する戦略が有効
(例)数列中の先頭、中央、末尾の3要素の中央値を選択する。

  • 同一キーを持つ要素の順序がソート前後で維持されない
  →不安定なソート

  • 不安定さは分割操作に依存しており、安定な分割を行う実装も可能
  →一般に実行速度が低下

  • マージソートやクイックソートは、再帰呼び出しやオーバーヘッドのため、数列の長さが短い場合には挿入ソートより遅くなることがある

計算量


データ数をNとすると

分割操作の計算量 O(N)

平均計算量 O(NlogN)

分割後の数列の長さが1しか短くならない時、
最大の計算量 O(N^2)


クイックソートプログラム


配列の中身を昇順に並び替える。

【JavaScript】
function q_sort(numbers,left,right)
{
    var pivot,l_hold,r_hold;

    l_hold = left;
    r_hold = right;
    pivot = numbers[left]; //ピボットを決定
    while(left < right)
    {
        while((numbers[right] >= pivot) && (left < right))
        {
            right--;
        }
        if(left != right)
        {
            numbers[left] = numbers[right];
            left++;
        }
        while((numbers[left] <= pivot) && (left < right))
        {
            left++;
        }
        if(left != right)
        {
            numbers[right] = numbers[left];
            right--;
        }
    }
    numbers[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;
    if(left < pivot)
    {
        q_sort(numbers,left,pivot-1);
    }
    if(right > pivot)
    {
        q_sort(numbers,pivot+1,right);
    }
}

//クイックソートの本体
function quickSort(numbers,array_size)
{
    q_sort(numbers,0,array_size-1);
}

//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前:");
for(var i=0;i < h.length;i++)
{
    document.write(h[i]+" ");
}
document.write("<br>");

//クイックソート
quickSort(h,h.length);

document.write("整列後:");
for(var i=0;i < h.length;i++)
{
    document.write(h[i]+" ");
}

【実行結果】
整列前:6 3 8 4 5 1 2 9 7 0
整列後:0 1 2 3 4 5 6 7 8 9


その他ソート

  1. 選択ソート
  2. バブルソート
  3. 挿入ソート
  4. マージソート
  5. シェルソート
  6. ヒープソート
  7. クイックソート