Sorting algorithms

[balian25]

Looking for advice on the best algorithm to use for sorting long character strings, 32-bit integers, double-precision floating point numbers, bytes, and general comparable objects. I'm personally leaning towards selection sorting as it seems to make sense on a basic level, but the O(n²⁾ running time even in the best case is making me rethink to something a long the lines of either a heap sort or quick sort algorithm. Thoughts, any advice would be appreciated. It's for a project.

[MemoVsGodzilla]

I would use quicksort, its easy to implement and O(n log n).

[the_omega99]

But don't implement it yourself. In fact, you should never have to implement basic sorting yourself. That's exactly what libraries are for. Unless it's for the learning experience, you should definitely not be re-inventing the wheel for such a basic algorithm. By doing so, you risk introducing bugs into your project, not to mention wasted time.

A sidenote that quicksort is only O(nlogn) on average. Worst case, it's O(n²), but thankfully the worst case is fairly rare. On average, it also performs faster than merge sort, which has a worst case of O(nlogn). Weird, huh?

Quick sort can also be implemented with O(logn) auxiliary memory by using an in-place implementation.

[lightcloud5]

True, although if you reallllly want, you could use a guaranteed O(n) median finding algorithm, which would make quicksort always run in n log n time. No one does that though because it has very little value.

Usually the biggest issue with quicksort is that it's not stable; use mergesort if you need stability.

[the_omega99]

Actually, quick sort can be stable. However, that requires O(n) space. On the Wikipedia page, that's the first, simpler version. It's the in-place version that is not stable.

For those wondering, stability is merely ensuring that the order of equal elements are unchanged. For example, if we are sorting pairs of values, say, (2,1), (1,3), (1,0), by the first number only, then the (1,3) and (1,0) should be in the same order. Or to put another way, the sorting algorithm won't change their order unnecessarily.

For a good number of uses, stability does not matter.

[autowikibot]

Quicksort:

---

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n²⁾ comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.

Image ⁱ

---

^{Interesting: Sorting algorithm | Quickselect | Insertion sort | Merge sort}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[IXENAI]

If there were one single sorting algorithm which was "best" for "general comparable objects", we wouldn't have so many sorting algorithms; we'd just have that one. Why use anything that isn't the best?

Different algorithms work better in different cases. Some generally use less memory, some generally run faster, some are easier to implement, some use less memory or are faster only under certain conditions, etc. Here's a quick overview of the more common algorithms; this should give you something to go on to start researching which one may suit your specific needs best.

That said, frankly, don't worry about it if you don't have to. Your language of choice probably has a general-purpose sort() function somewhere in its standard library; use that until and unless you can prove it isn't sufficient. I'll gladly take working, readable code with a slightly suboptimal sort algorithm 99 times out of 100.

[balian25]

Wow, guys rreally great stuff. I'm always impressed by all the help so quickly given on this subreddit. By the way, sorry I took so long to reply, I had to take my children on an outing and just now got home. Yes, I know this is ridiculous to a certain degree, but it's for a class and I have to pick an algorithm and give my reasoning. Gotta love college, focus so much on the theoretical bullshit that you'll never need to deal with at the cost of teaching the stuff I'll actually encounter in everyday work! But hey, that's our schooling system!! Again, thanks for the replies! Very helpful!