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); } };