CODEWITHSUNDEEP
algorithm
asd
asd

Reputation: 225

why we are always using quick sort ? or any specific sorting algorithm?

why we are always using quick sort ? or any specific sorting algorithm ??

i tried some experiment on my PC using quick,merge,heap,flash sort

results:-

sorting algorithm : time in nanosecond -> time in minutes

quick sort time : 135057597441 -> 2.25095995735

Flash sort time : 137704213630 -> 2.29507022716667

merge sort time : 138317794813 -> 2.30529658021667

heap sort time : 148662032992 -> 2.47770054986667

using java in built function

long startTime = System.nanoTime();

given times are in nanoseconds there hardly any difference between them if we convert them into seconds for 20000000 random integer data and max array size is 2147483647 in java.if we are using in-place algorithm then there may be difference of 1 to 2 min till max array size.

if the difference is too small why we should care ??

Upvotes: 5

Views: 2211

Answers (4)

Richard
Richard

Reputation: 61259

Correctness. While switching between sort algorithms might offer speed-ups under some specific scenarios, the cost of proving that algorithms work can be quite high.

For instance, TimSort, a popular sorting algorithm used by Android, Java, and Python, had an implementation bug that went unnoticed for years. This bug could cause a crash and was easily induced by the user.

It took a dedicated team "looking for a challenge" to isolate and solve the issue.

For this reason, any time a standard implementation of a data structure or algorithm is available, I will use that standard implementation. The time saved by using a smarter implementation is rarely worth uncertainty about the implementation's security and correctness.

Upvotes: 0

user2864740
user2864740

Reputation: 61865

All of the algorithms presented have a similar average case bounds, of O(n lg n), which is the "best" a comparison sort can do.

Since they share the same average bounds, the expected performance of these algorithms over random data should be similar - which is what the findings show. However, the devil is in the details. Here is a very quick summary; follow the links for further details.

Quicksort is generally not stable (but there are stable variations). While quicksort has an average bounds of O(n lg n), Quicksort has a worst case bounds of O(n * n) but there are ways to mitigate this. Quicksort, like heapsort, is done in-place.

Merge-sort is a stable sort. Mergesort has a worst case bounds of O(n lg n) which means it has predictable performance. Base merge-sort requires O(n) extra space so it's generally not an in-place sort (although there is an in-place variant, and the memory for a linked list implementation is constant).

Heapsort is not stable; it also has the worst case bounds of O(n lg n), but has the benefit of a constant size bounds and being in-place. It has worse cache and parallelism aspects than merge-sort.

Exactly which one is "best" depends upon the use-case, data, and exact implementation/variant.

Merge-sort (or hybrid such as Timsort) is the "default" sort implementation in many libraries/languages. A common Quicksort-based hybrid, Introsort is used in several C++ implementations. Vanilla/plain Quicksort implementations, should they be provided, are usually secondary implementations.

Merge-sort: a stable sort with consistent performance and acceptable memory bounds.

Quicksort/heapsort: trivially work in-place and [effectively] don't require additional memory.

Upvotes: 8

BartoszKP
BartoszKP

Reputation: 35891

Your conclusion is correct: most people that do care about this in most situations waste their time. Differences between these algorithms in terms of time and memory complexity become significant in a particular scenarios where:

  • you have huge number of elements to sort

  • performance is really critical (for example: real-time systems)

  • resources are really limited (for example: embedded systems)

(please note the really)

Also, there is the concern of stability which may be important more often. Most standard libraries provide stable sort algorithms (for example: OrderBy in C#, std::stable_sort in C++, sort in Python, sort methods in Java).

Upvotes: 1

user1864610
user1864610

Reputation:

We rarely need to sort integer data. One of the biggest overheads on a sort is the time it takes to make comparisons. Quicksort reduces the number of comparisons required by comparison with, say, a bubble sort. If you're sorting strings this is much more significant. As a real world example some years ago I wrote a sort/merge that took 40 minutes with a bubble sort, and 17 with a quick sort. (It was a z80 CPU a long time ago. I'd expect much better performance now).

Upvotes: 2

Related Questions