You are not logged in. Please login at www.codechef.com to post your questions!

×

Sorting algorithm

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

asked 22 Jan '13, 23:39

praveen_kishor's gravatar image

1★praveen_kishor
40111313
accept rate: 0%


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 .

link

answered 22 Jan '13, 23:44

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

edited 23 Jan '13, 01:01

Thanks Vineet....

(23 Jan '13, 00:13) praveen_kishor1★

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).

(10 Mar '13, 05:48) kullalok2★

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

link

answered 25 May '13, 17:20

chandan11111's gravatar image

3★chandan11111
3.6k133555
accept rate: 10%

edited 25 May '13, 19:13

1

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

(26 May '13, 13:22) p_coder2★

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

(26 May '13, 13:28) chandan111113★

Hello @praveen_kishor,

This problem:

Turbo Sort

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

link

answered 22 Jan '13, 23:45

kuruma's gravatar image

3★kuruma
17.6k72143209
accept rate: 8%

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/

link

answered 23 Jan '13, 00:38

ani94's gravatar image

2★ani94
5292410
accept rate: 5%

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

(23 Jan '13, 00:54) praveen_kishor1★
1

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.

(23 Jan '13, 01:02) anton_lunyov ♦6★

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 .

(23 Jan '13, 01:03) ani942★
1

@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)

(23 Jan '13, 09:34) sidhantgoyal5★

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.

link

answered 12 Nov '16, 21:03

rashedcs's gravatar image

2★rashedcs
49751553
accept rate: 4%

It is the Quick sort ...fastest and best

link

answered 10 Apr '17, 22:49

divyanshu_shuk's gravatar image

2★divyanshu_shuk
411
accept rate: 0%

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.

link

answered 10 Apr '17, 23:06

karan10xb's gravatar image

2★karan10xb
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,643
×836
×833
×770

question asked: 22 Jan '13, 23:39

question was seen: 5,541 times

last updated: 10 Apr '17, 23:06