アルゴリズムとデータ構造編【整列】 第6章 クイックソート

先頭へ戻る

この章の概要

この章の概要です。

クイックソート

この章では、クイックソートを取り上げます。

クイックソートは、その名の通り、非常に高速なソートを実現するアルゴリズムです。
具体的には、平均計算量が O(n log n) であり、 対象のデータに事前に何らかの制約を要求しない汎用的なソートアルゴリズムとしては理論上、最高性能となります。
しかし、最悪時の計算量は O(n2) で、これはバブルソート並みに悪い性能です。 最悪の場合は工夫によって、ほぼ避けることができます。 この辺りのことは、後程説明します。

クイックソートの原理は次のようになります。
まず、対象のデータ列の中から、適当な1つの要素を選択します。 これを基準値(ピボット)として、基準値より小さい要素と大きい要素とに分割していきます。
結果、データ列の先頭付近には基準値より小さい値を持った要素が集まり(まだソートはされていません)、 その次に基準値となった要素が来て、さらにその後ろには、基準値より大きい値を持った要素が集まります(こちらもまだソートはされていません)。

例えば、元のデータ列が {7, 2, 9, 6, 4, 3, 8, 1, 5} だとします。 ここで、真ん中にある要素 4 を基準値に選択したとすると、分割を行った結果は次のようになります。 (ここでは基準値の選び方を、真ん中になる要素としていますが、あくまで一例としてそうしているだけです。 実際には選び方にもポイントがあります)。

{2, 3, 1, 4, 7, 9, 6, 8, 5}

次に、基準値より小さい側の集まりと、大きい側の集まりの中のそれぞれで、ここまでと同じ操作を繰り返します。 もし、集まりの中に要素が1個しかない、あるいは0個の場合は、その集まりについては何も行いません。
小さい側は {2, 3, 1} です。 仮に、基準値を真ん中の 3 とすると、結果は次のようになります。

{2, 1, 3, (4, 7, 9, 6, 8, 5)}

() の中の要素は、今は相手にしていない部分を表します。
基準値 3 よりも大きい側は要素がありませんが、小さい側にはまだ2つの要素があるので、こちらは続行します。 基準値は 2 としましょう。

{1, 2, (3, 4, 7, 9, 6, 8, 5)}

基準値より小さい側の要素は1個、大きい側は0個になったので、両方ともこれにて完了です。
話を戻して、{2, 3, 1, 4, 7, 9, 6, 8, 5} のところの大きい側の集まりを処理します。 大きい側の集まりは {7, 9, 6, 8, 5} です。 基準値を、真ん中にある 6 とすると、次のような結果になります。

{(1, 2, 3, 4), 5, 6, 7, 9, 8}

小さい側の要素は1個になったので完了です。 大きい側の集まり {7, 9, 8} は続行しましょう。 今度の基準値は真ん中の 9 です。

{(1, 2, 3, 4, 5, 6), 7, 8, 9}

小さい側は要素が2つあるので続行します。 すでに {7, 8} の順番になっているのでソート済みですが、それは関係ありません。
今度の基準値は 7 です。

{(1, 2, 3, 4, 5, 6), 7, 8, (9)}

ここまでで、すべての要素は1つずつばらばらな状態まで細分化されたはずです。 そして、この状態になると、既に全体としてデータ列はソート済みになっています。

プログラム例

クイックソートの実装方法には、様々な亜種が存在していますが、 ここではまず、先ほど説明した原理通りに素直に実装してみます。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void quick_sort(int* array, size_t size);
static void quick_sort_rec(int* array, int begin, int end);
static int select_pivot(int* array, int begin, int end);
static void print_array(const int* array, size_t size);

int main(void)
{
	int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

	print_array( array, SIZE_OF_ARRAY(array) );
	quick_sort( array, SIZE_OF_ARRAY(array) );
	print_array( array, SIZE_OF_ARRAY(array) );

	return 0;
}

/*
	クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
	/* 配列全体を対象にする */
	quick_sort_rec( array, 0, size - 1 );
}

/*
	クイックソート (再帰部分、昇順)
*/
void quick_sort_rec(int* array, int begin, int end)
{
	int pivot = select_pivot( array, begin, end );
	int i = begin;
	int j = end;

	while( 1 ){
		while( array[i] < pivot ){ ++i; }  /* 基準値以上の値が見つかるまで右方向へ進めていく */
		while( array[j] > pivot ){ --j; }  /* 基準値以下の値が見つかるまで左方向へ進めていく */

		if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
		/* 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
		   基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
		   位置関係を交換する。
		*/
		SWAP( int, array[i], array[j] );
		
		/* 次回に備えて、注目点をずらす */
		i++;
		j--;
	}


	/* 基準値の位置より左側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */
	if( i - begin >= 2 ){
		quick_sort_rec( array, begin, i - 1 );
	}

	/* 基準値の位置より右側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */
	if( end - j >= 2 ){
		quick_sort_rec( array, j + 1, end );
	}
}

/*
	基準値を選ぶ
*/
int select_pivot(int* array, int begin, int end)
{
	return array[(begin + end) / 2];  /* 中央の要素を基準値とする */
}

/*
	配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
	size_t i;

	for( i = 0; i < size; ++i ){
		printf( "%d ", array[i] );
	}
	printf( "\n" );
}

実行結果:

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

クイックソートの実装の中核となっているのは、quick_sort_rec関数ですが、 main関数からは quick_sort関数を呼び出すようにしています。
quick_sort関数は、他のソートアルゴリズムを実装した関数と簡単に取り換えられるようにするために用意したものです。 これまでの章で実装したソートアルゴリズムの関数と同じ引数・戻り値になっています。

quick_sort_rec関数には、ソート対象となる配列と、その範囲を指定しています。 quick_sort関数からは、配列全体をソートするような引数を渡しています。

quick_sort_rec関数の実装を見ていきましょう。
まずは、基準値を決定します。 ここではソート範囲の中央にある要素を基準値としており、変数pivot に格納しています。

while文の内側に入ると、すぐに2つの while文が現れます。 この2つの while文は、 基準値の位置よりも左側(添字が若い方)にあり、基準値よりも大きな値を持った要素の位置と、 基準値の位置よりも右側にあり、基準値よりも小さな値を持った要素の位置とを探しています。 それぞれ、ソート範囲の両端から中央に向かって探します。
ここで発見された2つの要素は、基準値との大小関係が逆になっていますから、 それぞれの位置を交換してやれば、正しい大小関係になります。

2つの while文の条件式は、現在の注目位置にある値と基準値とが同じ値の場合には満たされずにループを抜け出します。 そのため、基準値の位置を通り越して反対側にまで進んでしまうことはありません。 これは、配列の範囲外アクセスのチェックが不要だということでもあります。

ソート範囲の両端から進めてきた2つの添字(i, j) がぶつかり合った時点で、外側の while文を抜け出します。 これで、1回目の大小関係入れ替え処理が完了します。

次は、基準位置の左側の集まりと、右側の集まりに対して同じ処理を繰り返します。 同じ処理を綺麗に実装するためには再帰処理が利用できます。 quick_sort_rec関数の引数が、配列と要素数ではなく、配列と範囲の指定になっている理由がここにあります。 範囲を調整すれば、再帰呼び出しが利用できる訳です。

基準位置の左側の集まり、右側の集まりが、要素数が1個以下の場合には、その部分に対する再帰処理は行いませんから、 処理を繰り返していくうちに、いずれ再帰処理は停止して、クイックソート全体も終了を迎えます。

性能

クイックソートの計算量は、平均的には O(n log n) です。 これは前章のシェルソートの計算量 O(n1.25)~O(n1.5) よりも更に良い性能です。 実際に比較してみましょう。
シェルソートに関しては、コードライブラリの ppps_int_sort を使うようにしています。 実装は解説通りのものになっていると考えて頂いて結構です。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_sort.h"

#define ARRAY_SIZE              100000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void init_array(int* array, size_t size);
static void quick_sort(int* array, size_t size);
static void quick_sort_rec(int* array, int begin, int end);
static int select_pivot(int* array, int begin, int end);

int main(void)
{
	int array[ARRAY_SIZE];
	
	
	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	ppps_shell_sort( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("shell_sort");

	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	quick_sort( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("quick_sort");

	return 0;
}

/*
	配列を初期化
*/
void init_array(int* array, size_t size)
{
	size_t i;

	srand(0);

	for(i = 0; i < size; ++i){
		array[i] = rand() % size;
	}
}

/*
	クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
	/* 配列全体を対象にする */
	quick_sort_rec( array, 0, size - 1 );
}

/*
	クイックソート (再帰部分、昇順)
*/
void quick_sort_rec(int* array, int begin, int end)
{
	int pivot = select_pivot( array, begin, end );
	int i = begin;
	int j = end;

	while( 1 ){
		while( array[i] < pivot ){ ++i; }  /* 基準値以上の値が見つかるまで右方向へ進めていく */
		while( array[j] > pivot ){ --j; }  /* 基準値以下の値が見つかるまで左方向へ進めていく */

		if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
		/* 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
		   基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
		   位置関係を交換する。
		*/
		SWAP( int, array[i], array[j] );
		
		/* 次回に備えて、注目点をずらす */
		i++;
		j--;
	}


	/* 基準値の位置より左側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */
	if( i - begin >= 2 ){
		quick_sort_rec( array, begin, i - 1 );
	}

	/* 基準値の位置より右側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */
	if( end - j >= 2 ){
		quick_sort_rec( array, j + 1, end );
	}
}

/*
	基準値を選ぶ
*/
int select_pivot(int* array, int begin, int end)
{
	return array[(begin + end) / 2];  /* 中央の要素を基準値とする */
}

実行結果:

shell_sort: 0.039000 seconds
quick_sort: 0.022000 seconds

クイックソートの方が高速になりました。

最悪の場合

前の項の実験では、クイックソートは確かに高速なようでした。 しかし、クイックソートの、最悪時の計算量は O(n2) であり、これはバブルソート並みの性能です。 最悪時というのがどのような状況かというと、基準値の位置で分割したとき、 左側または右側にだけ要素が偏ってしまっている場合です
クイックソートが最速の性能を発揮するには、1回の分割ごとに、要素が基準値の位置の左右にちょうど半分ずつ振り分けられる必要があります。 ちょうど半分とまで言わないまでも、それに近いぐらいに左右に振り分けられれば高速さを保てます。 しかし、片側にだけ偏ると、ソート完了までに必要な分割作業の回数が増加してしまいますから、低速になります。

意図的に、クイックソートの性能が最悪になるようなデータ列を作って実験してみます。 先ほどのプログラムの中で、init_array関数を次のように書き換えます。

void init_array(int* array, size_t size)
{
	size_t i;
	
	for(i = 0; i < size / 2; ++i){
		array[i] = i;
	}
	for(i = size / 2; i < size; ++i){
		array[i] = size - i;
	}
}

このデータ列は、左半分は整列済み(昇順)、右半分は真逆(降順)に並んでしまっている状態です。 このようなデータ列だと、基準値の位置の左側には要素がなく、右側だけしか要素が存在しませんから、 1回の分割のたびに、ソート対象範囲は1つずつしか狭まりません。
このデータ列をソートすると、次のような結果が得られました。

実行結果:

shell_sort: 0.011000 seconds
quick_sort: 8.188000 seconds

今度はクイックソートの方が圧倒的に遅くなりました。

この問題は、基準値を選ぶ方法を工夫することで軽減できます。 これについては、後で取り上げます
ただ、それでも軽減ということであって、完全な対策にはなりません。 最良時と最悪時との性能差が許容できない場合は、性能が安定的なシェルソートのようなアルゴリズムを使うことも考えた方がいいでしょう。


もう1つ問題があります。 それは、再帰呼び出しの回数が劇的に増加してしまうため、スタック領域が足りなくなってしまう恐れがあるということです。 実際、この実験のときには、コンパイラの設定を変更してスタックサイズを増やさないと実行を正常に終えることができませんでした。
スタックサイズの問題は、データ列の並び方自体が最悪なケースでないとしても、単純にデータ数が多ければ起こり得ます。 そこで、再帰呼び出しを行わないようにクイックソートを改良する必要があります。 この後、再帰しないクイックソートの実装を取り上げます

基準値の選び方

性能」のところで、データ列の並び方が悪いケースでの性能悪化を示しました。 この問題に対する対策の1つとして、基準値の選び方を工夫することが考えられます。

よくある方法の1つは、データ列から3つの要素を選び出し、そのメジアン(中央値)を基準値とするというものです。 選び出す3つの要素はどれでもいいのですが、データ列の先頭、中央、末尾を使うのが簡単です。
なお、メジアンとは、幾つかの数値を昇順か降順に整列させたときに、真ん中に来る値のことです。 例えば、(2, 6, 3, 7, 8) のメジアンは、昇順に整列すると (2, 3, 6, 7, 8) なので、その真ん中にある 6 になります。 平均値とは違うので注意して下さい(平均なら (2+6+3+7+8)/5 = 5.2 になります)。

3要素のメジアンを使う方法で実装したクイックソートで、性能を調べてみます。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_sort.h"

#define ARRAY_SIZE              100000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void init_array(int* array, size_t size);
static void quick_sort(int* array, size_t size);
static void quick_sort_rec(int* array, int begin, int end);
static int select_pivot(int* array, int begin, int end);
static int median3(int x, int y, int z);

int main(void)
{
	int array[ARRAY_SIZE];
	
	
	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	ppps_shell_sort( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("shell_sort");

	init_array( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_BEGIN(1);
	quick_sort( array, SIZE_OF_ARRAY(array) );
	PPP_CHECK_PERFORM_END("quick_sort");

	return 0;
}

/*
	配列を初期化
*/
void init_array(int* array, size_t size)
{
	size_t i;
	
	for(i = 0; i < size / 2; ++i){
		array[i] = i;
	}
	for(i = size / 2; i < size; ++i){
		array[i] = size - i;
	}
}

/*
	クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
	/* 配列全体を対象にする */
	quick_sort_rec( array, 0, size - 1 );
}

/*
	クイックソート (再帰部分、昇順)
*/
void quick_sort_rec(int* array, int begin, int end)
{
	int pivot = select_pivot( array, begin, end );
	int i = begin;
	int j = end;

	while( 1 ){
		while( array[i] < pivot ){ ++i; }  /* 基準値以上の値が見つかるまで右方向へ進めていく */
		while( array[j] > pivot ){ --j; }  /* 基準値以下の値が見つかるまで左方向へ進めていく */

		if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
		/* 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
		   基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
		   位置関係を交換する。
		*/
		SWAP( int, array[i], array[j] );
		
		/* 次回に備えて、注目点をずらす */
		i++;
		j--;
	}


	/* 基準値の位置より左側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */
	if( i - begin >= 2 ){
		quick_sort_rec( array, begin, i - 1 );
	}

	/* 基準値の位置より右側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */
	if( end - j >= 2 ){
		quick_sort_rec( array, j + 1, end );
	}
}

/*
	基準値を選ぶ
*/
int select_pivot(int* array, int begin, int end)
{
	return median3(array[begin], array[(begin + end) / 2], array[end-1]);  /* 中央値を基準値とする */
}

/*
	3要素の中央値を求める
*/
int median3(int x, int y, int z)
{
	if( x < y ){
		if( y < z ){
			return y;
		}
		else if( z < x ){
			return x;
		}
		return z;
	}
	else{
		if( z < y ){
			return y;
		}
		else if( x < z ){
			return x;
		}
		return z;
	}
}

実行結果:

shell_sort: 0.013000 seconds
quick_sort: 0.033000 seconds

シェルソートには及びませんでしたが、大幅に改善されました(以前は8秒以上掛かっていました)。

このように改善されるのは、「性能」で説明したように、 分割の際に振り分けられる要素数の偏りが軽減されるからです。
最悪のケースでは、ほとんど整列済みか、ほとんど逆順になってしまっているときに分割を行うため、 左右の片側にだけ要素が集まる訳ですが、基準値をメジアンで求めると、整列済み(または逆順)の列の中央辺りで分割が起こることになるので、 うまく2分割できるようになります。

再帰しないクイックソートの実装

再帰による実装は、コードが簡潔になる利点はあるものの、「性能」のところで触れたように、 スタックが足りなくなる恐れがあります。 ソート作業は、大量のデータに対して行うことも多いので、この問題は致命的です。

この問題は、自力でスタックを制御できるようにして、再帰構造を取りやめれば解決できます。 実際に、再帰しない方法で実装したものが、次のプログラムになります。

#include <stdio.h>
#include <math.h>
#include "ppps_int_stack.h"

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void quick_sort(int* array, size_t size);
static void quick_sort_body(int* array, int begin, int end);
static int select_pivot(int* array, int begin, int end);
static void print_array(const int* array, size_t size);

int main(void)
{
	int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

	print_array( array, SIZE_OF_ARRAY(array) );
	quick_sort( array, SIZE_OF_ARRAY(array) );
	print_array( array, SIZE_OF_ARRAY(array) );

	return 0;
}

/*
	クイックソート (昇順)
*/
void quick_sort(int* array, size_t size)
{
	/* 配列全体を対象にする */
	quick_sort_body( array, 0, size - 1 );
}

/*
	クイックソート (本体、昇順)
*/
void quick_sort_body(int* array, int begin, int end)
{
	static const int STACK_SIZE = sizeof(int) * 8 * 2;  /* 必要なスタックサイズ。最後の * 2 は、2つの値をセットで格納するため */
	int pivot, i, j;
	PPPSIntStack stack;
	
	
	stack = ppps_int_stack_create(STACK_SIZE);
	
	ppps_int_stack_push( stack, begin ); /* 範囲の下限をスタックへ積む */
	ppps_int_stack_push( stack, end );   /* 範囲の上限をスタックへ積む */

	/* スタックが空になるまで繰り返す */
	while( !ppps_int_stack_is_empty(stack) ){

		/* 範囲の情報をスタックから取り出す */
		/* スタックは後入れ先出しの構造なので、積んだときとは逆の順序で取り出さなければならない点に注意 */
		end = ppps_int_stack_pop( stack );
		begin = ppps_int_stack_pop( stack );

		while( 1 ){

			/* 範囲が逆転していたら何もすることはない */
			if( begin >= end ){
				break;
			}
			
			pivot = select_pivot( array, begin, end );
			i = begin;
			j = end;

			while( 1 ){
				while( array[i] < pivot ){ ++i; }  /* 基準値以上の値が見つかるまで右方向へ進めていく */
				while( array[j] > pivot ){ --j; }  /* 基準値以下の値が見つかるまで左方向へ進めていく */

				if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
				/* 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
				   基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
				   位置関係を交換する。
				*/
				SWAP( int, array[i], array[j] );
				
				/* 次回に備えて、注目点をずらす */
				i++;
				j--;
			}
		
			/* 左右の配列のうち、要素数が少ない方を先に処理する */
			/* 後で処理する側は、その範囲をスタックへ積んでおく */
			if( i - begin < end - j ){
				/* 左側の配列を次のソート処理の対象にする */
				ppps_int_stack_push( stack, j + 1 );  /* 右側の下限 */
				ppps_int_stack_push( stack, end );    /* 右側の上限 */
				end = i - 1;
			}
			else{
				/* 右側の配列を次のソート処理の対象にする */
				ppps_int_stack_push( stack, begin );  /* 左側の下限 */
				ppps_int_stack_push( stack, i - 1 );  /* 左側の上限 */
				begin = j + 1;
			}
		}
	}

	ppps_int_stack_delete( stack );
}

/*
	基準値を選ぶ
*/
int select_pivot(int* array, int begin, int end)
{
	return array[(begin + end) / 2];  /* 中央の要素を基準値とする */
}

/*
	配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
	size_t i;

	for( i = 0; i < size; ++i ){
		printf( "%d ", array[i] );
	}
	printf( "\n" );
}

実行結果:

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

スタックの実装には、コードライブラリにあるサンプル実装 ppps_int_stack を使用しています。 性能上は自力で実装した方が高速になりますが、ここでは、既にある実装を再利用しています。

まず、ソート対象の範囲情報をスタックへ積みます。 範囲情報は、配列の上限と下限を表す添字のセットになっています。
再帰版の場合なら、再帰呼び出しを行っていたところでは、代わりにスタックから範囲情報を取り出すという処理を行います。 そして、その範囲内に対してソート処理を実行します。 ソート処理自体は再帰版と同じで、基準値を決めて、配列を分割します。

配列を分割した後、要素数が少ない側の部分配列を先に処理させるようにすることがポイントになっています。 このようにすることで、ある瞬間にスタックに積み込まれているデータの個数を少なく抑えることができます。

この方法で実装すると、計算上、データの総数が n個とすれば、 スタックサイズは log2 n 以上の容量があれば足りることが実証されています。
必要なスタックサイズは、まじめに計算してもいいですが、quick_sort関数の引数として渡される範囲情報は int型になっているので、 int型で表現できる上限値を超えるデータ数が指定されることはあり得ません。 そこで、int型のビット数を調べて、その値を使っています(ただし、ここでは範囲情報を、上限の添字と下限の添字の2つセットにしているので、 実際には更に2倍の容量が必要です)。 int型が 64ビットだとしても、たかだか 128要素で済むので、定数で構わないという判断をしています。

まじめに計算するなら、C99 以降であれば log2関数にデータ総数を渡し、(返された値 + 1) * 2 とすればいいでしょう。C99 より以前の規格では log2関数がありませんが、log関数を使って「log((double)n) / log(2.0)」とすれば計算できます。

まとめ

クイックソートは、平均計算量が O(n log n) という、高い性能を誇るアルゴリズムです。 しかし、最悪時の計算量は O(n2) にまで悪化してしまいます。
なお、クイックソートは安定なソートアルゴリズムではありません

以下に列挙したように、性能をできるだけ最適化する方法が幾つか存在しています。

ただし、いずれの方法でも、最悪時に計算量が O(n2) に落ち込むことを完全に避けることはできません。 もし、これを避けなければならないのであれば、そもそもクイックソート自体を諦めて、 ヒープソート(第8章)などの性能が安定的なアルゴリズムを採用した方が良いでしょう。


練習問題

問題① 基準値の選び方の1つに、ランダムでどれかの要素を使うという方法があります。 この方法で実装して、パフォーマンスを測定してみて下さい。

問題② 再帰版と非再帰版とでは、パフォーマンスに差があるでしょうか。測定して下さい。

問題③ クイックソートの性能改善の手段として、ソート対象の要素数が十分小さくなったら(n <10 程度が基準とされます)、 その部分のソートに挿入ソート(第4章)を使うという方法があります。 実装して、パフォーマンスを測定して下さい。


解答ページはこちら

参考リンク

更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2017/5/4 「性能」の項から、 最悪の場合についての記述を「最悪の場合」に分離。 文章も少し修正。

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2013/1/19 性能調査を、コードライブラリのソースを使って行うように変更。

'2012/11/25 新規作成。





前の章へ(第5章 シェルソート(挿入ソートの改良))

次の章へ(第7章 マージソート)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS