yu00’s blog

プログラミングに関する備忘録です

よくわかるクイックソート解説

ソートのアルゴリズムであるクイックソートについて
できるだけ分かりやすくなるよう心がけて解説していきます.

クイックソートの考え方

クイックソートは次のような処理を行っています

  • 1. バラバラなデータからランダムな数(ピボット)を選択する.

f:id:yu00:20150529172847g:plain
f:id:yu00:20150529172921g:plain

  • 2. 選択した数より大きいグループと小さいグループに分ける

f:id:yu00:20150529172952g:plain

  • 3. 2つのグループそれぞれに対して,1,2の処理を行い,さらに分割する

f:id:yu00:20150529173143g:plain

このように,ランダムな数を選択->大小2グループに分割->
それぞれのグループを更に分割
と,分割を繰り返していくことでソートが完了します.
f:id:yu00:20150529173311g:plain

ソースコード

C言語ソースコード例は次のようになります.

#include <stdio.h>

// data1とdata2を入れ替える
void swap(int *data1, int *data2)
{
	int tmp = *data1;
	*data1 = *data2;
	*data2 = tmp;
}

// ピボットのIDを選ぶ.この関数の中身を変えることで
// クイックソートの性能が変化する.
int choose_pivot_id(int data[], int leftID, int rightID)
{
	return leftID;
}

// data[leftID]~data[rightID]までのデータを
// pivotより大きいグループと小さいグループに分ける
// pivotがある場所のIDを返す
int partition(int data[], int leftID, int rightID, int pivotID)
{
	int pivot = data[pivotID];
	// いったんpivotを右端に保存しておく
	swap(&data[pivotID], &data[rightID]);
	// 左端から見て行き,pivot以下のデータを
	// 左へ移動していく
	int p = leftID;
	int i;
	for(i = leftID; i <= rightID-1; i++){
		if(data[i] <= pivot){
			swap(&data[i], &data[p]);
			p++;
		}
	}
	// pがグループの境界になるので
	// 保存しておいたpivotをpの位置に移動する
	swap(&data[p], &data[rightID]);
	return p;
}

void quick_sort(int data[], int leftID, int rightID)
{
	if(leftID >= rightID) return;
	// ピボットのIDを選ぶ
	int pivotID = choose_pivot_id(data, leftID, rightID);
	// pivotより大きいグループと小さいグループに分ける
	int p = partition(data, leftID, rightID, pivotID);
	// 左側をクイックソート
	quick_sort(data, leftID, p-1);
	// 右側をクイックソート
	quick_sort(data, p+1, rightID);
}

int main(void) {

	int data[] = {3,4,5,1,2};
	int i;

	quick_sort(data, 0, 4);

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

ソースコード解説

partition()

partition()は次のような処理をしています.

まず,ピボットをいったん右端に移動し,保存しておきます.
f:id:yu00:20150529174204g:plain

次にiとpを左端にセットします.
f:id:yu00:20150529174312g:plain

そしてiを動かし左から順に見て行き,ピボット以下のデータを
検索します.
ピボット以下のデータが見つかったらpの位置と入れ替えます.
f:id:yu00:20150529174411g:plain

データ入れ替えたらpの位置を一つ右へ動かします.
f:id:yu00:20150529174614g:plain

ピボット以下のデータを検索->入れ替え->p++を繰り返します.
f:id:yu00:20150529174709g:plain
f:id:yu00:20150529174718g:plain

この処理を繰り返していくことで,最終的に
pの位置を境にして,左はピボット以下,右はピボットより
大きいデータとなります.
f:id:yu00:20150529174844g:plain

最後にpの位置と,保存しておいたピボットを入れ替えます.
f:id:yu00:20150529174942g:plain

これでピボットより左はピボット以下,
ピボットより右はピボットより大きいデータとなります.