Quicksort

Quick Sort

whatever

Openlearnware

Invariant

At the beginning of each iteration of the loop of lines 3-6, for any array index k,

1. If p ≤ k ≤ i, then A[k] ≤ x.

2. If i +1 ≤ k ≤ j - 1, then A[k] > x

3. If k = r, then A[k] = x

Initialization

Prior to the first iteration of the loop, i = p -1 and j = p. Because no values lie between p and i and no values lie between i +1 and j -1, the first two conditions of the loop invariant are trivially satisfied. The assignment in line 1 satifies the third condition.

Quicksort(A,p,r)

if p < r

Partition(A,p,r)

Quicksort(A,p,q - 1)

Quicksort(A,q + 1,r)

Partition(A,p,r)

x = A[r]

i = p - 1

for j = p to r - 1

if A[j] ≤ x

i = i + 1

exchange A[i] with A[j]

exchange A[i + 1] with A[r]

return i + 1