Quicksort is the other important sorting algorithm that is based on the divide-and-conquer approach. Unlike mergesort, which divides its input elements according to their position in the array, quicksort divides them according to their value.

**Quicksort**

Quicksort
is the other important sorting algorithm that is based on the
divide-and-conquer approach. Unlike mergesort, which divides its input elements
according to their position in the array, quicksort divides them according to
their value. We already encountered this idea of an array partition in Section
4.5, where we discussed the selection problem. A partition is an arrangement of
the array’s elements so that all the elements to the left of some element ** A**[

Obviously,
after a partition is achieved, ** A**[

Here is
pseudocode of quicksort: call *Quicksort*** (A**[0

**ALGORITHM** *Quicksort*** (A**[

//Sorts a
subarray by quicksort

//Input:
Subarray of array ** A**[0

indices ** l** and

//Output:
Subarray ** A**[

**if ***l < r*

** s **←

*Quicksort*** (A**[

*Quicksort*** (A**[

As a
partition algorithm, we can certainly use the Lomuto partition discussed in
Section 4.5. Alternatively, we can partition ** A**[0

As
before, we start by selecting a pivot—an element with respect to whose value we
are going to divide the subarray. There are several different strategies for
selecting a pivot; we will return to this issue when we analyze the algorithm’s
efficiency. For now, we use the simplest strategy of selecting the subarray’s
first element: ** p** =

Unlike
the Lomuto algorithm, we will now scan the subarray from both ends, comparing
the subarray’s elements to the pivot. The left-to-right scan, denoted below by
index pointer ** i,** starts
with the second element. Since we want elements smaller than the pivot to be in
the left part of the subarray, this scan skips over elements that are smaller
than the pivot and stops upon encountering the first element greater than or
equal to the pivot. The right-to-left scan, denoted below by index pointer

After
both scans stop, three situations may arise, depending on whether or not the
scanning indices have crossed. If scanning indices ** i** and

**ALGORITHM** *HoarePartition*** (A**[

//Partitions
a subarray by Hoare’s algorithm, using the first element

as a pivot

//Input:
Subarray of array ** A**[0

indices ** l** and

//Output:
Partition of ** A**[

this function’s value

** p **←

** i **←

**repeat**

**repeat ***i*** **←** ***i*** **+** **1** until **** A**[

**until ***i*** **≥** ***j*

swap** (A**[

**return ***j*

Note that
index ** i** can go out of the subarray’s
bounds in this pseudocode. Rather than checking for this possibility every time
index

An
example of sorting an array by quicksort is given in Figure 5.3.

We start
our discussion of quicksort’s efficiency by noting that the number of key
comparisons made before a partition is achieved is ** n** + 1 if the scanning indices cross
over and

In the
worst case, all the splits will be skewed to the extreme: one of the two
subarrays will be empty, and the size of the other will be just 1 less than the
size of the subarray being partitioned. This unfortunate situation will happen,
in particular, for increasing arrays, i.e., for inputs for which the problem is
already solved! Indeed, if ** A**[0

So, after
making ** n** + 1
comparisons to get to this partition and exchanging the pivot

Thus, the
question about the utility of quicksort comes down to its average-case
behavior. Let ** C_{avg}(n)** be the
average number of key comparisons made by quicksort on a randomly ordered array
of size

Thus, on
the average, quicksort makes only 39% more comparisons than in the best case.
Moreover, its innermost loop is so efficient that it usually runs faster than
mergesort (and heapsort, another ** n** log

Because
of quicksort’s importance, there have been persistent efforts over the years to
refine the basic algorithm. Among several improvements discovered by
researchers are:

better
pivot selection methods such as ** randomized quicksort** that uses a
random element or the

switching
to insertion sort on very small subarrays (between 5 and 15 elements for most
computer systems) or not sorting small subarrays at all and finishing the
algorithm with insertion sort applied to the entire nearly sorted array
modifications of the partitioning algorithm such as the three-way partition
into segments smaller than, equal to, and larger than the pivot (see Problem 9
in this section’s exercises)

According
to Robert Sedgewick [Sed11, p. 296], the world’s leading expert on quicksort,
such improvements in combination can cut the running time of the algorithm by
20%–30%.

Like any
sorting algorithm, quicksort has weaknesses. It is not stable. It requires a
stack to store parameters of subarrays that are yet to be sorted. While the
size of this stack can be made to be in ** O(**log

**Exercises
5.2**

** **1. Apply quicksort to sort the list ** E, X, A, M, P , L, E** in
alphabetical order. Draw the tree of the recursive calls made.

2. For the partitioning procedure outlined in this section:

**
**Prove that if the scanning indices stop while
pointing to the same element, i.e., ** i** =

**
**Prove that when the scanning indices stop, ** j** cannot point to an element more
than one position to the left of the one pointed to by

**
**Give an example showing that quicksort is not a
stable sorting algorithm.

**
**Give an example of an array of ** n** elements for which the sentinel
mentioned in the text is actually needed. What should be its value? Also
explain why a single sentinel suffices for any input.

**
**For the version of quicksort given in this section:

**
**Are arrays made up of all equal elements the
worst-case input, the best-case input, or neither?

**
**Are strictly decreasing arrays the worst-case
input, the best-case input, or neither?

**
****a. **For
quicksort with the median-of-three pivot selection, are strictly increas-ing
arrays the worst-case input, the best-case input, or neither?

**
**Answer the same question for strictly decreasing
arrays.

**
****a. **Estimate
how many times faster quicksort will sort an array of one million** **random numbers than insertion sort.

**
**True or false: For every ** n >** 1

Design an
algorithm to rearrange elements of a given array of ** n** real
num-bers so that all its negative elements precede all its positive elements.
Your algorithm should be both time efficient and space efficient.

**
****a. **The** Dutch
national flag problem **is to rearrange an array of characters

**
**Explain how a solution to the Dutch national flag
problem can be used in quicksort.

**
**Implement quicksort in the language of your choice.
Run your program on a sample of inputs to verify the theoretical assertions
about the algorithm’s efficiency.

*11. Nuts and bolts *You are given a collection of* **n** *bolts of different widths and* *** n
**corresponding
nuts. You are allowed to try a nut and bolt together, from

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Divide and Conquer : Quicksort |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.