Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*Matlab
- figure; n=[100 1000 2000 3000 4000 5000 6000]; t=[0 0.04 0.15 0.32 0.56 0.87 1.26]; plot(n,t);
- */
- #include <iostream>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <assert.h>
- #include <iomanip>
- #include <vector>
- #include <sstream>
- #include <algorithm>
- using namespace std;
- // Aufgabe 2.1
- vector <double> GenerateNumbers(string Selection, size_t n){
- vector<double> feld;
- for (size_t i = 0; i < n; i++){
- if (!string(Selection).compare("up")){ feld.push_back(i); }
- else if (!string(Selection).compare("down")){ feld.push_back(i*(-1)); }
- else if (!string(Selection).compare("constant")){ feld.push_back(17); }
- else if (!string(Selection).compare("random")){ feld.push_back((double)rand() / (RAND_MAX)); }
- else{ throw "Error: Das Programm braucht einen Modus! [random|up|down|constant]"; }
- }
- return feld;
- }
- //Aufgabe 2.2
- template < class T > bool IsSortedAndNothingIsLost
- (vector <T> &Before, vector <T> &After){
- bool SomethingIsLost = false;
- size_t n = Before.size();
- //überprüfung des sortierten vektors
- for (size_t i = 0; i<(n - 1); i++)
- {
- if (After[i]>After[i + 1])
- {
- return false;
- }
- }
- //Wir überprüfen jede einzelne Stelle und haken ab
- bool *hilfsarray = new bool[n];
- if (*hilfsarray == NULL){ throw "Das Hilfsarray hatte nicht genug speicher um erstellt zu werden."; }
- for (size_t i = 0; i<n; i++)
- {
- hilfsarray[i] = false;
- }
- // wir haken ab
- for (size_t i = 0; i<n; i++)
- {
- SomethingIsLost = true;
- for (size_t j = 0; j < n; j++){
- if (Before[i] == After[j] && false == hilfsarray[j]){
- hilfsarray[j] = true;
- SomethingIsLost = false;
- break;
- }
- }
- if (true == SomethingIsLost){
- delete[] hilfsarray;
- return false;
- }
- }
- delete[] hilfsarray;
- return true;
- }
- //Aufgabe 2.3
- template <class T> void InsertionSort(vector<T> &a){
- const int len = (int)a.size();
- int i, j;
- T temp;
- for (i = 1; i < len; i++){
- temp = a[i];
- for (j = i - 1; j >= 0 && a[j] > temp; j--){
- a[j + 1] = a[j];
- }
- a[j + 1] = temp;
- }
- }
- //template <class T> void MergeSort(vector<T> &a){
- /*int curr_size; // For current size of subarrays to be merged
- // curr_size varies from 1 to n/2
- int left_start; // For picking starting index of left subarray
- // to be merged
- int n = a.size();
- // Merge subarrays in bottom up manner. First merge subarrays of
- // size 1 to create sorted subarrays of size 2, then merge subarrays
- // of size 2 to create sorted subarrays of size 4, and so on.
- for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size)
- {
- // Pick starting point of different subarrays of current size
- for (left_start = 0; left_start<n - 1; left_start += 2 * curr_size)
- {
- // Find ending point of left subarray. mid+1 is starting
- // point of right
- int mid = left_start + curr_size - 1;
- int right_end = min(left_start + 2 * curr_size - 1, n - 1);
- // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
- merge(a, left_start, mid, right_end);
- }
- }
- }
- /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
- //template <class T> void merge(vector<T> &a, int l, int m, int r)
- /*{
- int i, j, k;
- int n1 = m - l + 1;
- int n2 = r - m;
- // create temp vectors
- vector<T> L (n1), R(n2);
- // Copy data to temp vectors L[] and R[]
- for (i = 0; i < n1; i++)
- L[i] = a[l + i];
- for (j = 0; j < n2; j++)
- R[j] = a[m + 1 + j];
- // Merge the temp arrays back into arr[l..r]
- i = 0;
- j = 0;
- k = l;
- while (i < n1 && j < n2)
- {
- if (L[i] <= R[j])
- {
- a[k] = L[i];
- i++;
- }
- else
- {
- a[k] = R[j];
- j++;
- }
- k++;
- }
- // Copy the remaining elements of L[], if there are any
- while (i < n1)
- {
- a[k] = L[i];
- i++;
- k++;
- }
- // Copy the remaining elements of R[], if there are any
- while (j < n2)
- {
- a[k] = R[j];
- j++;
- k++;
- }
- }
- /*
- //Aufgabe 2.4
- /*
- template <class T> void MergeSort(vector<T> &a){
- const int len = (int)a.size();
- T* x = a;
- T* y = new T[len];
- for (int seg = 1; seg < len; seg += seg){
- for (int start = 0; start < len; start += seg + seg){
- int low = start;
- int mid = (start + seg) < len ? (start + seg) : len;
- int high = (start + seg + seg) < len ? (start + seg + seg) : len;
- int k = low;
- int start1 = low, end1 = mid;
- int start2 = mid, end2 = high;
- while (start1 < end1 && start2 < end2){
- y[k++] = x[start1] < x[start2] ? a[start1++] : a[start2++];
- }
- while(start1 < end1){
- y[k++] = x[start1++];
- }
- while (start2 < end2){
- y[k++] = x[start2++];
- }
- }
- T* temp = x;
- x = y;
- y = temp;
- }
- if (x != a){
- for (int i = 0; i < len; i++){
- y[i] = x[i];
- }
- y = x;
- }
- delete y[];
- }
- */
- //template <class T> void MergeSort(vector<T> &a){}
- template <class T> void merge_sort(vector<T> &V, int size){
- vector<T> temp[size];
- int mid, i;
- if (size < 2) {
- return;
- }
- else {
- mid = size / 2;
- merge_sort(V, mid);
- merge_sort(V + mid, size - mid);
- merge(V, mid, V + mid, size - mid, temp);
- for (i = 0; i < size; i++) {
- V[i] = temp[i];
- }
- }
- }
- template <class T> int merge(vector<T> &List1, int size1, vector<T> &List2, int size2, vector<T> &List3)
- {
- int i1, i2, i3;
- if (size1 + size2 > size) {
- return false;
- }
- i1 = 0; i2 = 0; i3 = 0;
- /* while both lists are non-empty */
- while (i1 < size1 && i2 < size2) {
- if (list1[i1] < list2[i2]) {
- list3[i3++] = list1[i1++];
- }
- else {
- list3[i3++] = list2[i2++];
- }
- }
- while (i1 < size1) {
- /* copy remainder of list1 */
- list3[i3++] = list1[i1++];
- }
- while (i2 < size2) {
- /* copy remainder of list2 */
- list3[i3++] = list2[i2++];
- }
- return true;
- }
- int main(int argc, char *argv[]) {
- char *Selection = NULL;
- // Flags
- bool Vergleich = false;
- bool CheckResult = false;
- bool Zeitmessung = false;
- bool UseMergeSort = false;
- int SizeOfArray = 0;
- vector<double> Original;
- double MeasuredTime;
- // Zuerst fragen wir die Paramter ab:
- try{
- if (argv[1] == NULL){
- throw "mysort n Direction [ -o ] [ -c ] [ -t ] [ -m | -i ]";
- }
- if (!(istringstream(argv[1]) >> dec >> SizeOfArray)){
- throw "Der erste Wert muss ein Integer sein!";
- }
- if (SizeOfArray < 1){
- throw "keine negativen Zahlen erlaubt!";
- }
- // Selection
- if (!string(argv[2]).compare("up") ||
- !string(argv[2]).compare("down") ||
- !string(argv[2]).compare("constant") ||
- !string(argv[2]).compare("random")) {
- Selection = argv[2];
- }
- // checken für flags
- for (int i = 3; i < argc; i++){
- if (!string(argv[i]).compare("-c")) {
- CheckResult = true;
- continue;
- }
- if (!string(argv[i]).compare("-o")) {
- Vergleich = true;
- continue;
- }
- if (!string(argv[i]).compare("-t")) {
- Zeitmessung = true;
- continue;
- }
- if (!string(argv[i]).compare("-m") && !string(argv[i]).compare("-i")){
- throw "-m und -i darf nur einmal benutzt werden!";
- }
- if (!string(argv[i]).compare("-m")) {
- UseMergeSort = true;
- continue;
- }
- if (!string(argv[i]).compare("-i")) {
- UseMergeSort = false;
- continue;
- }
- else{
- throw "Wrong Switch, use only one of - o | -c | -t | -m | -i ";
- }
- }
- if (Selection == NULL){
- throw "Error: Das Programm braucht einen Modus! [random|up|down|constant]";
- }
- //Aufgabe 2.5
- Original.reserve(SizeOfArray);
- Original = GenerateNumbers(Selection, SizeOfArray);
- vector<double>Sorted(Original);
- MeasuredTime = double(clock());
- // Welchen Algorithmus ?
- if (UseMergeSort == true){
- merge_sort(Sorted, SizeOfArray);
- }
- else{
- InsertionSort(Sorted);
- }
- if (Zeitmessung == true){ MeasuredTime = (double(clock()) - MeasuredTime) / CLOCKS_PER_SEC; }
- // Erfolgsüberprüfung
- if (CheckResult == true){
- if (true == IsSortedAndNothingIsLost(Original, Sorted)){
- cout << "Success" << endl;
- }
- else{
- throw "Check failed";
- }
- }
- /*
- if (Vergleich == true){
- cout << "Ergebnisse:" << endl << " Original : Sorted" << endl;
- for (int i = 0; i < SizeOfArray; i++){
- cout << setprecision(5) << setw(9) << Original[i] << " : " << setprecision(5) << Sorted[i] << endl;
- }
- }
- */
- if (Zeitmessung == true){
- cout << "--- It took " << setprecision(32) << MeasuredTime << " seconds to compute---" << endl;
- }
- }
- catch (const char *Error){
- cerr << Error;
- exit(1);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement