PAD Praktikum 4

void aufgabe_11() {
    const int n = 500000; // Anzahl der Zahlen im Array, muss statisch im Code festgelegt werden
    int A[n];

    for (int i = 0; i < n; i++) {
        A[i] = rand();
    }
    time_t timetmp = time(NULL);

    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j >= i; j--) {
            if (A[j - 1] > A[j]) {
                int tmp = A[j - 1];
                A[j] = A[j];
                A[j] = tmp;
            }
        }
        cout << "Fortschritt für " << n << " Zahlen: " << int(i * 100.0 / n) << " %\r";
    }

    cout << endl << "Zeit für " << n << " Zahlen: " << time(NULL) - timetmp << " Sekunden";
}

void aufgabe_12() {
    const int n = 500000; // Anzahl der Zahlen im Array, muss statisch im Code festgelegt werden
    int A[n];

    for (int i = 0; i < n; i++) {
        A[i] = rand();
    }
    time_t timetmp = time(NULL);

    for (int i = 0; i < n - 1; i++) {
        int tmp_cnt = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[tmp_cnt])
                tmp_cnt = j;
        if (tmp_cnt != i) {
            int tmp_val = A[tmp_cnt];
            for (int j = tmp_cnt; j > i; j--)
                A[j] = A[j - 1];
            A[i] = tmp_val;
        }
        cout << "Fortschritt für " << n << " Zahlen: " << int(i * 100.0 / n) << " %\r";
    }

    cout << endl << "Zeit für " << n << " Zahlen: " << time(NULL) - timetmp << " Sekunden";
}

void aufgabe_13() {
    const int n = 200000; // Anzahl der Zahlen im Array, muss statisch im Code festgelegt werden

    // Je nachdem ob man Vector oder Array für die Aufgabe verwendet das andere auskommentieren

    ///*
    vector<int> A(0);
    for (int i = 0; i < n; i++)
        A.push_back(rand());
    //*/

    /*
    int A[n];
    for (int i = 0; i < n; i++)
        A[i] = rand();
    */


    time_t timetmp = time(NULL);

    for (int i = 1; i < n; i++) {
        int tmp = A[i], ins = -1, left = 0, right = i;
        while (true) {
            if (left == right) {
                ins = left;
                break;
            }
            int mid = left + ((right - left) / 2);
            if (tmp > A[mid]) {
                left = mid + 1;
                continue;
            }
            if (tmp < A[mid]) {
                right = mid;
                continue;
            }
            ins = mid;
            break;
        }
        for (int j = i - 1; j >= ins; j--)
            A[j + 1] = A[j];
        A[ins] = tmp;
        cout << "Fortschritt für " << n << " Zahlen: " << int(i * 100.0 / n) << " %\r";
    }

    cout << endl << "Zeit für " << n << " Zahlen: " << time(NULL) - timetmp << " Sekunden";

}