Tags:
create new tag
view all tags

Day 1 Sample code

Hello world

#include <iostream>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */


using namespace std;
vector<int> genIntList(int n);
void display(vector<int> n);
void merge_sort(vector<int> &iArray, int s, int e);
void selectionSort(vector<int> &a);

const int MAXNUM = 1000;

int main() {
    clock_t t;
    srand(time(NULL));
    int n;
    vector<int> nums1, nums2;
    cout << "How many numbers? ";
    cin >> n;

    nums1 = genIntList(n);

    nums2 = nums1;

    t = clock();
    merge_sort(nums2, 0, nums2.size() - 1);
    t = clock() - t;
    cout << "Merge sort took " << ((float) t) / CLOCKS_PER_SEC << " seconds" << endl;
    //display(nums2);

    t = clock();
    selectionSort(nums1);
    t = clock() - t;
    cout << "Selection sort took " << ((float) t) / CLOCKS_PER_SEC << " seconds" << endl;
    //display(nums1);



    return 0;
}

vector<int> genIntList(int n) {
    vector<int> list;

    for (int i = 0; i < n; i++) {
        list.push_back(rand() % MAXNUM);
    }
    return list;
}

void display(vector<int> n) {
    for (int i = 0; i < n.size(); i++) {
        cout << n.at(i) << " ";
    }
    cout << endl;
}

void merge(vector<int> &a, int s, int e) {

    vector<int> b;

    int i = s;
    int m = (s + e) / 2;
    int j = m + 1;

    while ((i <= m) && (j <= e)) {
        if (a[i] < a[j]) {
            b.push_back(a[i++]);
        } else {
            b.push_back(a[j++]);
        }
    }

    if (j <= e) {
        for (int k = j; k <= e; k++) {
            b.push_back(a[k]);
        }
    }
    if (i <= m) {
        for (int k = i; k <= m; k++) {
            b.push_back(a[k]);
        }
    }

    int k = 0;
    for (int i = s; i <= e; i++) {
        a[i] = b[k++];
    }
}

//The recursive merge sort function

void merge_sort(vector<int> &iArray, int s, int e) {
    int m;
    //Check for base case
    if (s >= e) {
        return;
    }
    //First, divide in half
    m = (s + e) / 2;
    //First recursive call 
    merge_sort(iArray, s, m);
    //Second recursive call 
    merge_sort(iArray, m + 1, e);
    //The merge function
    merge(iArray, s, e);
}

void swap_values(int& v1, int& v2) {
    int temp;
    temp = v1;
    v1 = v2;
    v2 = temp;
}

int index_of_smallest(vector<int> a, int start_index) {
    int min = a[start_index];
    int index_of_min = start_index;
    for (int index = start_index + 1; index < a.size(); index++)
        if (a[index] < min) {
            min = a[index];
            index_of_min = index;
            //min is the smallest of a[start_index] through a[a.size()-1]
        }

    return index_of_min;
}

void selectionSort(vector<int> &a) {
    int index_of_next_smallest;
    for (int index = 0; index < a.size() - 1; index++) {//Place the correct value in a[index]:

        index_of_next_smallest = index_of_smallest(a, index);
        swap_values(a[index], a[index_of_next_smallest]);

        //a[0] <= a[1] <=...<= a[index] are the smallest of the original array 
        //elements. The rest of the elements are in the remaining positions.
    }
}

Topic revision: r1 - 2017-12-05 - JimSkon
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback