クイックソート

ホームアルゴリズム入門講座 > クイックソート

クイックソート

クイックソートの基本データ

クイックソートのアルゴリズム

クイックソートはソートアルゴリズムの王様と呼ばれます。仕組みはマージソートで使われる分割統治法を用いていますが、分割するタイミングを変えることで、一般にマージソートよりも高速に処理します。

クイックソートはまず「ピボット」と呼ばれる基準値を設定します。そして数直線を思い浮かべ、ピボットよりも小さい値がピボットより左へ、ピボットより大きい値がピボットの右へ行くように交換していきます。そして、交換が終了したらピボットの左側と右側で分けて、再帰的に繰り返します。

分割していくのは似ていますが、マージソートのようにマージするのではなく、元となるデータを使って全て処理するので、外部領域も不要です。その代わり、同じデータがある場合はそれらの並びは崩れるため、安定ソートではありません。

{
{4,1,3,5,2} をマージソートする
i は左から、y は右から進んで行くとする。

[全体]
1) 3をピボットとし、ソートの範囲は 0 から 4 まで({4,1,3,5,2})
2) iが 4 を、yが 2 をキャッチ。交換する {2,1,3,5,4}
3) iが 3 を、yが 3 をキャッチ。交換する {2,1,3,5,4}
4) i と y が逆転したので、止める 

[最初のピボットの左側]
1) 1をピボットとし、ソートの範囲は 0 から 2 まで({2,1,3})
2) iが 2 を、yが 1 をキャッチ。交換する {1,2,3,5,4}
3) i と y が逆転したので、止める

[最初のピボットの右側]
1) 5をピボットとし、ソートの範囲は 3 から 4 まで({5,4})
2) iが 5 を、yが 4 をキャッチ。交換する {1,2,3,4,5}
3) i と y が逆転したので止める

(プログラム出力)
Before: 4 1 3 5 2 
2 1 3 5 4  : 4 and 2, pivot=3
2 1 3 5 4  : 3 and 3, pivot=3
1 2 3 5 4  : 2 and 1, pivot=1
1 2 3 4 5  : 5 and 4, pivot=5
After: 1 2 3 4 5 

クイックソートは定義自体があいまいです。そのため、ピボットの取り方によっても、また終了を判定する方法によっても厳密にはアルゴリズムの流れが変わります。

しかし、そのような亜種も含めて、「ピボットを基準にして左右に分ける」ソートアルゴリズムをクイックソートといいます。

マージソートの実装

using System;

namespace NewWorld
{
	class MainClass
	{
		private static int count = 0;
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,2,1};
			
			Console.Write("Before: ");
			foreach(int num in data)
				Console.Write(num + " ");
			Console.WriteLine();
			
			QuickSort(data,0,data.Length-1);
			
			Console.Write("After: ");
			foreach(int num in data)
				Console.Write(num + " ");
			
			Console.WriteLine();
			Console.WriteLine("{0} times",count);
		}
		
		public static void QuickSort(int[] basedata, int start, int end)
		{
			int p = basedata[(start + end) / 2];
			int i = start;
			int y = end;
			int m;
			
			while(i < y && (end - start) > 1)
			{
				while(basedata[i] < p) i++;
				while(p < basedata[y]) y--;
				
				m = basedata[i];
				basedata[i] = basedata[y];
				basedata[y] = m;
				
				foreach(int num in basedata)
					Console.Write(num + " ");
				Console.Write(" : {0} and {1}, pivot={2}",basedata[y],basedata[i],p); 
				Console.WriteLine();
				
				if(i < end) i++;
				if(start < y) y--;
				
				count++;
				
			}
			if(start + 1 < i) QuickSort(basedata, start, i - 1);
			if(y < end - 1) QuickSort(basedata, y + 1, end);
		}
	}
}

クイックソートはその機能性の割には簡潔に記述することができます。上のプログラムでは途中経過を表示する機能と繰り返しの回数を計算する機能を含めているので、1.5倍ほどにふくれあがっていますが、クイックソート自体は簡潔です。

しかし、クイックソートのアルゴリズムだけを頼りにコードを記述するのは簡単ではありません。実は、ネット上にあるC言語のプログラムを参考に記述していましたが、そのコードが間違っていてある条件だと無限ループになるというミスが発覚し、パソコンが止まってしまったので、このアルゴリズムは私が0から記述したものです。

みなさんも他人を信用せず、自分でアルゴリズムをコードに変えてみてください。

なお、このプログラムは {1,2,3,5,4} などのほとんどそろっている条件の場合は無駄に交換してしまうことが分かっています。だれか改良してください。

(出力結果)

Before: 6 3 8 5 4 7 9 2 1 
1 3 8 5 4 7 9 2 6  : 6 and 1, pivot=4
1 3 2 5 4 7 9 8 6  : 8 and 2, pivot=4
1 3 2 4 5 7 9 8 6  : 5 and 4, pivot=4
1 2 3 4 5 7 9 8 6  : 3 and 2, pivot=3
1 2 3 4 5 7 6 8 9  : 9 and 6, pivot=9
1 2 3 4 5 6 7 8 9  : 7 and 6, pivot=7
After: 1 2 3 4 5 6 7 8 9 
6 times

出力結果が一番感動的なのはバブルソートです。クイックソートの途中経過には、ブクブクと上がっていく最小値の姿などを発見することはできません。

クイックソートの欠点

クイックソートはもっとも早いソートアルゴリズムですが、欠点もあります。

まずは、安定でないことです。たとえば、{学籍番号, 成績} という2つのデータを持った2次元配列をソートする場合を考えます。現在は学籍番号で並べられていますが、成績で並び替えたとき、成績が同じ生徒は学籍番号が逆になってしまうという特性があります。これを「安定でないソート」と言います。

これまでに紹介したバブルソート・挿入ソート・マージソートはすべて安定です。それは「隣り同士を比較する」からです。もし安定なソートを使いたければ、クイックソート以外を選択しなくてはいけません。

そして、ピボットの選び方によって速度が大きく変わることです。ピボットが「並び替えた後で中央にくるはずの値」であれば最適化されますが、端っこなどの値をとってしまうと、あまり高速ではなくなってしまいます。

さらに、ピボットの取り方が最悪の場合、無限ループに陥るといわれています。私自身、無限ループになってしまったので、条件をいろいろなところに散りばめています。

また、ほとんど整っているデータに対しては挿入ソートやマージソートの方が早いともいわれています。

このように、ソートアルゴリズムの王者といわれるクイックソートにも欠点はあります。ですが、クイックソートよりも早いアルゴリズムが存在するのかどうかも分からない以上、クイックソートはずっと使いつづけられるでしょう。

なお、マージソートやクイックソート(平均)の計算量O(n log n)を越えるソートアルゴリズムはないと証明されているので、いかにピボットをうまくとるか、などの方面から研究するといいかもしれません。