can anybody pls tell wich sorting technique i need to use??i tried with quick sort and insertion sort…both got tym limit exceed…i did with faster i/o…still it s not working…pls help…thanks
Insertion sort is O( n^2 ), Quick Sort is also O( n^2 ) in worst case. No. of elements in array is 10^6 => ( 10^6 ) ^ 2 = 10^4 * 10^8 operations. Judge computes 10^8 instructions in a second, yours would take ~10^4 seconds even with fast I/O.
Read more about sorting algorithms here
https://en.wikipedia.org/wiki/Sorting_algorithm
http://www.sorting-algorithms.com/
Try Merge-Sort, it’s O( n*log(n) ) or Count Sort which would work here & is even faster O( n ).
https://en.wikipedia.org/wiki/Merge_sort
https://en.wikipedia.org/wiki/Counting_sort
Regards,
Ouditchya Sinha.
2 Likes
thanks bro…
try bucket sort
If the range of the numbers to be sorted is around 1e6, the array can be easily sorted in o(n) as we can easily create an array of size 1e6 and its indices can be used for storing frequencies of elements.
1 Like