Merge Sort - Monday Dec. 12

Presentations ...

• PowerPoint
• PDF format

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;
}