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?
7/23/2021 10:00:52 PMMohamed Kharma
10 AnswersNew Answer
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.
1. Try using short instead of int. It should take half as long to move 2 bytes as 4 bytes. 2. Try sorting 100000 elements at a time(insertion sort). Then merge the sorted arrays. 3. If 100000 is still too big, try 50000, 20000 or maybe even 10000.
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
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
You need to execute it on your machine or any other machine unlike sololearn that halts any execution that takes more than few seconds .
Ipang how should i store it then? Would: int *randarray = new int[arraysize] work?
@all Thank you for the help.
Abhay yeah i tried that
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.
Please can help me with any program the include if else statement using c++