104 lines
2.1 KiB
C++
104 lines
2.1 KiB
C++
|
#include <iostream>
|
||
|
#include <vector>
|
||
|
#include <chrono>
|
||
|
#include <random>
|
||
|
#include <ctime>
|
||
|
#include <algorithm>
|
||
|
using namespace std;
|
||
|
|
||
|
int generatorf() {
|
||
|
return rand() % 10000 + 1;
|
||
|
}
|
||
|
|
||
|
void benchmark(void(*f)(vector<int>* v), vector<int>* v);
|
||
|
|
||
|
void sort_bubble(vector<int>* v);
|
||
|
void sort_quick_driver(vector<int>* v);
|
||
|
|
||
|
void sort_quick(vector<int>* v, int low, int high);
|
||
|
int sort_quick_partition(vector<int>* v, int low, int high);
|
||
|
|
||
|
int main() {
|
||
|
ios::sync_with_stdio(false);
|
||
|
|
||
|
srand(time(0));
|
||
|
|
||
|
vector<int> v(1000);
|
||
|
generate(v.begin(), v.end(), generatorf);
|
||
|
|
||
|
cout<<"The initial vector:\n";
|
||
|
for(vector<int>::iterator it = v.begin(); it < v.end(); it++) {
|
||
|
cout<<*it<<" ";
|
||
|
}
|
||
|
cout<<"\n\n\n";
|
||
|
|
||
|
vector<int> work;
|
||
|
|
||
|
// quick sort
|
||
|
work = v;
|
||
|
cout<<"--- Quick sort\n";
|
||
|
benchmark(sort_quick_driver, &work);
|
||
|
|
||
|
// bubble sort
|
||
|
work = v;
|
||
|
cout<<"--- Bubble sort\n";
|
||
|
benchmark(sort_bubble, &work);
|
||
|
|
||
|
cout.flush();
|
||
|
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
|
||
|
void benchmark(void(*f)(vector<int>* v), vector<int>* v) {
|
||
|
chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
|
||
|
(*f)(v);
|
||
|
chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
|
||
|
int duration = chrono::duration_cast<chrono::microseconds>(t2-t1).count();
|
||
|
cout<<"Execution time: "<<duration<<" us\n";
|
||
|
}
|
||
|
|
||
|
void sort_bubble(vector<int>* v) {
|
||
|
bool done = false;
|
||
|
while(!done) {
|
||
|
done = true;
|
||
|
for(vector<int>::iterator it = v->begin(); it < v->end() - 1; it++){
|
||
|
if(*it > *(it+1)){
|
||
|
done = false;
|
||
|
int tmp = *it;
|
||
|
*it = *(it+1);
|
||
|
*(it+1) = tmp;
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
int sort_quick_partition(vector<int>* v, int low, int high) {
|
||
|
int pivot = v->at(high);
|
||
|
int i = low - 1;
|
||
|
|
||
|
for(int j = low; j <= high - 1; j++) {
|
||
|
if(v->at(j) < pivot) {
|
||
|
i++;
|
||
|
swap(v->at(i), v->at(j));
|
||
|
}
|
||
|
}
|
||
|
swap(v->at(i+1), v->at(high));
|
||
|
|
||
|
return i + 1;
|
||
|
}
|
||
|
|
||
|
void sort_quick(vector<int>* v, int low, int high) {
|
||
|
if(low < high) {
|
||
|
int parti = sort_quick_partition(v, low, high);
|
||
|
|
||
|
sort_quick(v, low, parti - 1);
|
||
|
sort_quick(v, parti + 1, high);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
void sort_quick_driver(vector<int>* v) {
|
||
|
sort_quick(v, 0, v->size() - 1);
|
||
|
}
|