160 lines
3.1 KiB
C++
160 lines
3.1 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <cstdlib>
|
|
#include <chrono>
|
|
using namespace std;
|
|
|
|
#define SIZE 5000
|
|
|
|
void benchmark(void(*f)(vector<int>* v), vector<int>* v);
|
|
void sort_shell(vector<int>* v);
|
|
void sort_heap(vector<int>* v);
|
|
void sort_quick_driver(vector<int>* v);
|
|
|
|
int main(){
|
|
ios::sync_with_stdio(false);
|
|
|
|
cout<<"----- Testing sort algorithms -----\n\n\n";
|
|
cout<<"Usage: e[X]it, [C]reate vector, print [V]ector, [R]eset vector, [S]hell sort, [H]eap sort, [Q]uick sort\n\n";
|
|
|
|
srand(time(NULL));
|
|
|
|
vector<int> v;
|
|
vector<int> work;
|
|
|
|
while(true){
|
|
char command;
|
|
cout<<"> ";
|
|
cin>>command;
|
|
|
|
switch(command){
|
|
case 'X':
|
|
case 'x':
|
|
cout<<"Exiting..."<<endl;
|
|
return 0;
|
|
case 'C':
|
|
case 'c':
|
|
cout<<"Initializing vector...\n";
|
|
v.clear();
|
|
for(int i=0; i<SIZE; i++){
|
|
v.push_back(rand()%100000);
|
|
}
|
|
work = v;
|
|
cout<<"Done\n";
|
|
break;
|
|
case 'V':
|
|
case 'v':
|
|
cout<<"The vector:\n";
|
|
for(vector<int>::iterator it = work.begin(); it < work.end(); it++){
|
|
cout<<*it<<" ";
|
|
}
|
|
cout<<"\n";
|
|
break;
|
|
case 'R':
|
|
case 'r':
|
|
cout<<"Reinitializing working copy...\n";
|
|
work = v;
|
|
cout<<"Done\n";
|
|
break;
|
|
case 'S':
|
|
case 's':
|
|
cout<<"# Shell sort\n";
|
|
benchmark(sort_shell, &work);
|
|
break;
|
|
case 'H':
|
|
case 'h':
|
|
cout<<"# Heap sort\n";
|
|
benchmark(sort_heap, &work);
|
|
break;
|
|
case 'Q':
|
|
case 'q':
|
|
cout<<"# Quick sort\n";
|
|
benchmark(sort_quick_driver, &work);
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
void benchmark(void(*f)(vector<int>* v), vector<int>* v){
|
|
auto t1 = chrono::high_resolution_clock::now();
|
|
(*f)(v);
|
|
auto t2 = chrono::high_resolution_clock::now();
|
|
auto duration = chrono::duration_cast<chrono::nanoseconds>(t2 - t1).count();
|
|
cout<<"Execution time: "<<duration<<" ns\n";
|
|
}
|
|
|
|
void sort_shell(vector<int>* v){
|
|
for(int gap = v->size()/2; gap>0; gap/=2){
|
|
for(int i = gap; i < v->size(); i++){
|
|
int temp = v->at(i);
|
|
|
|
int j;
|
|
for(j=i; j >= gap && v->at(j-gap) > temp; j-=gap){
|
|
v->at(j) = v->at(j-gap);
|
|
}
|
|
|
|
v->at(j) = temp;
|
|
}
|
|
}
|
|
}
|
|
|
|
void sort_heap_heapify(vector<int>* v, int n, int i){
|
|
int largest = i;
|
|
int left = 2 * i + 1;
|
|
int right = 2 * i + 2;
|
|
|
|
if(left < n && v->at(left) > v->at(largest)){
|
|
largest = left;
|
|
}
|
|
|
|
if(right < n && v->at(right) > v->at(largest)){
|
|
largest = right;
|
|
}
|
|
|
|
if(largest != i){
|
|
swap(v->at(i), v->at(largest));
|
|
|
|
sort_heap_heapify(v, n, largest);
|
|
}
|
|
}
|
|
void sort_heap(vector<int>* v){
|
|
for(int i = v->size()/2 - 1; i>=0; i--){
|
|
sort_heap_heapify(v, v->size(), i);
|
|
}
|
|
|
|
for(int i = v->size() - 1; i>0; i--){
|
|
swap(v->at(0), v->at(i));
|
|
|
|
sort_heap_heapify(v, i, 0);
|
|
}
|
|
}
|
|
|
|
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);
|
|
}
|