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

Quicksort and Selection Problem

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