##### Differences

This shows you the differences between two versions of the page.

 — cs-142:sort [2014/11/18 08:02] (current)kseppi created 2014/11/18 08:02 kseppi created 2014/11/18 08:02 kseppi created Line 1: Line 1: + + #include <​cstdlib>​ + #include <​ctime>​ + #include <​iostream>​ + #include <​vector>​ + + using namespace std; + + /** + Merges two adjacent ranges in an vector. + @param a the vector with the elements to merge + @param from the start of the first range + @param mid the end of the first range + @param to the end of the second range + */ + void merge(vector<​int>​ & a, int from, int mid, int to) + { + int n = to - from + 1; // Size of the range to be merged + // Merge both halves into a temporary vector b + vector<​int>​ b(n); + + int i1 = from; + // Next element to consider in the first half + int i2 = mid + 1; + // Next element to consider in the second half + int j = 0; // Next open position in b + + // As long as neither i1 nor i2 is past the end, move the smaller + // element into b + + while (i1 <= mid && i2 <= to) + { + if (a[i1] < a[i2]) + { + b[j] = a[i1]; + i1++; + } + else + { + b[j] = a[i2]; + i2++; + } + j++; + } + + // Note that only one of the two while loops below is executed + // Copy any remaining entries of the first half + while (i1 <= mid) + { + b[j] = a[i1]; + i1++; + j++; + } + // Copy any remaining entries of the second half + while (i2 <= to) + { + b[j] = a[i2]; + i2++; + j++; + } + + // Copy back from the temporary vector + for (j = 0; j < n; j++) + { + a[from + j] = b[j]; + } + + + } + + /** + Sorts the elements in a range of an vector. + @param a the vector with the elements to sort + @param from start of the range to sort + @param to end of the range to sort + */ + void merge_sort(vector<​int>​ & a, int from, int to) + { + if (from == to) { return; } + int mid = (from + to) / 2; + // Sort the first half and the second half + merge_sort(a,​ from, mid); + merge_sort(a,​ mid + 1, to); + merge(a, from, mid, to); + } + + /** + Prints all elements in an vector. + @param a the array to print + @param size the number of elements in a + */ + void print(vector<​int>​ a, int size) + { + for (int i = 0; i < size; i++) + { + cout << a[i] << " "; + } + cout << endl; + } + + int main() + { + srand((unsigned int) time(0)); + const int SIZE = 20; + vector<​int>​ values; + for (int i = 0; i < SIZE; i++) + { + values.push_back(rand() % 100); + } + print(values,​ SIZE); + merge_sort(values,​ 0, SIZE - 1); + print(values,​ SIZE); + system("​pause"​);​ + return 0; + } + 