Turbo cpp/tsort

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.

3 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