Quicksort

Implementation

Quicksort, also known as the partition-sort, is among the many computing inventions of British computer scientist Tony Hoare. Though it has not gone unadjusted since its inception in the 1960s, the basic algorithm remains the same. Quicksort sorts elements by comparing their values as less than, greater than, or equal to a chosen pivot value in the range. Here is the simple, generalized pseudocode version of the algorithm:

function quicksort(array)

   less, equal, greater := three empty arrays

   if length(array) > 1

      pivot := select any element of array

      for each x in array

         if x < pivot then add x to less

         if x = pivot then add x to equal

         if x > pivot then add x to greater

         quicksort(less)

         quicksort(greater)

   array := concatenate(less, equal, greater)

-Pseudocode taken from RosettaCode

See the pseudocode algorithm above in action in this gif that portrays each step of sorting the array [5, 2, 1, 3, 7, 6, 4] using quicksort:

Speed

On average, an array will need to be partitioned log n times (where n is the number of elements in the array). Since each pass goes through every element to compare them to the pivot value, each pass takes O(n) time. Therefore, putting the two together means the quicksort algorithm above has O(n log n).

The performance of quicksort hinges on how one chooses the pivot value. While easiest to pick the first value blindly, as in the above example, this can lead to a worst-case scenario of O(n²) time (the worst-case being an already-sorted list). There are various ways to choose the pivot value to avoid this, including random selection and taking the median of 3 elements in the array, but none can guarantee the O(n log n) running time - just make it much more probable. Ideally, a pivot value creates sub-arrays of equal length; at worst, it creates empty ones.

Compared to mergesort, another highly popular sorting algorithm that runs in O(n log n) time, quicksort is often faster in practice despite doing more comparisons, though mergesort is likely the better performer for arrays that are already partially-sorted. In summary, as the online Perl documentation claims, "quicksort is often faster for small arrays, and on arrays of a few distinct values, repeated many times"¹.

 

Reference:

1. Perl (). Sort. [ONLINE] Available at: http://perldoc.perl.org/sort.html. [Last Accessed 14/04/2014].

© BrainMass Inc. brainmass.com April 28, 2024, 9:30 am ad1c9bdddf