216 lines
4.2 KiB
C++
216 lines
4.2 KiB
C++
|
#include <iostream>
|
||
|
#include <vector>
|
||
|
#include <string>
|
||
|
#include <random>
|
||
|
#include <ctime>
|
||
|
#include <chrono>
|
||
|
using namespace std;
|
||
|
|
||
|
string generateWord() {
|
||
|
const string charset = "abcdefghijklmnopqrstuvwxyz";
|
||
|
int length = rand() % 20 + 1;
|
||
|
string res = "";
|
||
|
for(int i=0; i<length; i++) {
|
||
|
res += charset[rand() % 26];
|
||
|
}
|
||
|
return res;
|
||
|
}
|
||
|
|
||
|
class ListItem {
|
||
|
public:
|
||
|
ListItem(string val) {
|
||
|
this->val = val;
|
||
|
next = NULL;
|
||
|
}
|
||
|
string val;
|
||
|
ListItem* next;
|
||
|
};
|
||
|
|
||
|
class List {
|
||
|
private:
|
||
|
ListItem* first;
|
||
|
int cnt;
|
||
|
public:
|
||
|
List() {
|
||
|
first = NULL;
|
||
|
cnt = 0;
|
||
|
}
|
||
|
ListItem* begin() {
|
||
|
return first;
|
||
|
}
|
||
|
ListItem** beginPtr() {
|
||
|
return &first;
|
||
|
}
|
||
|
void push_back(string val) {
|
||
|
if(first == NULL) {
|
||
|
first = new ListItem(val);
|
||
|
}
|
||
|
else {
|
||
|
ListItem* i = first;
|
||
|
while(i->next != NULL){
|
||
|
i = i->next;
|
||
|
}
|
||
|
i->next = new ListItem(val);
|
||
|
}
|
||
|
cnt++;
|
||
|
}
|
||
|
void clear() {
|
||
|
for(ListItem* i = first; i;) {
|
||
|
ListItem* cur = i;
|
||
|
i = i->next;
|
||
|
delete cur;
|
||
|
}
|
||
|
first = NULL;
|
||
|
cnt = 0;
|
||
|
}
|
||
|
int size() {
|
||
|
return cnt;
|
||
|
}
|
||
|
|
||
|
static ListItem* getLast(ListItem* i) {
|
||
|
while(i->next != NULL){
|
||
|
i = i->next;
|
||
|
}
|
||
|
return i;
|
||
|
}
|
||
|
};
|
||
|
|
||
|
void benchmarkSorts(List* v1, vector<string>* v2, int size);
|
||
|
void sort_quick_driver(vector<string>* v);
|
||
|
void sort_quick_driver(List* v);
|
||
|
|
||
|
int main() {
|
||
|
ios::sync_with_stdio(false);
|
||
|
srand(time(0));
|
||
|
|
||
|
List v1;
|
||
|
vector<string> v2;
|
||
|
|
||
|
benchmarkSorts(&v1, &v2, 10);
|
||
|
benchmarkSorts(&v1, &v2, 1000);
|
||
|
benchmarkSorts(&v1, &v2, 10000);
|
||
|
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
|
||
|
void generateSample(List* v1, vector<string>* v2, int size) {
|
||
|
v1->clear();
|
||
|
v2->clear();
|
||
|
cout<<"----- Sample size: "<<size<<"\n";
|
||
|
for(int i=0; i<size; i++) {
|
||
|
string w = generateWord();
|
||
|
v1->push_back(w);
|
||
|
v2->push_back(w);
|
||
|
}
|
||
|
}
|
||
|
void benchmarkSorts(List* v1, vector<string>* v2, int size) {
|
||
|
generateSample(v1, v2, size);
|
||
|
|
||
|
chrono::high_resolution_clock::time_point v1t1 = chrono::high_resolution_clock::now();
|
||
|
sort_quick_driver(v1);
|
||
|
chrono::high_resolution_clock::time_point v1t2 = chrono::high_resolution_clock::now();
|
||
|
int v1d = chrono::duration_cast<chrono::microseconds>(v1t2 - v1t1).count();
|
||
|
cout<<"Quick sort time for list: "<<v1d<<" us\n";
|
||
|
|
||
|
chrono::high_resolution_clock::time_point v2t1 = chrono::high_resolution_clock::now();
|
||
|
sort_quick_driver(v2);
|
||
|
chrono::high_resolution_clock::time_point v2t2 = chrono::high_resolution_clock::now();
|
||
|
int v2d = chrono::duration_cast<chrono::microseconds>(v2t2 - v2t1).count();
|
||
|
cout<<"Quick sort time for vector: "<<v2d<<" us\n";
|
||
|
|
||
|
cout<<endl;
|
||
|
}
|
||
|
|
||
|
int sort_quick_partition(vector<string>* v, int low, int high) {
|
||
|
string 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<string>* 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<string>* v) {
|
||
|
sort_quick(v, 0, v->size() - 1);
|
||
|
}
|
||
|
|
||
|
ListItem* sort_quick_partition(ListItem* low, ListItem* high, ListItem** newLow, ListItem** newHigh) {
|
||
|
ListItem* pivot = high;
|
||
|
ListItem* prev = NULL;
|
||
|
ListItem* cur = low;
|
||
|
ListItem* tail = pivot;
|
||
|
|
||
|
while(cur != pivot) {
|
||
|
if(cur->val < pivot->val) {
|
||
|
if(*newLow == NULL) {
|
||
|
*newLow = cur;
|
||
|
}
|
||
|
|
||
|
prev = cur;
|
||
|
cur = cur->next;
|
||
|
}
|
||
|
else {
|
||
|
if(prev) {
|
||
|
prev->next = cur->next;
|
||
|
}
|
||
|
ListItem* tmp = cur->next;
|
||
|
cur->next = NULL;
|
||
|
tail->next = cur;
|
||
|
tail = cur;
|
||
|
cur = tmp;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
if(*newLow == NULL) {
|
||
|
*newLow = pivot;
|
||
|
}
|
||
|
|
||
|
*newHigh = tail;
|
||
|
|
||
|
return pivot;
|
||
|
}
|
||
|
ListItem* sort_quick(ListItem* low, ListItem* high) {
|
||
|
if(!low || low == high) {
|
||
|
return low;
|
||
|
}
|
||
|
|
||
|
ListItem* newLow = NULL;
|
||
|
ListItem* newHigh = NULL;
|
||
|
|
||
|
ListItem* pivot = sort_quick_partition(low, high, &newLow, &newHigh);
|
||
|
|
||
|
if(newLow != pivot) {
|
||
|
ListItem* tmp = newLow;
|
||
|
while(tmp->next != pivot) {
|
||
|
tmp = tmp->next;
|
||
|
}
|
||
|
tmp->next = NULL;
|
||
|
|
||
|
newLow = sort_quick(newLow, tmp);
|
||
|
tmp = List::getLast(newLow);
|
||
|
tmp->next = pivot;
|
||
|
}
|
||
|
|
||
|
pivot->next = sort_quick(pivot->next, newHigh);
|
||
|
|
||
|
return newLow;
|
||
|
}
|
||
|
void sort_quick_driver(List* v) {
|
||
|
*v->beginPtr() = sort_quick(v->begin(), List::getLast(v->begin()));
|
||
|
}
|