Randomized Quicksort

単純にQuicksortのpivot選択をランダムにしただけ。
これで理論上は、O(nlogn)になります。

/*
 * Rquicksort.h
 *
 *  Created on: 2010/05/22
 */

#include<vector>
#include<cstdlib>
using namespace std;

template<class type> class Rquicksort{
private:
	void swap(vector<type>& nums, int i, int j){
		type tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

public:
	void RQuickSort(vector<type>& nums,int i,int j){

		int pivot = i + (rand() % j);
		swap(nums,pivot,i);
		int k = i+1;
		int l = j;
		while(k<l){
			while(nums[k] < nums[i]){
				k++;
			}
			while(nums[l] >= nums[i]){
				l--;
			}
			swap(nums,k,l);
		}
		swap(nums,k,l);
		swap(nums,i,l);
		if(i>l-1)	RQuickSort(nums,i,l-1);
		if(l+1>j)	RQuickSort(nums,l+1,j);
	}
};