Runtime of 1 million elements[SOLVED]

Question

I wrote this code below that allows you to enter an array size and then it stores random numbers between 1 - 999 in the array, then sorts them and give the runtime in nanoseconds.

This is the code:
https://code.sololearn.com/cA2A59A21A87

However, when I try to put the size of the array to 1000000, the code would just stop working. Any suggestions on how to get it to sort an array of size 1 million?

Answer 1

Mohammed Kharma,
Yes it will work, I was just reminding you the difference.

int randArray[arraysize]; // in stack

int* randArray = new int[arraysize]; // in heap

Prefer heap storage when big memory allocation is needed in order not to exhaust the stack.

Answer 2

The time complexity of insertion sort is O(n^2),
this means that even if the CPU runs at 4GHz (4000000000 cicles per second) and you perform one step every cicle it will take 250 second to finish

At first sight I'll say every step takes maybe 17 cicles, that means 250*17=4250s= more than 70min

P. S. : consider using std:vector (or array) and the random library
Also, that while loop can easily be a for loop and it's better to use --j or j-=1 than j=j-1

Answer 3

Apart from the algorithm thingy,
Use of VLA with 1.000.000 elements consumes a considerable amount of memory, not to mention compatibility issue.

int randArray[arraysize]; // VLA usage

Answer 4

You need to execute it on your machine or any other machine unlike sololearn that halts any execution that takes more than few seconds .

Answer 5

Ipang how should i store it then? Would:
int *randarray = new int[arraysize]
work?

Answer 6

@all Thank you for the help.

Answer 7

Abhay yeah i tried that

Answer 8

Angelo i see what you mean but i am kinda forced to use insertion sort. i will try to change the while loop to for loop and run it again. Thank you.

Answer 9

Please can help me with any program the include if else statement using c++