Is there any better Sorting technique?

general
1

I tried to solve TSORT problem using quicksort…
It is one of the best sorting algorithm having time complexity nlogn…
Still it says time limit exceeded…
Can anyone suggest me some other better algorithm or is there some catch or something?

1 Like
2

There is a problem with your implementation. O(n \log n) solution passes easily.
BTW that problem is supposed to get you acquainted with your favorite language inbuilt sorting function.
C: qsort
C++: sort

Also if you are using C++ it might be a slow I/O issue.

3

Quick sort has a complexity of O(n^2) in worst case. Therefore it is better to use merge-sort or in-built sort function in c++ which has a time complexity of O(nlogn).

4

Merge Sort or Tim sort is best But it take extra O(n) space. And Time complexity is always O(nlogn)

5

Use inbuilt stl in c++ sort(arr,arr+n); to sort the array take maximum array size to be 10^6 it will remove time complexity

1 Like
6

Don’t forget that the worst time complexity of quick sort algorithm is O(N^2).

Try any other sorting algorithm with worst time complexity O(N lg N) and it’ll surely pass.

Heap sort: CodeChef: Practical coding for everyone

Merge sort:
https://www.codechef.com/viewsolution/16263565

Tim sort:
CodeChef: Practical coding for everyone (Python magic ;))

In fact you can visit my github profile
sorting-/ at master · sarthakmanna/sorting- · GitHub for different sorting algorithms.

Useless, I know… :frowning:

7

Inbuilt sort function in c++ passes it in 0.15… refer this solution for using in built function of c++…
Well this can be done in O(2t + 2000001) ( which is O(t) ) and which is O(4000001) in worst case since input is 0<=N<=10^6 ,0<=t<=10^6 … Here is link of my 2nd soln and it is O(t) which ran in 0.11 seconds… code has (more than) enough comments and do let me know if u dont get…

8

Merge sort works always.

1 Like
9

Soln 2 is useful when range of the numbers is less…
And the soln 1 is useful when t is small…

10

thank you :slight_smile:
problem solved…must have been the worst case of quicksort which was making a problem…worked with merge sort :smiley:

11

FYI: problem is not with quicksort but your implementation. A randomised pivot selection gives expected O(n \log n) even in the worst case.