イネマルのプログラミング備忘録

趣味プログラマーのメモ

C++で双方向リストをクイックソート

独自実装のリストクラスをクイックソートする

訳あって、STL(std)のlistを使用しない状況に遭遇
ソートを実装する必要が出たときに、使用した実装を備忘録

注意

stdが使用できる環境では無用な産物のはず

目的

シーケンシャルアクセスなコンテナ
(双方向リストクラス)をクイックソートする

確認用のプログラム

※動作確認は、VC2013

#include <iostream>
#include <random>
#include <list>
#include <functional>

// STLのイテレータが使用できない特殊な状況を想定
// 今回は代用としてstd::listを継承して定義
// 双方向リストを想定
template < typename t_Type >
class MyList : public std::list<t_Type>{
public:
	MyList(){}
	~MyList(){}
public:
	void QuickSort(
		// 本来は、staticなメンバでデフォルトの比較関数を用意する
		std::function<bool(t_Type, t_Type)> _compFunc = [](t_Type l, t_Type r)->bool{
			return l < r;
	}){
		if (size() > 1){
			_QuickSort(begin(), end(), size(), _compFunc);
		}
	}
private:
	// クイックソートの実装
	static void _QuickSort(
		typename MyList<t_Type>::iterator& beginIt,
		typename MyList<t_Type>::iterator& endIt,
		unsigned distance,
		std::function<bool(t_Type, t_Type)>& _compFunc)
	{
		if (distance < 2){
			return;
		}

		auto pivotIt = beginIt;
		t_Type pivot = *pivotIt;
		auto curIt = beginIt;
		auto partitionIt = curIt;
		unsigned leftSize = 0;
		auto rightIt = endIt;

		--rightIt;
		std::swap(*pivotIt, *rightIt);
		while (curIt != rightIt){
			if (_compFunc(*curIt, pivot)){
				std::swap(*curIt, *partitionIt);
				++partitionIt;
				++leftSize;
			}
			++curIt;
		}
		std::swap(*partitionIt, *rightIt);
		rightIt = partitionIt;
		++rightIt;

		_QuickSort(beginIt, partitionIt, leftSize, _compFunc);
		_QuickSort(rightIt, endIt, (distance - leftSize) - 1, _compFunc);
	}
};

int main(){
	using ListType = int;
	std::random_device randFunc;
	MyList<ListType> intList;

	for (int count = 0; count < 10; ++count){
		intList.emplace_back(static_cast<ListType>(randFunc()));
	}

	std::cout << std::endl << "【昇順】" << std::endl;
	intList.QuickSort();
	for (auto it = intList.begin(); it != intList.end(); ++it){
		std::cout << (*it) << std::endl;
	}

	std::cout << std::endl << "【降順】" << std::endl;
	intList.QuickSort([](ListType l, ListType r)->bool{
		return l >= r;
	}); 
	for (auto it = intList.begin(); it != intList.end(); ++it){
		std::cout << (*it) << std::endl;
	}

	rewind(stdin), getchar();
	return 0;
}

あとがき

ランダムアクセス可能なコンテナに対するサンプルはよく見かけますが、
リスト構造のようなシーケンシャルアクセスな実装の場合の対応策です。
イテレータの比較演算が定義されていないと
1対1で書き換えられなかったりするので、
とりあえず双方向リスト構造での実装例を備忘録行き。