Code ...
//
// mergesort
//
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
using namespace std;
string chars = "qwertyuioplkjhgfdsazxcvbnm";
int charsPerString = 8;
int stringsPerVector = 20000;
char randomChar() {
return chars[rand() % chars.size()];
}
string makeRandomString() {
string s;
for (int i=0; i<charsPerString; i++) {
s = s + randomChar();
}
return s;
}
vector<string> makeRandomStrings() {
vector<string> vs;
for (int i=0; i<stringsPerVector; i++) {
vs.push_back(makeRandomString());
}
return vs;
}
void printVector (vector<string> &vs) {
for (int i=0; i<vs.size(); i++) {
cout << vs[i] << endl;
}
cout << endl;
}
void bubblesort (vector<string> &vs) {
for (int i=0; i<vs.size()-1; i++) {
for (int j=0; j<vs.size()-i-1; j++) {
if (vs[j] > vs[j+1]) {
string swapper = vs[j];
vs[j] = vs[j+1];
vs[j+1] = swapper;
}
}
}
}
vector<string> merge (vector<string> &a, vector<string> &b) {
// create a new deck
vector<string> result (a.size() + b.size());
// i -> first deck (a)
// j -> second deck (b)
int i = 0;
int j = 0;
// k -> result deck
for (int k=0; k<result.size(); k++) {
// finished with a and b?
if (i >= a.size() && j >= b.size()) {
break;
}
// finished with a?
else if (i >= a.size()) {
result[k] = b[j++];
}
// finished with b?
else if (j >= b.size()) {
result[k] = a[i++];
}
// compare
else if (a[i] < b[j]) {
result[k] = a[i++];
}
else {
result[k] = b[j++];
}
}
return result;
}
vector<string> partial (vector<string> &vs, long start, long end) {
vector<string> result (end-start+1);
for (int i=0; i<result.size(); i++) {
result[i] = vs[start+i];
}
return result;
}
vector<string> mergeSort(vector<string> &vs) {
// check base case for recursion
if (vs.size() <= 1) {
return vs;
}
// find midpoint
long mid = vs.size() / 2;
// divide into two
vector<string> lowerHalf = partial (vs, 0, mid-1);
vector<string> upperHalf = partial (vs, mid, vs.size()-1);
// sort using mergeSort
vector<string> lowerSorted = mergeSort(lowerHalf);
vector<string> upperSorted = mergeSort(upperHalf);
// merge the two halves
return merge(lowerSorted, upperSorted);
}
int main(int argc, const char * argv[]) {
vector<string> unsorted = makeRandomStrings();
printVector (unsorted);
auto beforeMerge = chrono::high_resolution_clock::now();
vector<string> sorted = mergeSort(unsorted);
auto afterMerge = chrono::high_resolution_clock::now();
auto mergeElapsedTime = afterMerge - beforeMerge;
printVector (sorted);
auto beforeBubble = chrono::high_resolution_clock::now();
bubblesort (unsorted);
auto afterBubble = chrono::high_resolution_clock::now();
auto bubbleElapsedTime = afterBubble - beforeBubble;
printVector (unsorted);
cout << "Merge Sort: " << mergeElapsedTime.count() << endl;
cout << "Bubble Sort: " << bubbleElapsedTime.count() << endl;
cout << "Improvement factor: " << bubbleElapsedTime / mergeElapsedTime << endl;
return 0;
}
