[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 28 KB, 400x300, QFquJ.png [View same] [iqdb] [saucenao] [google]
5764344 No.5764344 [Reply] [Original]

Why is Quick Sort faster than Merge Sort?
They both have the same algorithm complexity, O(n log n), so what's with quick sort coming out on top?

>> No.5764354

bump for interest

>> No.5764364

>>5764344
It is an in place sorting algorithm, so it is skipping the step in merge sort where a large portion of the list is being moved from one list to another.

Basically, merge sort just has more constant time complexity than quicksort.

>> No.5765089

smaller constant in front of n log n.

>> No.5765214

>>5764344

Actually quicksort is O(n^2).

>> No.5765221

>>5765089
This, plus there could be extra linear terms behind it.

>> No.5765305

>>5765214
Wrong, quicksort is O(n)

>> No.5765311

>>5765305
Where n = m^2 and you are comparing m things, yes it is.

>> No.5765343

>>5764344
Wow, I didn't notice at first, but nice troll. 10/10

>> No.5765349

>>5765343
what

>> No.5765401

>>5765349
Quicksort's complexity is O(n^2), yet it's pictured in the graph as faster than both heapsort and mergesort, which both are O(n log n).

>> No.5765417

Anyone care to share their wisdom or link to a place where q (n log n) / q(n^2) stuff is explained? :)

>> No.5765432

>>5765401
O(n^2) is the worst case. On average it is O(n log n)

>> No.5765455

>>5765417
Just look it up on wikipedia. It's under "big O notation".

Short version is, if something is O(f(x)), it means that once x gets sufficiently large, it is bounded from above by some constant * f(x).

So quicksort being O(n^2) means that for sufficiently large numbers of items to be sorted, it will always take equal or less than kn^2 units of time.

>> No.5765459

Random access memory isn't really random access. Caching stores copies of recently accessed blocks of memory in a location that is much faster to read from than regular memory. Quicksort makes very efficient use of the cache since the partition step is just a linear sweep over a (after a few steps, small) array. Mergesort "jumps around" more in memory and requires O(n) extra space rather than the O(log n) of quicksort, both which hurts cache performance.

This is a complicated topic, and a detailed analysis is beyond me.

>> No.5765464

>>5765459
The same phenomenon is the reason why "insert an element at position n" is much faster in a growable array than it is in a linked linked. All the cache misses during iteration through the linked list are so costly that copying the array is trivial in comparison.

>> No.5765474

>>5765459
Still, there are modifications you can make to mergesort that make it constant memory, at the cost of increasing the time complexity to O(n (log n)^2).

>> No.5765793

OP here, thanks for the answers, I get it.

>> No.5765825

>>5764344
it's not
Buble sort is the fastest in real life

>> No.5765834

>>5765825
>bubble sort
>fastest
lel. http://www.youtube.com/watch?v=k4RRi_ntQc8

>> No.5765848

>>5765825
le epic trolled xddd
u r! the master ruseman
le disney face xdddd

>> No.5765858

>>5765834
>>5765848

When the max displacement of the ideal position to the correct position is small and/or constant w.r.t. n, say k<<<n places, bubble sort runs in O(k*n) ≋ O(n) iterations. So if you're receiving data that already sorted but some packets get delayed, fixing it is better done by bubble sort.

>> No.5765865

>>5765858
bubble sorts average is n^2

>> No.5765866

>>5765858
If this is data you don't have full control over, you have a security issue.

>> No.5765867

>>5765865
It's like you didn't even read what he wrote.

>> No.5765887

>>5765825
>Why is Quick > Merge
>Its not because Bubble > Both

fuck am i reading

>> No.5765914

>>5765887

Run Quick sort on data that is in the reverse order gives O(n^2); slower than Merger

Basically, it all depends on the data sets [except insertion sort which always sucks].

>>5765866
What?

>> No.5765921

>>5765867
Of course not, that would require brain function which cs majors don't have. They just mindlessly parrot whatever they hear.

>> No.5765976

>>5765921
butthurt biology major who didn't get into med school detected

>> No.5765986
File: 62 KB, 500x888, 1327555555555.png [View same] [iqdb] [saucenao] [google]
5765986

>>5765976
nope

>> No.5766001

>>5765986
Easily the stupidest image I have ever seen on /sci/. Physics openly laughs in the face of mathematical rigor, and chemistry has never even pretended to be mathematically rigorous.

>> No.5766003

>>5766001
>taking a troll image on /sci/ seriously
>falling for the "biology is stupid" ruse
come back when your skin isn't paper thin

>> No.5766031

>>5765914
>What?
If you use a sorting algorithm with a horrible worst case, an attacker can craft an input sequence triggering that worst case. There have been several real world cases of this, with sorting and hashing being prime candidates for attack.

>> No.5766071

>>5766031
I'm talking about scientific computing, not web development crap. Plus, setting a timer to respond after is FAR better than wasting cpu time using shittier algorithms