Quicksort Algorithm

From GM-RKB
Jump to navigation Jump to search

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

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


References

2012

  1. S. S. Skiena, The Algorithm Design Manual, Second Edition, Springer, 2008, p. 129
  2. "Data structures and algorithm: Quicksort". Auckland University. http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html. 

2017

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.