クイックソート(quick sort)は、事実上最も高速であると知られ、広く利用されている。
マージソートと同様に、与えられた数列を2つに分割しながら動作する整列アルゴリズム
1 》クイックソート図解
分割の手順
- 数列からある要素(ピボット)を選ぶ
- ピボット以下の要素からなる部分列とピボット以上から成る部分列に分割する
ここで、左端と右端それぞれの要素にカーソルをセットする
②分割を行う際、ピボット以下の要素を配列の先頭、ピボット以下の要素を配列の末尾に移動させる
その際、次のように分割する
- h[left] >= (ピボット)が成立する要素が見つかるまでleftカーソルを右方向に走査する
- h[right] <=(ピボット)が成立する要素が見つかるまでrightカーソルを左方向に走査する
上記条件を満たす要素同士h[left]とh[right]を交換するとこのようになった
③再び操作を続けると左右のカーソルが交差する。これで1度目の分割は終了
- ピボット以下のグループ:h[0]~h[left-1]
- ピボット以上のグループ:h[right+1]~h[h.length-1]
- ピボットと一致するグループ:h[right+1]~h[left-1]
以下の条件を満たすとき、要素数1のグループとなっていない
- rightカーソルが先頭より右側に位置する(先頭<right)とき、左グループを分割
- leftカーソルが末尾より左側に位置する(left<末尾)とき、右グループを分割
以上で整列完了
特徴
- クイックソートの性能を向上させるには、数列の中央値をピボットとして選択する戦略が有効
- 同一キーを持つ要素の順序がソート前後で維持されない
- 不安定さは分割操作に依存しており、安定な分割を行う実装も可能
- マージソートやクイックソートは、再帰呼び出しやオーバーヘッドのため、数列の長さが短い場合には挿入ソートより遅くなることがある
計算量
データ数をNとすると
分割操作の計算量 O(N)
平均計算量 O(NlogN)
分割後の数列の長さが1しか短くならない時、
最大の計算量 O(N^2)
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
コメント
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。