Sorting algorithm

general
, , ,
1

which is the best sorting algorithm for a large array ??

2 Likes
2

Any algorithm that promises n * log(n) time and uses less extra space is good . Merge sort is one example which takes the minimum asymptotic time i.e. n * log(n) and takes O(n) space .
NOTE : It is a proven fact that a sorting algorithm cannot take less than n * log(n) time if the array contains arbitrary entries . If the array entries come from a limited set then algorithms like counting sort can sort the array in order n time .

7 Likes
3

Hello @praveen_kishor,

This problem:

[Turbo Sort][1]

can somehow be used as a “benchmark” for how fast a sorting algorithm needs to be in order to solve sorting related problems here.

My advice is that you experiment different algorithms and also explore the built-in sorting functions on the language you are using… That should help you to answer this question.

Best regards,

Bruno
[1]: http://www.codechef.com/problems/TSORT

3 Likes
4

Thanks Vineet…

5

Try using stl functions like sort. You’ll need to to use a vector for that. Once you have a vector say “vec” with values contained in it, you can sort it with the function sort(vec.begin(),vec.end()). This will sort the entire array.

Refer to this link and you may get a better idea.
http://www.cplusplus.com/reference/algorithm/sort/

1 Like
6

Thanks ani, but stl functions are only for c++ ( as i know ). What if i want to write sorting programs in C ?

7

Then you can use function qsort() from stdlib.h:
http://www.cplusplus.com/reference/cstdlib/qsort/
It is available in pure C.
But it’s syntax more complex than for sort.

1 Like
8

Yes, stl exists only for c++ . But, you can have a look at the sorting techniques running in nlogn here : http://en.wikipedia.org/wiki/Sorting_algorithm . I think merge sort and heap sort are good options. Try implementing the merge-sort algorithm .

9

@ani94 i would like to point out that its not necessary to use a vector for using sort function in c++. if u have an array of size n u can simply go for sort(a,a+n)

1 Like
10

I just discovered this post and I would like to clarify one thing.
@vineetpaliwal is almost correct. Comparison-based sorting algorithms cannot be faster than NlgN. However, sorts like Radix Sort can be O(N).

11

check out this http://bigocheatsheet.com/#sorting you will get the answer :slight_smile:
enjoy :slight_smile:

3 Likes
12

I personally think that merge sort is the best sorting algorithm…

1 Like
13

yup! its little bit slower than quick sort but it is stable algorithm :slight_smile:

14

I think merge sort is best algorithm for large array. It time complexity O(n log(n) at worst case and space complexity is O(n) at worst case. Merge sort is the clear winner in terms of speed.

15

It is the Quick sort …fastest and best

16

The best sorting algorithms work on the divide and conquer rule. if any algorithm has O(nlogn) complexity then it is considered good as there is no other sorting algorithm that gives complexity less than O(nlogn).

Various sorting algorithms are-

Bubble sort : complexity of O(n^2).

Quick sort : worst case complexity is O(n^2) when array is already sorted.
average case complexity is O(n*logn).

Merge sort : complexity is O(n*logn) but it requires extra space. Thus, space complexity is more.

Randomised Quick sort : it partitions the array at a random chosen pivot and statistically it is gives O(n*logn) for any kind of input. it does not require any extra space.

Conclusion : According to me Randomised Quick sort is the best sorting algorithm.