Code Exiting on above 500,000 number of input

Ali Hasan Khan 0
Viewed 61

I was performing sorting algorithm to calculate their runtime to execute, in which I was giving millions of number of input to sort, but my code is exiting on above 500,000 input and not showing any output. Is there anyway I can solve it.

int size;
cout<<"Enter size of the array: "<<endl;
cin>>size;
int a[size];
for(int i=0;i<size;i++)
{
    a[i]=rand()%size;
}
int temp = 0;
double cl=clock();
for (int i = 0; i < size; i++)
{
    for (int j = i + 1; j < size; j++)
    {
        if (a[j] < a[i])
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}
double final=clock()-cl;
cout<<final/(double)CLOCKS_PER_SEC;

}

c++14 sorting algorithm c++
1 Answers

You code crashes on 500'000 input because of stack overflow, you're allocating array on stack of too big size:

int a[size];

Stack size is usually few megabytes at most.

Also it is probably an extensions not of all compilers to have dynamically allocated array on stack, usually size should be a compile time constant.

To overcome stack crash either you have to use std::vector which can provide any size as big as there is free memory, for that do:

std::vector<int> a(size);

(also #include <vector>). Or you may use dynamically allocated array through new operator:

int * a = new int[size];

For this case don't forget to do delete[] a; at the end of program (see docs here).

Don't forget that input 500'000 takes very much of time using your bubble sort. For example 10 times less, 50'000, takes around 10 seconds on my machine.

Full working code using std::vector plus code formatting:

Try it online!

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int size;
    cout << "Enter size of the array: " << endl;
    cin >> size;
    std::vector<int> a(size);
    for (int i = 0; i < size; i++) {
        a[i] = rand() % size;
    }
    int temp = 0;
    double cl = clock();
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (a[j] < a[i]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    double final = clock() - cl;
    cout << final / (double)CLOCKS_PER_SEC;
}
Arty0
Related