Explore BrainMass
Share

Explore BrainMass

    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(n2time (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"1.

     

    Reference:

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

    © BrainMass Inc. brainmass.com April 2, 2020, 9:35 pm ad1c9bdddf

    BrainMass Solutions Available for Instant Download

    Create a Java Program To Compare Two Search Algorithms

    Write a Java application that performs the following task: - Create an int array (you can declare the values yourself, or use the Random feature in java to create this array). - Sort the data. - Prompt user to input an integer from the keyboard. - Search for the user input value in the array created in step 1 using a simpl