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

×

# Sorting algorithm

 3 which is the best sorting algorithm for a large array ?? asked 22 Jan '13, 23:39 40●11●13●13 accept rate: 0%

 8 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 . answered 22 Jan '13, 23:44 12.4k●47●107●171 accept rate: 12% Thanks Vineet.... (23 Jan '13, 00:13) 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★
 6 check out this http://bigocheatsheet.com/#sorting you will get the answer :) enjoy :) answered 25 May '13, 17:20 3.6k●13●35●55 accept rate: 10% 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)
 4 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 answered 22 Jan '13, 23:45 3★kuruma 17.6k●72●143●209 accept rate: 8%
 2 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/ answered 23 Jan '13, 00:38 2★ani94 529●2●4●10 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) 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) 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)
 0 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. answered 12 Nov '16, 21:03 2★rashedcs 497●5●15●53 accept rate: 4%
 0 It is the Quick sort ...fastest and best answered 10 Apr '17, 22:49 41●1 accept rate: 0%
 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. answered 10 Apr '17, 23:06 11 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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