Shakersort vs. Quicksort

Shakersort vs. Quicksort

Category:

Science & Technology

Tags:

• opengl
• quicksort
• shakersort

[Mank25]

Quicksort's quick, yeah yeah yeah!

[thaimodz]

@dented42 Yes. Shakersort is bidirectional bubblesort.

[someonerules]

@BushHatesMe I love replying to 2 year old comments too!

[BushHatesMe]

@Mank25 It's not slow,no no no!

[CMark342]

@blauhuden111

I just wrote a quicksort, it is extremely easy to avoid O(n^2) perf on presorted, or reverse sorted arrays.

Only the most naive implementations will behave that way.

Also, memory usage should be controlled by using a stack to eliminate recursion overhead and modifying the algorithm to be an in place sort instead of using 2 separate arrays for the high and low values.

You are correct that the basic recursive quicksort algorithm will behave badly in this case though.

[blauhunden111]

@spechtbert No really, quicksort uses a lot of memory when fed a fully-sorted or mostly-sorted array. Look it up. quicksort has a O(n^2) if it's sorting a presorted array.

[spechtbert]

@T0B0KKE sure.

[T0B0KKE]

@spechtbert It's the truth.

[spechtbert]

@T0B0KKE rofl.

[ComedyNaruto]

this animation is cool^^

[T0B0KKE]

quicksort sucks if the data is already close to being sorted... and it uses loads of memory.

[Magnetohydrodynamics]

If you want interesting sorts, look into Smoothsort.