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

×

Fastest sorting algorithm .

2
1

Which is the fastest sorting algorithm?

asked 10 Nov '16, 00:29

rashedcs's gravatar image

1★rashedcs
4871525
accept rate: 4%


Inbuilt function of sort available in "algorithm" header file of C/C++.. sort() are much faster than any other implemented sort!!

link

answered 10 Nov '16, 00:44

bansal1232's gravatar image

4★bansal1232
2.6k112
accept rate: 16%

Merge Sort is the fastest stable sorting algorithm with worst-case complexity of O(nlogn), but it requires extra space. Although, if memory constraints are very tight you can use Quick Sort, whose worst-time compelxity is O($n^{2}$) but average case complexity is O(nlogn).
A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.



If you feel your question has been answered, mark it as accepted.

link

answered 10 Nov '16, 00:44

srd091's gravatar image

5★srd091
1.5k111
accept rate: 42%

Answer is hidden as author is suspended. Click here to view.

answered 10 Nov '16, 17:22

pkien's gravatar image

4★pkien
(suspended)
accept rate: 12%

edited 10 Nov '16, 17:23

For competitive programming purposes, the standard library sort() should do just fine. In C++ it is an implementation of introsort. Mergesort is often not a great candidate because of all the extra memory used.

On a side note, there is a sorting algorithm, block sort, that:

  • Uses O(1) extra memory
  • Is stable
  • Runs in O(N log N) in worst case
  • Runs in O(N) in best case
link

answered 25 Nov '16, 18:05

wefgef's gravatar image

0★wefgef
3123
accept rate: 14%

This is a good link for time complexity of various algorithms and data structures.

http://bigocheatsheet.com/

link

answered 24 Nov '16, 23:58

mathecodician's gravatar image

5★mathecodician
2.6k320
accept rate: 8%

link

answered 10 Nov '16, 00:48

kay_kay's gravatar image

4★kay_kay
1.2k218
accept rate: 20%

1)Merge Sort is unarguably the fastest sorting algorithm with a worst-case complexity= O(n logn) . This means that whatever be the arrangement of the elements in the array, it won't take more than n*logn steps to sort the array. A standard computer generally takes 1 second to perform 10^8 such steps/operations. An important point to note here is that the base of the logarithm is 2 and not 10 or e as generally taken in schools. The only disadvantage of Merge Sort is that it requires extra space , i.e. an extra array to merge the sorted elements into. This is important to know because sometimes additional space has a great cost attached with it.

2)Quicksort is usually the sorting algorithm that is used everywhere. A few examples of this would be the inbuilt java, C++ sorting functions, MS Excel ,etc. Quicksort has an average worst-case complexity of O(n logn) but a worst-case complexity of O(n^2). However, this only occurs when the array is already sorted and can be overcome by randomizing the position of the pivot everytime. This is a very convenient technique since it does not have the additional cost of an entire new array.

link

answered 25 Nov '16, 00:27

akashbhalotia's gravatar image

3★akashbhalotia
39910
accept rate: 0%

edited 26 Nov '16, 23:31

I use sorted().This is built-in in Python and is over 4 times faster than other sorting techniques.

link

answered 26 Nov '16, 11:15

bkishan29's gravatar image

0★bkishan29
262
accept rate: 25%

I think that a.sort() and sorted(a) have the same time complexity. Both use Tim Sort and I don't it's like 4 times faster or anything like that but it has a best case time complexity of O(n).

(26 Nov '16, 11:44) mathecodician5★

Well there's no de facto 'fastest sorting algorithm (Else there'd be just one sorting algorithm and everybody would've used that). It all depends on how the input data is.

  • If the array is nearly sorted, then Insertion sort, Selection sort would be the algorithm of my choice.
  • If I already know the input elements range, eg. If I want to sort 1 billion characters, I know there're just 26 unique elements, I'd go with Counting sort
  • If I'm sorting objects, I want the sort to be stable. I'd use Java's Collections.sort() which internally uses Tim Sort
  • If I'm just sorting random numbers of which I have no data about(eg. range), I'd use Java's Arrays.sort() which uses Double Pivoted Quick sort
link

answered 26 Nov '16, 19:32

lawliet_yagami's gravatar image

3★lawliet_yagami
312
accept rate: 0%

in java Arrays.sort(arr_name);

link

answered 26 Nov '16, 18:07

app_geek's gravatar image

1★app_geek
1
accept rate: 0%

fastest sorting algorithm will be the merge sort.since the time complexity is less even in the worst case(nlogn).Even if the array is properly arranged or not,it wouldn't take more than nlogn steps to sort the array.

link

answered 26 Nov '16, 20:15

sanah's gravatar image

0★sanah
1
accept rate: 0%

C++ STL sort function is fastest. If you want your own implementation then randomized quick sort and heap sort are really good candidates as they are universal unlike radix sort which is O(n) but demands keys in lexicographic order.

Thus, overall inbuilt sort functions are quite fast and are thus widely used

link

answered 24 Feb, 12:48

inovation123's gravatar image

4★inovation123
4236
accept rate: 11%

Dear, don't take it in wrong way, but the Q was asked last year, and already answered. Even what you said about C++ stl is what bansal said in his accepted answer. I know you want to help, but I don't think bumping these 3-4 month old thread would be that helpful (many OPs wont be around now, or even they are ,chances are they might have already found the answers). Just take care that you don't bump to the extent that threads more closer to current affairs get neglected.

I hope I put my point across amicably.

(24 Feb, 14:55) vijju123 ♦5★

I totally agree with you mate. Thanks

(24 Feb, 15:02) inovation1234★
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:

×773

question asked: 10 Nov '16, 00:29

question was seen: 7,315 times

last updated: 24 Feb, 15:02