クイックソート
クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO(nlog n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n2)である。また数々の変種がある。 安定ソートではない。
pivot(基準とする値)を選択し、
pivotより左にあるデータでpivotより大きいものはpivotの右側にある要素とシャッフルし
pivotより右にあるデータでpivotより小さいものはpivotの左側にある要素とシャッフルをする。
これによりpivotの位置は確定し、pivotより左と右にある要素について、それぞれ同じ処理を繰り返していく。
※pivotの値が中央の値に近ければ近いほど高率よくソートできるため
サンプルコードでは、先頭の要素と末尾の要素と中央の要素をとりだし、2番目に大きい値をpivotに採用しています。
例)
6,3,7,5,2,4,1
先頭(6)と末尾(1)と中央(5)を比較し、5をpivotとする。
6,3,7,[5],2,4,1
pivotより左側で5以上値を探す(6)
pivotより右側で5以下値を探す(1)
入れ替える
1,3,7,[5],2,4,6
同様に5以上の値を探す(7)
同様に5以下の値を探す(4)
入れ替える
1,3,4[5],2,7,6
同様に5以上の値を探す(5)
同様に5以下の値を探す(2)
入れ替える
1,3,4,2,[5],7,6
5が確定
↓
|1,3,4,2|[5]|7,6|
pivotの左右に対し同じ処理を繰り返す
↓
1,3,4,2
先頭(1)と末尾(2)と中央(3)を比較し、2をpivotとする。
1,3,4,[2]
pivotより左側で2以上値を探す(3)
pivotより右側で2以下値を探す(2)
入れ替える
1,[2],4,3
↓
|1|[2]|4,3|
↓
１は、これ以上ソートは不要
[1,2]|4,3|
↓
4,3
先頭(4)と末尾(3)と中央(4)を比較し、3をpivotとする。
4,[3]
pivotより左側で2以上値を探す(4)
pivotより右側で2以下値を探す(3)
入れ替える
3,4
[1,2,3,4,5]|7,6|
↓
7,6
先頭(7)と末尾(6)と中央(7)を比較し、6をpivotとする。
7,[6]
pivotより左側で2以上値を探す(7)
pivotより右側で2以下値を探す(6)
入れ替える
[6,7]
↓
1,2,3,4,5,6,7
サンプルコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Markup;
namespace SampleCode
{
class Program
{
static void Main(string[] args)
{
// 20までの数字を生成しシャッフルする
var data = Program.GenerateData(7);
// Sort前
Console.WriteLine(string.Join(',', data));
// Mergeソート
Program.QuickSort(data, 0, data.Count -1);
// Sort後
Console.WriteLine(string.Join(',', data));
}
static void QuickSort(List<int> data, int left, int right)
{
var l = left;
var r = right;
if(r - l < 1) { return; }
// 3要素から中央の値をpivotとする
var pivot = SelectPivot(data, l, r);
Console.WriteLine("pivot:" + pivot);
while (true)
{
while (data[l] < pivot) { l++; }
while (pivot < data[r]) { r--; }
if (r <= l) { break; }
var temp = data[l];
data[l] = data[r];
data[r] = temp;
l++;
r--;
}
Console.WriteLine(string.Join(',', data));
QuickSort(data, left, l - 1);
QuickSort(data, r + 1, right);
}
static int SelectPivot(List<int> data, int l, int r)
{
int m = (l + r) / 2;
if(data[m] <= data[l] && data[r] <= data[l])
{
return data[m] <= data[r] ? data[r] : data[m];
}
else if(data[l] <= data[m] && data[r] <= data[m])
{
return data[l] <= data[r] ? data[r] : data[l];
}
else
{
return data[l] <= data[m] ? data[m] : data[l];
}
}
/// <summary>
/// 任意の1〜nまでのリストを生成し、Fisher-Yatesシャッフルしたものを返す
/// </summary>
/// <param name="maxNumber"></param>
/// <returns>１〜任意の数字までのシャッフルされたリスト</returns>
static List<int> GenerateData(int maxNumber)
{
// 1未満の場合は空のリストを返す
if (maxNumber < 1) { new List<int>(); }
// 1から任意の数字までのリストを生成
var num = Enumerable.Range(1, maxNumber).ToList<int>();
// シャッフル
Random r = new Random();
for (var i = num.Count() - 1; 0 < i; i--)
{
var rand = r.Next(i);
// 乱数が最大値と同じ時、シャッフル元とシャッフル先が同一となるため何もしない
if (rand == i) { continue; }
var temp = num[i];
num[i] = num[rand];
num[rand] = temp;
}
return num;
}
}
}