problem with measuring time of that algorithms

Question

i've got some trobules with my project, so i have to measure uptime of few sorting algorithms. There is the code:

#include <iostream>
#include <fstream>
#include <time.h>
#include <random>
using namespace std;

int A[100000];
int n = 100000;
void fill_random() {
    fstream vals;
    vals.open("random_vals.txt", ios::in | ios::app | ios::out);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        A[i] = rand();
        vals << A[i] << "\n";
    }
    vals.close();
}

void fill_increasing() {
    fstream vals;
    vals.open("increasing_vals.txt", ios::in | ios::app | ios::out);
    for (int i = 0; i < n; i++) {
        A[i] = i;
        vals << A[i] << "\n";
    }
    vals.close();
}

void fill_decreasing() {
    fstream vals;
    vals.open("decreasing_vals.txt", ios::in | ios::app| ios::out);
    for (int i = 0; i < n; i++) {
        A[i] = -i;
        vals << A[i] << "\n";
    }
    vals.close();
}

void fill_vshape() {
    fstream vals;
    vals.open("vshape_vals.txt", ios::in | ios::app | ios::out);
    int i = 0;
    int j = n - 1;
    int k = 0;
    while (i < j)
    {
        A[i] = k;
        A[j] = k - 1;
        i = i + 1;
        j = j - 1;
        k = k - 2;
        vals << A[i] << "\n";
        vals << A[j] << "\n";

    }
    if (i == j) A[i] = k;

    vals.close();
}

void Swap(int A[], int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}
//Selection sort
int ArgMin(int A[], int begin, int end) {
    int argmin = begin;
    for (int i = begin + 1; i <= end; i++) {
        if (A[i] < A[argmin]) argmin = i;
    }
    return argmin;
}
void SelectionSort(int A[], int n) {
    for (int i = 0; i <= n - 1; i++) {
        int j = ArgMin(A, i, n - 1);
        Swap(A, i, j);
    }
}

//InsertionSort
void InsertionSort(int A[], int n) {
    for (int j = 1; j <= n-1; j++) {
        int key = A[j];
        int i = j - 1;
        while (i >= 0 && A[i] > key) {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;
    }
}
//QuickSort
int partition(int A[], int p, int q) {
    int pivot = A[q];
    int i = p - 1;
    for (int j = p; j < q; j++) {
        if (A[j] <= pivot) {
            i++;
            Swap(A, i, j);
        }
    }
    swap(A[i + 1], A[q]);
    return i + 1;
}

void QuickSort(int A[], int p, int q) {
    while (p < q) {
        int pivot = partition(A, p, q);
        if (pivot - p < q - pivot) {
            QuickSort(A, p, pivot - 1);
            p = pivot + 1;
        }
        else {
            QuickSort(A, pivot + 1, q);
            q = pivot - 1;
        }
    }
}

//RandomizedQuickSort

int RandomizedPartition(int A[], int p, int r) {
    int i = 0;
    i = (rand() % (r - p + 1)) + p;
    Swap(A, i, r);
    return partition(A, p, r);
}
void RandomizedQuickSort(int A[], int p, int r) {
    while (p < r) {
        int q = RandomizedPartition(A, p, r);
        if (q - p < r - q) {
            RandomizedQuickSort(A, p, q - 1);
            p = q + 1;
        }
        else {
            RandomizedQuickSort(A, q + 1, r);
            r = q - 1;
        }
    }
}
//HeapSort
void Heapify(int A[], int n, int i) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int largest = i;
    if (l<n && A[l]>A[largest]) {
        largest = l;
    }
    if (r<n && A[r]>A[largest]) {
        largest = r;
    }
    if (largest != i) {
        Swap(A, i, largest);
        Heapify(A, n, largest);
    }
}
void BuildMaxHeap(int A[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        Heapify(A, n, i);
    }
}
void HeapSort(int A[], int n) {
    BuildMaxHeap(A, n);
    for (int i = n - 1; i > 0; i--) {
        Swap(A, i, 0);
        Heapify(A, i, 0);
    }
}

void functions(string file) {
    int* T;
    int k = 100000;
    fstream results;
    results.open("results.txt", ios::in | ios::app | ios::out);
    fstream vals;
    vals.open(file, ios::in | ios::app | ios::out);
   //Selection sort
    cout << "Selection sort\n";
    results << "Selection sort\n";
    for (int i = 1; i <= 10; i++)
    {
        vals.open(file, ios::in | ios::app | ios::out);
        T = new int[i * 10000];
        for (int j = 0; j < i*10000; j++) {
            vals >> T[j];
        }
        clock_t begin = clock();
        SelectionSort(T, i * 10000);
        clock_t end = clock();
        cout << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        results << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        delete[] T;
    }
    vals.close();
    //Insertion sort
    cout << "Insertion sort\n";
    results << "Insertion sort\n";
    for (int i = 1; i <= 10; i++)
    {
        vals.open(file, ios::in | ios::app | ios::out);
        T = new int[i * 10000];
        for (int j = 0; j < i * 10000; j++) {
            vals >> T[j];
        }
        clock_t begin = clock();
        InsertionSort(T, i * 10000);
        clock_t end = clock();
        cout << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        results << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        delete[] T;
    }
    vals.close();
    //Quick sort
    cout << "Quick sort\n";
    results << "Quick sort\n";
    for (int i = 1; i <= 10; i++)
    {
        vals.open(file, ios::in | ios::app | ios::out);
        T = new int[i * 10000];
        for (int j = 0; j < i * 10000; j++) {
            vals >> T[j];
        }
        clock_t begin = clock();
        QuickSort(T, 0, (i * 10000) - 1);
        clock_t end = clock();
        cout << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        results << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        delete[] T;
    }
    vals.close();
    //Randomized Quick sort
    cout << "Randomized quick sort\n";
    results << "Randomized quick sort\n";
    for (int i = 1; i <= 10; i++)
    {
        vals.open(file, ios::in | ios::app | ios::out);
        T = new int[i * 10000];
        for (int j = 0; j < i * 10000; j++) {
            vals >> T[j];
        }
        clock_t begin = clock();
        RandomizedQuickSort(T, 0, i * 10000 - 1);
        clock_t end = clock();
        cout << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        results << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        delete[] T;
    }
    vals.close();
    //Heap sort
    cout << "Heap sort\n";
    results << "Heap sort\n";
    for (int i = 1; i <= 10; i++)
    {
        vals.open(file, ios::in | ios::app | ios::out);
        T = new int[i * 10000];
        for (int j = 0; j < i * 10000; j++) {
            vals >> T[j];
        }
        clock_t begin = clock();
        HeapSort(T, i * 10000);
        clock_t end = clock();
        cout << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
        results << i * 10000 << "k:" << (double)(end - begin) / CLOCKS_PER_SEC << "\n";
    }
    delete[] T;
    vals.close();
}
int main() {
    fill_random();
    fill_increasing();
    fill_decreasing();
    fill_vshape();
    fstream results;
    results.open("results.txt", ios::in | ios::app | ios::out);

    ///random values
    cout << "===RANDOM VALUES===\n";
    results << "===RANDOM VALUES===\n";

    functions("random_vals.txt");

    ///increasing values
    cout << "===INCREASING VALUES===\n";
    results << "===INCREASING VALUES===\n";

    functions("increasing_vals.txt");

    ///decreasing values
    cout << "===DECREASING VALUES===\n";
    results << "===DECREASING VALUES===\n";

    functions("decreasing_vals.txt");

    ///vshape values
    cout << "===VSHAPE VALUES===\n";
    results << "===VSHAPE VALUES===\n";

    functions("vshape_vals.txt");
}

I dont know why, but insertion sort returns 0 seconds values - of course in some cases this algorithm can be O(n) and can be really fast, but i.e for random data of 100 000 numbers the uptime should be much longer. The same problem i have with heap sort - I know that this algorithm is n log n and can be really fast, but returned values are in my opinion too low and they have no sense (sorting i.e 100k numbers is faster than 70k ). I tried to solve that problems with chatgpt - it helped me with a lot of stack overflow problems with quicksorts but it didnt solve that 2 issues: ). Can somebody help me with that problems? There must be some logical problems. I also tried to see the values of T[] before using of InsertionSort() and i don't know why the list dont have assigned values. There is example of results

===RANDOM VALUES===
Selection sort
10000k:0.057
20000k:0.268
30000k:0.629
40000k:1.1
50000k:1.658
60000k:2.264
70000k:3.047
80000k:3.93
90000k:5.007
100000k:6.103
Insertion sort
10000k:0.04
20000k:0.001
30000k:0
40000k:0
50000k:0
60000k:0
70000k:0
80000k:0
90000k:0
100000k:0
Quick sort
10000k:0.001
20000k:0.959
30000k:2.12
40000k:3.778
50000k:5.906
60000k:8.494
70000k:11.636
80000k:14.97
90000k:18.624
100000k:23.085
Randomized quick sort
10000k:0.002
20000k:0.918
30000k:2.052
40000k:3.728
50000k:5.706
60000k:8.248
70000k:13.48
80000k:23.045
90000k:18.613
100000k:23.168
Heap sort
10000k:0.001
20000k:0.001
30000k:0.001
40000k:0.001
50000k:0.002
60000k:0.001
70000k:0.002
80000k:0.001
90000k:0.003
100000k:0.002
===INCREASING VALUES===
Selection sort
10000k:0.063
20000k:0.239
30000k:0.529
40000k:0.993
50000k:1.519
60000k:2.115
70000k:2.91
80000k:3.759
90000k:4.871
100000k:5.926
Insertion sort
10000k:0
20000k:0
30000k:0
40000k:0
50000k:0
60000k:0
70000k:0
80000k:0
90000k:0.001
100000k:0.001
Quick sort
10000k:0.235
20000k:0.941
30000k:2.141
40000k:3.643
50000k:5.68
60000k:8.161
70000k:11.238
80000k:14.606
90000k:18.552
100000k:22.808
Randomized quick sort
10000k:0.001
20000k:0.922
30000k:2.032
40000k:3.686
50000k:5.682
60000k:8.212
70000k:11.168
80000k:14.563
90000k:18.44
100000k:22.94
Heap sort
10000k:0.002
20000k:0.001
30000k:0.001
40000k:0.001
50000k:0.001
60000k:0
70000k:0.002
80000k:0.001
90000k:0.001
100000k:0.001
===DECREASING VALUES===
Selection sort
10000k:0.058
20000k:0.236
30000k:0.534
40000k:0.99
50000k:1.483
60000k:2.108
70000k:2.882
80000k:3.78
90000k:4.74
100000k:5.992
Insertion sort
10000k:0.083
20000k:0
30000k:0
40000k:0
50000k:0
60000k:0
70000k:0
80000k:0
90000k:0
100000k:0
Quick sort
10000k:0.137
20000k:0.922
30000k:2.079
40000k:3.701
50000k:5.992
60000k:11.125
70000k:17.698
80000k:24.486
90000k:27.251
100000k:24.234
Randomized quick sort
10000k:0.001
20000k:0.91
30000k:2.1
40000k:3.732
50000k:5.905
60000k:8.6
70000k:11.618
80000k:15.222
90000k:20.774
100000k:26.331
Heap sort
10000k:0.002
20000k:0
30000k:0.001
40000k:0.001
50000k:0
60000k:0.001
70000k:0.001
80000k:0.001
90000k:0.001
100000k:0.001
===VSHAPE VALUES===
Selection sort
10000k:0.099
20000k:0.246
30000k:0.539
40000k:0.947
50000k:1.506
60000k:2.18
70000k:3.07
80000k:3.975
90000k:5.01
100000k:7.47
Insertion sort
10000k:0.043
20000k:0
30000k:0
40000k:0
50000k:0
60000k:0
70000k:0
80000k:0
90000k:0.001
100000k:0
Quick sort
10000k:0.079
20000k:1.036
30000k:2.267
40000k:3.944
50000k:6.113
60000k:8.47
70000k:11.916
80000k:15.424
90000k:20.015
100000k:23.917
Randomized quick sort
10000k:0.001
20000k:0.914
30000k:2.078
40000k:3.886
50000k:6.103
60000k:8.535
70000k:11.933
80000k:14.784
90000k:19.946
100000k:24.883
Heap sort
10000k:0.001
20000k:0
30000k:0.001
40000k:0
50000k:0.001
60000k:0.001
70000k:0.001
80000k:0.002
90000k:0.001
100000k:0.001

C:\Users\sergi\source\repos\zad1\x64\Debug\zad1.exe (process 7264) exited with code 0.
To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
Press any key to close this window . . .

An optimizing compiler can completely remove your calls to `InsertionSort` (or any of your sorts, if I'm observing them correctly), because the results of those sorts are never used. See the [as-if rule](https://stackoverflow.com/questions/15718262/what-exactly-is-the-as-if-rule#:~:text=The%20%22as%2Dif%22%20rule%20implies%20that%20in%20any%20situation,to%20be%20characterized%20as%20UB.). — Drew Dormann, Mar 14 '23 at 01:12
To ensure your compiler doesn't optimize the entire calculation away, make sure your program produces output derived from the operation. One such way to do that might be to output the result of calling `std::is_sorted` on your data. That's also a useful test to ensure your algorithm actually sorted the data. — paddy, Mar 14 '23 at 02:47
Side note: Too much code. If you have a bug with insertion sort, you want a program that does nothing but demonstrate the problem with the insertion sort program. That's a `main` function that fills up the array with values to be sorted (best not to use random values for this because you want repeatable results) calls the insertion sort function, and then prints the broken results. Usually while you're making this example you find you've stripped out enough of the unnecessary stuff to give the mistake too little room to hide in, spot the sucker, and fix it. — user4581301, Mar 14 '23 at 02:53

score -1 · Answer 1 · answered Mar 14 '23 at 10:50

It turned out that the problem was the way of getting data from file. Opening and closing file many times caused that numbers werent loaded correctly (it loaded 0s or weird numbers), so instead of opening the file many times for getting into start of the file I used seekg method.

problem with measuring time of that algorithms

1 Answers1