Created
November 17, 2015 01:02
-
-
Save renyuntao/bff19880b2b5276bed3c to your computer and use it in GitHub Desktop.
Quick Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<ctime> | |
#include<random> | |
using std::cout; | |
using std::cin; | |
using std::endl; | |
int partition(int arr[],int low,int high) | |
{ | |
int i = low + 1; | |
int j = high; | |
int tmp = arr[low]; | |
while(1) | |
{ | |
while(j != low && arr[j] > tmp) --j; //from right to left | |
while(i != high && arr[i] <= tmp) ++i; //from left to right | |
if(i < j) | |
{ | |
int t = arr[j]; | |
arr[j] = arr[i]; | |
arr[i] = t; | |
} | |
else | |
break; | |
} | |
return j; | |
} | |
void quicksort(int arr[],int low,int high) | |
{ | |
if(low < high) | |
{ | |
int j = partition(arr,low,high); | |
int t = arr[j]; | |
arr[j] = arr[low]; | |
arr[low] = t; | |
if(low < j) | |
quicksort(arr,low,j-1); | |
if(high > j) | |
quicksort(arr,j+1,high); | |
} | |
} | |
void generateRandData(int *randArr,int size,int seed) | |
{ | |
std::uniform_int_distribution<unsigned> u(0,1000); | |
std::default_random_engine e(seed); | |
for(int i = 0; i < size; ++i) | |
randArr[i] = u(e); | |
} | |
int main() | |
{ | |
int *arr = new int[1000000]; | |
int seed; | |
cout<<"Input seed:"; | |
cin>>seed; | |
generateRandData(arr,1000000,seed); | |
//std::default_random_engine e(seed); | |
//std::uniform_int_distribution<unsigned> u(0,10000); | |
//for(int i = 0;i < 999999;++i) | |
// arr[i] = u(e); | |
clock_t start = clock(); | |
quicksort(arr,0,999999); | |
clock_t end = clock(); | |
cout<<"time:"<<static_cast<float>(end-start)/CLOCKS_PER_SEC<<endl; | |
delete [] arr; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment