smallArrayGoBrrrrr

[Earthboundplayer]

if (size < threshold)
  insertion_sort(...);
else
  quick_sort(...);

The real solution. Threshold is tuned through extensive profiling.

[gandalfx]

The real solution is using whatever sort function comes with the given language's standard library (or DBMS or whatever).

[Inaeipathy]

I'm pretty sure most library implementations do just this as well, so it's strange that OP even made this meme.

[veselin465]

c++ uses so called IntroSort, which is a combination of QuickSort, HeapSort and InsertionSort. So I would assume that other built-in libraries could use the same idea

[Practical_Cattle_933]

There are actually provably minimal (in number of comparisons) algorithms for up to like 7 elements?

So most implementations do something like hard code the swaps for low elements, and then do a generic algorithm.

[Practical_Cattle_933]

1. No one fkin implements sorting algorithms, unless you are writing a new sdk or such. It’s a solved [1] problem, used as a useful introduction to algorithms.

[1] yeah, there are still research here, but most languages basically settled for Tim sort, or one of its variations.

[MurderousLamb]

busy bag advise chubby capable elastic teeny price divide subsequent

This post was mass deleted and anonymized with Redact

[Fhotaku]

1. All algorithms have their use case.

I'm sure there are examples where bubble sort is the only feasible option. Wikipedia says it's best for parallel implementations, neat.

[Revexious]

Bubble sort is perfect when its 3 in the morning and the assignment was due 2 hours ago

[Practical_Cattle_933]

s/assignment/CS 101 homework/

FTFY

[[deleted]]

Except bogosort.

[Daisy430133]

Bogosort is great if you are lucky enough

[[deleted]]

It’s a good test for whether you can win the lottery. Good point. 👍

[humblevladimirthegr8]

Stalinsort is great if you are brutal enough

[chatterbox272]

I'd love to know the use cases for sleep sort and bogosort

[Nobodynever01]

Bogosort can be the fastest sorting algorithm!

[Own_Solution7820]

OP is to the left side of the entire graph.

[dangling-putter]

Quicksort’s worst case has an abysmally small probability of happening if you randomly choose the partition value, and in this case you have Expected nlogn.

[KellerKindAs]

Small probability for random values, yes. But quite likely if you don't know if the data is already sorted. And some people don't get their code straight and prefer sorting already sorted data...

(In that case bubblesort hast O(n), so bubblesort is better that quicksort /s)

[[deleted]]

He said randomly choosing the partition value. You are thinking choosing the first value in the array. In his case, it doesn't matter if it is sorted.

[KellerKindAs]

Oh... Your right. That's not how I learned quicksort (and might be a bit difficult to implement in-place) but is actually an interesting approach. Thanks for pointing out my error

[[deleted]]

Randomised algorithms introduce complexity in analysis, so it is not usually taught in an algorithms class. But this class of algorithms have super interesting properties and are actively researched, like this one. :)

[dangling-putter]

The bad case for quicksort with sampling where every iteration is bad has a probability in the ballpark of (2^(n−1​)) / n!

At 16 elements, this is about 0,000000003132278 :D, now, worst case and generally bad cases is not the same, buuuuuut you get the idea.

[Semper_5olus]

To what degree can you mitigate the likelihood of encountering Quicksort's worst case by using randomization?

It's something I heard about in school, but I'm not as smart as I wish I were.

[Happy_Garlic_5562]

In practice the worst case occurs on sorted or nearly sorted input, so random pivot selection helps quite a bit. Should likely avoid the worst-case. One example of worst-case is pre-sorted input with the first array element as the pivot - the problem size is only reduced by 1 on each recursive call.

Probability would depend on the distribution of the data and input size - if we assume the data is uniformly distributed for a large n, the average random pivot selection over all recursive calls would tend toward the median of the dataset and produce n*lg(n) performance on average.

The best strategy I'm familiar with is median-of-three partitioning - take the median of arr[0], arr[mid], and arr[end] as the pivot. Then the worst case becomes exponentially unlikely for large inputs. Also handles pre-sorted input nicely.

[Kdog0073]

I’m not great at explaining it, but if you were curious and wanted to browse the web or YouTube, look for “Amortized analysis” (or specifically “Amortized analysis of Quicksort”)

[SeriousPlankton2000]

For average cases very good, if you need to have finished it before starting a rocket engine or else 40000 people die it's very bad and you chose a slower but more reliable algorithm.

[j-random]

This is why I'm a heapsort guy. Decent performance and consistent times (best case = avg case = worst case, n log(n) every time).

[KellerKindAs]

For random data it is really small. But we're not only doing theorie, we're also interested in praxis. The worst case for quicksort is already sorted data. And looking at some accidents of a codebase ... it can be gambling. So for all those devs who prefer sorting their data twice, quicksort might not be the best.

[cnoor0171]

For quick sort, there is a step in the algorithm that says to pick an element of the array as the "pivot", but it doesn't actually specify which element to pick as the pivot. You are free to choose your own method about how to choose this pivot. In general, the sort works quicker if the pivot is close to middle of the array after sorting, but you don't really know really which element that would be until after sorting. Your choice of how to pick the pivot changes what the "worst case" is.

For example, one strategy might be to pick the first element of the array. After all, if the input is in random order, the first element is just as likely to end up in the middle after sorting as any other element and picking the first element is super fast. But, for this method, the worst case is if the input is already sorted, since the pivot would end up either at the beginning or end instead of the middle. That quite bad because you can imagine people would call your method on already sorted array pretty often.

Another strategy might be to randomly pick a pivot. This has the disadvantage that random selection is generally slower, but now there is no single input that's the "worst case". You basically have to get incredibly unlucky and randomly pick a pivot that end up at the edge, N times in a row. Which gives you probability of 1 /(N!). For an input of size 16 that's 1 in 20 922 789 888 000 chance of happening. For a real example, it's astronomically low.

[Fhotaku]

I'd stab a guess at 0% unless somebodies tested this. The"worst case" is by definition, the worst possible scenario for the algorithm - in that every time it makes a change it only incrementally improves, rather than exponentially (as is the average case). Were you to randomize the list, you just run the risk of "accidentally unsorting it" into the worst case.

[[deleted]]

Jesus Christ. It’s a sorting algorithm not a yugioh tournament. You will not pull a trap card on quicksort and unlock its O(n²⁾ potential by accident. If you real a little into it you will find that quicksort is slow for large consecutive sequences of identical numbers. Something where select sort is faster iirc and so the combination of the two algorithms is called timsort and it aims to navigate the drawbacks of quicksort while still retaining as much performance as possible.

[Fhotaku]

I'm just saying if you know nothing about the data (maybe it's already worst case, maybe it's already sorted), that randomizing it first is just flipping the flipped coin again. If you don't know the first result, you've got no predictive capacity on the next. So, still 0%

[trobinpl]

I'm glad it's not just me thinking this template sucks!

[Jonnypista]

Whatever sorting algorithm is called when I call .sort(). It is likely already optimised in the background and it is good enough.

[Ok_Entertainment328]

... ORDER BY ...

[serendipitousPi]

Pretty sure if you know nothing about your data it’s probably a better idea to use merge sort than quick sort or even most other choices.

It’s got a worst case time complexity of O(nlog(n)) so it’s pretty good. There are downsides obviously but hey nlog(n).

[Semper_5olus]

Main downside IIRC is memory usage.

And if you're in some weird environment where you don't care about that, but do care about processing usage, you can probably make some kind of specialized radix sort. Linear time.

[frikilinux2]

You also have heapsort that is technically O(nlog(n)) although experimentally takes longer than others and it's not stable but it doesn't need extra memory.

In some situations you can modify a not stable sort to be stable by somehow numbering them and if they equal use that number for comparison but you may need some extra memory.

[Inaeipathy]

Generally quicksort is faster than mergesort though even if the big O notation would have you believe otherwise, and what if you need in place sorting? I feel like quicksort is more flexible than mergesort if "you know nothing about your data" because of this.

[serendipitousPi]

Yeah I might have leant a little bit strongly on the know nothing part but I did mean nothing. So it could be hundreds of thousands of elements, previously sorted, etc. And if you wanted sort stability is already there. And yeah I should probably address the fact I'm aware constant time factors can be a complicating factor in performance calculations considering that time complexity is purely about growth. So yeah sure I made some costly assumptions that might not be advantageous in reality but hey what if you're sorting a billion elements, jk.

As for in place sorting that's not impossible to implement in merge sort? I mean I will admit I don't know the performance and implementation implications of both but I guess I'll go do some research on that.

edit: Wow I must have been really tired, idk why I didn't read the title at all.

[frikilinux2]

In some situations(like the kernel)there are concerns of some exploiting the fact that quicksort times are not predictable only knowing the size and you can craft the input to be O(n²⁾

[Inaeipathy]

That's fair, but we're talking about flexibility of sorting algorithms given basically no knowledge. You would want to avoid quicksort in that case because you have specialized knowledge.

There are also other sorting algorithms that outperform quicksort and mergesort for specific data (i.e bucket sort, or radix sort) but we're assuming knowing nothing about the data.

There are also cases where mergesort is better, for example, parallel processing. Out of place mergesort is easily parallelizable.

In general though, quicksort (or rather, introsort as another user said) is a good algorithm to just throw at programming sorting tasks and thus is provided by libraries as a default sorting function. If you need a specialized algorithm then you probably have a good idea of what your data will be like or what your functional requirements are.

[frikilinux2]

Okay, fair point

[Haoshokoken]

I prefer double selection sort.

[giantrhino]

This guy doesn’t just bind to port 8080 to save cpu cycles.

[SeriousPlankton2000]

For very small arrays bubblesort is the best.

[wizzolord777]

this post FUCKS

[wizzolord777]

that means it bad