A Practical Guide to Data Structures and Algorithms using Java

150 A Practical Guide to Data Structures and Algorithms Using Java

sort does very little computation before the recursive calls are made, and performs most of the

required work after the recursive calls have completed. In contrast, quicksort performs all of its

extra computation prior to making the recursive calls. Specifically, quicksort first selects a pivot

element and subdivides the array with respect to the pivot element so that when the pivot element

is in position p, all elements in positions 0 ≤ i ≤ p − 1 are no larger than the pivot element, and

all elements in positions p + 1, . . . , n − 1 are at least as large as the pivot element. Quicksort ...