Introduction to Recursive Programming by Manuel Rubio-Sanchez

Author:Manuel Rubio-Sanchez [Rubio-Sanchez, Manuel]
Language: eng
Format: azw3, pdf
Publisher: CRC Press
Published: 2017-10-05T04:00:00+00:00

6.2.2 The quicksort algorithm

The quicksort algorithmAlgorithm!sorting!quicksort is another method developed by Tony Hoare. It is based on the divide and conquer approach and receives its name due to its remarkable efficiency. Unlike the merge sort algorithm, its running time in the worst case is O ( n 2 ) . However, in the best and average cases it runs in Θ ( n log n ) time, and can be several times quicker than the merge sort algorithm in practice.

To understand the difference between both methods, observe that the decomposition in merge sort is easy. In particular, the input list can be divided in two halves by simply using appropriate index ranges (0:n//2 and n//2:n). However, combining the results of the subproblems requires solving yet another problem (merge) that is not immediately straightforward. In contrast, in the quicksort algorithm the decomposition is hard, but the combination stage is not only trivial, but may not even be necessary in some implementations.

Specifically, instead of simply dividing the list in two halves, quicksort’s decomposition transforms the input by using a partitioning scheme like the ones presented in Section 5.4. Figure 6.2 illustrates this type of decomposition, where the sublists within the original list are separated by a pivot (the sublist to the right of the pivot contains elements that are less than or equal to the pivot, and the sublist to the left is composed of numbers that are greater than the pivot). A concrete recursive diagram based on the previous decomposition could be:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.