なんとなくクイックソート

そういえばクイックソートを書いたことがなかった(気がする)。

1. ピボットを選択する。(ここでは要素のまんなかの場所を指定した。)
2. ピボットより大きいものを右、小さいものを左に並べる
3. その大きいもの、小さいものの中で1.を繰り返す

問題は、ある値を境に左右に分ける処理であり、それがqsort関数である。

1. 左端からピボット以上のものを探索する(i_left番目)
2. 右端からピボット以下のものを探索する(i_right番目)
3. i_left < i_rightなら両方とも探索できているため、お互いを入れ替える
4. お互いを入れ替えたら、再び探索を始めるが、2つの値が同じならi_leftとi_rightを進めて再び探索を始める

#include <iostream>

using namespace std;

void dump(int* data, int size) {
	for(int i = 0; i < size; ++i) {
		cout << data[i] << ", ";
	}
	cout << endl;
}

void qsort(int* data, int size) {
	const int i_pivot = size / 2;
	const int pivot = data[i_pivot];

	int i_left = 0, i_right = size - 1;

	if(size <= 1) {
		return;
	}
	else if(size == 2) {
		if(data[0] > data[1]) {
			int temp = data[0];
			data[0] = data[1];
			data[1] = temp;
		}
		return;
	}

	while(true) {
		for(; i_left < i_right; ++i_left) {
			if(data[i_left] >= pivot) {
				break;
			}
		}

		for(; i_right > i_left; --i_right) {
			if(data[i_right] <= pivot) {
				break;
			}
		}

		if(i_left < i_right) {
			int temp = data[i_left];
			if(temp == data[i_right]) {
				++i_left;
				--i_right;
			}
			else {
				data[i_left] = data[i_right];
				data[i_right] = temp;
			}
		}
		else {
			break;
		}
	}

	qsort(data, i_left);
	qsort(&data[i_left], size - i_left);
}

int main() {
	int data[] = { 1, 6, 4, 9, 3, 2, 8, 7, 0 };
	const int size = sizeof(data) / sizeof(int);
	qsort(data, size);
	dump(data, size);

	cin.get();
	return 0;
}

追記

ライブラリを使うところは使って、省略しました。

void qsort(int* data, int size) {
	using std::swap;
	const int pivot = data[size / 2];

	int i_left = 0, i_right = size - 1;

	if(size <= 1) {
		return;
	}
	else if(size == 2) {
		if(data[0] > data[1]) {
			swap(data[0], data[1]);
		}
		return;
	}

	while(true) {
		for(; i_left < i_right; ++i_left) {
			if(data[i_left] >= pivot) {
				break;
			}
		}

		for(; i_right > i_left; --i_right) {
			if(data[i_right] <= pivot) {
				break;
			}
		}

		if(i_left < i_right) {
			swap(data[i_left], data[i_right]);
			++i_left;
			--i_right;
		}
		else {
			break;
		}
	}

	qsort(data, i_left);
	qsort(&data[i_left], size - i_left);
}