Shakersort vs. Quicksort

[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.

[ComedyNaruto]

this animation is cool^^

[T0B0KKE]

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

[spechtbert]

@T0B0KKE rofl.

[T0B0KKE]

@spechtbert It's the truth.

[spechtbert]

@T0B0KKE sure.

[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.

[Magnetohydrodynamics]

If you want interesting sorts, look into Smoothsort.

[putzmitt3l]

is the other sort tweeked selection sort ??? far more interesting than selection... still Quick is quick for the quicksort :P

[dented42]

@putzmitt3l It looks to me like its a kind of bubble sort, only it goes is two directions.

[thaimodz]

@dented42 Yes. Shakersort is bidirectional bubblesort.

[Mank25]

Quicksort's quick, yeah yeah yeah!

[woo216]

@Mank25 fuck off ive invented a sort quicker than quicksort but im gonna release it after my patent has been processed my new way to sort is gonna change the world wait and see

[BushHatesMe]

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

[someonerules]

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

[skkissjanos]

nice;)