Differences

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

Link to this comparison view

cs-142:sort [2014/11/18 15:02] (current)
kseppi created
Line 1: Line 1:
 +<code c++> 
 +#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; 
 +
 +</​code>​
cs-142/sort.txt · Last modified: 2014/11/18 15:02 by kseppi
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0