Quicksort implementation in C++

Standard

This one among a thousand implementaions of the Quicksort algorithm.

Its runtime is O(n log(n)) since you divide each part into two and recursively sort the two parts (always splitting by 2 is logarithmic growth…).

You could optimize it by using Insertionsort for a small input vector (i.e. less than 50 elements). Additionally you can convert the recursive algorithm into a iterative one (maybe I will post this in the future).
You should be careful, and always pass the input vector per reference “&”. If you don’t sorting does not take effect on the input in the end.

Here is another implementation that works on plain integer arrays.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">