読者です 読者をやめる 読者になる 読者になる

クイックソート

ソース

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<random>
#include<ctime>
#include<algorithm>
using namespace std;

void outputVector(vector<int> x){
	cout<<"[ ";
	if(x.size()>0){
		cout<<x[0];
	}
	for(int i=1;i<x.size();i++){
		cout<<" , "<<x[i];
	}
	cout<<" ]"<<endl;
}

vector<int> quick_sort(vector<int> x){
	if(x.size()<=1)
		return x;
	vector<int> ret;
	int p=x[0];
	vector<int> left,right;
	for(int i=1;i<x.size();i++){
		if(p>x[i]){
			left.push_back(x[i]);
		}else{
			right.push_back(x[i]);
		}
	}
	ret=quick_sort(left);
	ret.push_back(p);
	vector<int> ok=quick_sort(right);
	for(int i=0;i<ok.size();i++){
		ret.push_back(ok[i]);
	}
	return ret;
}

vector<int> quick_sort2(vector<int> x){
	vector<int> ret(x);
	queue<pair<int,int> > qu;
	qu.push(make_pair(0,ret.size()));
	while(!qu.empty()){
		pair<int,int> pa=qu.front();qu.pop();
		int povit=ret[pa.first];
		int i=pa.first+1,j=pa.second-1;
		while(i<j){
			for(;i<pa.second;i++){
				if(povit<=ret[i]){
					break;
				}
			}
			for(;j>pa.first;j--){
				if(povit>ret[j]){
					break;
				}
			}
			if(i<j){
				int tmp=ret[i];
				ret[i]=ret[j];
				ret[j]=tmp;
			}
		}
		if(povit>ret[pa.first+1]){
			i=pa.first+1;
			for(;i<pa.second-1;i++){
				if(ret[i]<povit && povit<=ret[i+1]){
					break;
				}
			}
			ret[pa.first]=ret[i];
			ret[i]=povit;
		}else{
			i=pa.first;
		}
		if(pa.first+1<i){
			qu.push(make_pair(pa.first,i));
		}
		if(i+2<pa.second){
			qu.push(make_pair(i+1,pa.second));
		}
	}
	return ret;
}


int main(){
	mt19937 engine;
	uniform_int_distribution<int> distribution( 1, 1000000 ) ;
        
	vector<int> x;
	for(int i=0;i<1000000;i++){
		x.push_back(distribution(engine));
	}
	
	clock_t start,end;
	
	//outputVector(x);
	
	start=clock();
	vector<int> s1=quick_sort(x);
	end=clock();
	//outputVector(s1);
	cout<<"time: "<<((double)(end-start)/CLOCKS_PER_SEC)<<endl;
	
	start=clock();
	vector<int> s2=quick_sort2(x);
	end=clock();
	//outputVector(s2);
	cout<<"time: "<<((double)(end-start)/CLOCKS_PER_SEC)<<endl;

	start=clock();
	sort(x.begin(),x.end());
	end=clock();
	//outputVector(s2);
	cout<<"time: "<<((double)(end-start)/CLOCKS_PER_SEC)<<endl;
	
	for(int i=0;i<s1.size();i++){
		if(s1[i]!=s2[i]){
			cout<<i<<": error s1:"<<s1[i]<<" s2:"<<s2[i]<<endl;
		}
	}
}

出力

time: 3.32
time: 0.59
time: 0.45

quick_sortみたいな再帰タイプのクイックソートをみて、再帰毎にvector生成してておせーんじゃなかと思い、quick_sort2はクイックソート - Wikipediaを参考に作成
案の定、再帰タイプの方が遅い
コード、アルゴリズム的には再帰タイプの方が全然綺麗だけど、こういう遅いコードって気になる

実行する場合はランダム生成にC++0xつかってるので必要

g++ -std=c++0x c.cpp