# Difference: SortCompare ( vs. 1)

#### Revision 12017-12-05 - JimSkon

Line: 1 to 1
>
>
 META TOPICPARENT name="Fall2017"

### Hello world

`<-- SyntaxHighlightingPlugin -->`
```#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.
}
}

```
`<-- end SyntaxHighlightingPlugin -->`

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback