【C++ちゃんは】クイックソートの非再帰版【かわいい】

クイックソートの非再帰版

クイックソートは通常、再帰を使って書かれます。再帰呼び出しはスタック領域を使ってしまいますので、呼び出しがあまりにも深くなるとスタックオーバーフローを出してしまいます。

そのため、再帰呼び出しを使わないで書いてみました。とはいえ、結局スタックを自分で定義して呼び出すだけなので何もアルゴリズムは変わりません。再帰呼び出しをするどんなアルゴリズムも次のような手順で簡単に非再帰版に変わります。

まずはクイックソートを再帰を使って書きます。

#include <algorithm>
#include <vector>
void qsort_normal(std::vector<int>& array, int left, int right) {
	if (left < right) {
		auto i = left;
		auto j = right;
		auto pivot = array[(left + right) / 2];
		
		while (i <= j) {
			while (array[i] < pivot) {
				++i;
			}
			while (array[j] > pivot) {
				--j;
			}
			if (i <= j) {
				std::swap(array[i], array[j]);
				++i;
				--i;
			}
		}
		qsort_normal(array, left, j);
		qsort_normal(array, i, right);
	}
}

では自分でスタックを用意しましょう。とはいえ、スタックはすでに標準ライブラリにありますからそちらを使えばいいでしょう。

置き換えるのは簡単です。

1. まずは関数の引数の初期値をスタックにプッシュします。
2. 次に再帰版の関数全体をwhile(スタックが残っている場合) { 処理全体 }とします。
3. そして、再帰呼び出し部分をそのまま、その引数をスタックにプッシュする処理に置き換えます。

以上です。簡単ですね。それでは実際のコードを見てみましょう。

void qsort_stack(std::vector<int>& array) {
	struct stack_data {
		size_t left;
		size_t right;
	};
	
	std::stack<stack_data> stack;
	stack.push({ 0, array.size() - 1 });
	
	while (!stack.empty()) {
		auto top = stack.top();
		auto left = top.left;
		auto right = top.right;
		stack.pop();
		
		if (left < right) {
			auto i = left;
			auto j = right;
			auto pivot = array[(left + right) / 2];

			while (i <= j) {
				while (array[i] < pivot) {
					++i;
				}
				while (array[j] > pivot) {
					--j;
				}
				if (i <= j) {
					std::swap(array[i], array[j]);
					++i;
					--j;
				}
			}
			stack.push({ left, j });
			stack.push({ i, right });
		}
	}
}

実はこの処理のままだと遅くなります。ここでちょっとだけ最適化を考えます。ポップしてすぐif文を実行してはじかれてしまったらプッシュした意味がなくなります。そこで、pushする前にif文で判定するのです。

また、C++の言語の問題ですが、std::stackは標準で内部のデータ構造にstd::dequeを用います。dequeは両端キューと呼ばれるものですが、先頭への追加を考えるとvectorよりも速いです。ところが、stackは末尾に追加したり末尾から取ってくるデータ構造ですから、そもそも先頭に挿入することがありません。従って、このデータ構造ではなくstd::vectorを用いると速くなります。(なぜdequeなのかは知りません!)

もろもろ改善したコードは次の通りです。

void qsort_stack(std::vector<int>& array) {
	struct stack_data {
		size_t left;
		size_t right;
	};

	std::stack<stack_data, std::vector<stack_data>> stack;
	stack.push({ 0, array.size() - 1 });

	while (!stack.empty()) {
		auto top = stack.top();
		auto left = top.left;
		auto right = top.right;
		stack.pop();
		
		auto i = left;
		auto j = right;
		auto pivot = array[(left + right) / 2];
		while (i <= j) {
			while (array[i] < pivot) {
				++i;
			}
			while (array[j] > pivot) {
				--j;
			}
			if (i <= j) {
				std::swap(array[i], array[j]);
				++i;
				--j;
			}
		}
		
		if (left < j) {
			stack.push({ left, j });
		}
		if (i < right) {
			stack.push({ i, right });
		}
	}
}

次のコードで計測してみました。WindowsTimerクラスは自作の計測クラスで、内部でWin32APIのQueryPerformanceCounterを使っています。

#include <cstdio>
#include <random>
int main() {
	WindowsTimer wt;

	std::vector<int> v;
	std::random_device rd;
	std::mt19937_64 mt(rd());
	std::uniform_int_distribution<unsigned int> uid(0, 10000);

	for (int i = 0; i < 1000000; ++i) {
		v.push_back(uid(mt));
	}
	std::vector<int> v2 = v;

	wt.start();
	qsort_normal(v, 0, v.size() - 1);
	wt.stop();

	printf("normal %f [s]\n", wt.get());

	wt.start();
	qsort_stack(v2);
	wt.stop();
	
	printf("stack %f [s]\n", wt.get());

	system("pause");
	return 0;
}

結果はどちらも同じくらいになりました。めでたしめでたし。、

normal 0.066744 [s]
stack 0.064659 [s]