+ 2

Runtime of 1 million elements[SOLVED]

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?

23rd Jul 2021, 10:00 PM
Mohamed Kharma
Mohamed Kharma - avatar
9 Antworten
+ 3
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.
24th Jul 2021, 3:05 AM
Ipang
+ 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
23rd Jul 2021, 10:28 PM
Angelo
Angelo - avatar
+ 2
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
24th Jul 2021, 2:48 AM
Ipang
+ 1
You need to execute it on your machine or any other machine unlike sololearn that halts any execution that takes more than few seconds .
23rd Jul 2021, 10:24 PM
Abhay
Abhay - avatar
+ 1
Ipang how should i store it then? Would: int *randarray = new int[arraysize] work?
24th Jul 2021, 2:51 AM
Mohamed Kharma
Mohamed Kharma - avatar
+ 1
@all Thank you for the help.
24th Jul 2021, 3:51 PM
Mohamed Kharma
Mohamed Kharma - avatar
0
Abhay yeah i tried that
23rd Jul 2021, 10:49 PM
Mohamed Kharma
Mohamed Kharma - avatar
0
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.
24th Jul 2021, 2:54 AM
Mohamed Kharma
Mohamed Kharma - avatar
0
Please can help me with any program the include if else statement using c++
25th Jul 2021, 5:04 AM
Abubakar Sadiq Ahmad
Abubakar Sadiq Ahmad - avatar