Quicksort

Internal

• Data Structures and Algorithms
• Sorting Algorithms

Overview

CLRS page 170.

In-place sorting divide-and-conquer algorithm.

Worst-case time	Θ(n2)
Expected running time	Θ(n lgn)
Best-case time

Algorithm

The procedure receives the reference to the array containing the numbers to be sorted, and the edges p (the first element of the section to be sorted) and r (the element immediately following the last element to be sorted, or the outside of the array). As all divide-and-conquer algorithms, Quicksort has three steps:

1. Divide: it partitions the area to be sorted in three zones, possibly empty: 1) the left zone a[p ... q-1] contains numbers smaller or equal with a special element, called pivot, 2) one zone with one element a[q] containing the pivot 3) the right zone a[q +1 ... r-1], possibly empty that contains numbers bigger or equal with the pivot.
2. Conquer: applies itself recursively on the left zone and on the right zone.
3. Combine: since the zones are already sorted, there is nothing to combine.

Quicksort and Selection Problem

The randomized Quicksort algorithm is somewhat similar to the one used by the generic selection problem.