Quick Sort

Quick Sort

As the name implies, it is quick, and it is the algorithm generally preferred for sorting.

Quick Sort

1

Basic Ideas

(Another divide-and-conquer algorithm) Pick an element, say P (the pivot) Re-arrange the elements into 3 sub-blocks,

those less than or equal to (≤) P (the left-block S1) 2. P (the only element in the middle-block) 3. those greater than or equal to (≥) P (the rightblock S2)

1.

Repeat the process recursively for the left- and right- sub-blocks. Return {quicksort(S1), P, quicksort(S2)}. (That is the results of quicksort(S1), followed by

P, followed by the results of quicksort(S2))

Quick Sort 2

Basic Ideas

Pick a “Pivot” value, P Create 2 new sets without P Items smaller than or equal to P Items greater than or equal to P

0 31 13 43 26 57

quicksort(S1)

≤ ≤

65

≤ ≤

75 92 81

quciksort(S2)

0 13 26 31 43 57

65

75 81 92

0 13 26 31 43 57 65 75 81 92

Quick Sort

3

Basic Ideas

S is a set of numbers

S1 = {x ∈ S – {P} | x ≤ P}

P

S2 = { x∈ S – {P} | P ≤ x}

Quick Sort

4

Basic Ideas

Note: The main idea is to find the “right” position for the pivot element P. After each “pass”, the pivot element, P, should be “in place”. Eventually, the elements are sorted since each pass puts at least one element (i.e., P) into its final position. Issues: How to choose the pivot P ? How to partition the block into sub-blocks?

Quick Sort 5

Implementation

Algorithm I:

int partition(int A[ ], int left, int right); // sort A[left..right] void quicksort(int A[ ], int left, int right) { int q ; if (right > left ) { q = partition(A, left, right); // after ‘partition’ // A[left..q-1] ≤ A[q] ≤ A[q+1..right] quicksort(A, left, q-1); quicksort(A, q+1, right); } }

Quick Sort 6

Implementation

// select A[left] be the pivot element) int partition(int A[], int left, int right); { P = A[left]; i = left; j = right + 1; for(;;) //infinite for-loop, break to exit { while (A[++i] < P) if (i >= right)...