Quicksort Algorithm

The Quicksort Algorithm is a randomized divide and conquer algorithm sorting algorithm.

• Context:
  • It can be implemented by a Quicksort-based Sorting System.
• Example(s):

function qsort!(a,lo,hi)
   i, j = lo, hi
   while i < hi
       pivot = a[(lo+hi)>>>1]
       while i <= j
           while a[i] < pivot; i = i+1; end
           while a[j] > pivot; j = j-1; end
           if i <= j
               a[i], a[j] = a[j], a[i]
               i, j = i+1, j-1
           end
       end
       if lo < j; qsort!(a,lo,j); end
       lo, j = i, hi
   end
   return a
end

• Counter-Example(s):
  • Bubblesort.
  • Mergesort.
• See: Las Vegas Algorithm.

---

---

References

2012

• http://en.wikipedia.org/wiki/Quicksort
  • QUOTE: 'Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes [math]\displaystyle{ {O}(n\log n) }[/math] comparisons to sort n items. In the worst case, it makes [math]\displaystyle{ {O}(n^2) }[/math] comparisons, though this behavior is rare. Quicksort is often faster in practice than other [math]\displaystyle{ {O}(n\log n) }[/math] algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only [math]\displaystyle{ {O}(\log n) }[/math] additional space.

    Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort.

2017

• https://github.com/JuliaLang/julia/blob/master/test/perf/perf.jl

function qsort!(a,lo,hi)
   i, j = lo, hi
   while i < hi
       pivot = a[(lo+hi)>>>1]
       while i <= j
           while a[i] < pivot; i = i+1; end
           while a[j] > pivot; j = j-1; end
           if i <= j
               a[i], a[j] = a[j], a[i]
               i, j = i+1, j-1
           end
       end
       if lo < j; qsort!(a,lo,j); end
       lo, j = i, hi
   end
   return a
end

1962

• (Hoare, 1962) ⇒ C. A. R. Hoare. (1962). “Quicksort.” In: The Computer Journal 1962 5(1) doi:10.1093/comjnl/5.1.10
  • ABSTRACT: A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper.

---