DEV Community

What is Quicksort

Muhammed H. Alkan on November 02, 2018

Quicksort is a popular and common sorting algorithm that known to be really efficient. It createn 1959, and published in 1961 by Tony Hoare (He's k...
Read full post
Collapse
 
tux0r profile image
tux0r • • Edited

Despite the name, the quick sort algorithm has a worst-case complexity of O(n²). You might or might not want to try merge sort instead, depending on the size (and sorting state) of your list.

Collapse
 
grayjack profile image
GrayJack •

Or you could select a random element to be the pivot, that way you reduce a lot the chances of waving the worst case

Collapse
 
lyfolos profile image
Muhammed H. Alkan •

Add it!

Collapse
 
lyfolos profile image
Muhammed H. Alkan •

Thanks for reminding me! I just forgot to add it.

Collapse
 
chenge profile image
chenge •

quicksort in Ruby. Short and clear.

def qs a
  (pivot = a.pop) ? 
    qs(a.select{|i| i <= pivot}) + [pivot] + qs(a.select{|i| i > pivot}) :
    []
end
Collapse
 
lyfolos profile image
Muhammed H. Alkan • • Edited

I just tried to make it more readable for beginners. I can do oneliner in Python and OCaml too.

qs = lambda a: [] if not a else qs([n for n in a if n < a[0]]) + [a[0]] + qs([n for n in a if n > a[0]])

It's still readable, IMO.

So?