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]
markdown guide
 

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.

 

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

 

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

 
 

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

 

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?

 

O(n²) 😧 Check out TimSort , optimized version of MergeSort with O(N*LOG(N)) worst-case complexty.

Tim Peters created Timsort for Pytho 😍

code of conduct - report abuse