Quicksort

!

Quicksort

Partition

Given a list $L$ and an element $x$ in $L$, partitioning $L[p \dots r]$ by the pivot element $x$ does the following:

Rearrange the elements in $L[p\dots r]$ so that there exists a position $q$ such that after rearrangment:

  1. $L[q] = x$
  2. $\forall i\in [p, q-1],\ L[i] \leq x$
  3. $\forall i\in [q+1, r],\ L[i] \geq x$
  4. !

!

Version 0.1: simple, but takes more memory

Let’s implement partition(L, p, r) with the minimal effort:

def partition(L, p, r):
    x = L[r]
    L1 = [y for y in L[p:r] if y <= x]
    L2 = [y for y in L[p:r] if y > x]
    L[p:r+1] = L1 + [x] + L2

!

Version 0.2: more involved, but takes no additional memory

!

def partition(L, p, r):
    x = L[r]
    i = p - 1
    for j in range(p, r):
        if L[j] <= x:
            i += 1
            L[i], L[j] = L[j], L[i]
    L[i+1], L[r] = L[r], L[i+1]

!

It only involves element swapping, so it requires zero additional memory.


But its correctness is much less obvious.

Analysis of partition

!

def partition(L, p, r):
    x = L[r]
    i = p - 1
    for j in range(p, r):
        if L[j] <= x:
            i += 1
            L[i], L[j] = L[j], L[i]
    L[i+1], L[r] = L[r], L[i+1]

!

Bookkeeping is the key:

Analysis of partition

!

def partition(L, p, r):
    x = L[r]
    i = p - 1
    for j in range(p, r):
        if L[j] <= x:
            i += 1
            L[i], L[j] = L[j], L[i]
    L[i+1], L[r] = L[r], L[i+1]

!

Loop invariance:

After each iteration, $L[p, j]$ is properly partitioned:

  • $L[p, i] \leq x$
  • $L[i+1, j] > x$
  • !

Quicksort

def quicksort(L, p, r):
    if p < r:
        k = partition(L, p, r)
        quicksort(L, p, k-1)
        quicksort(L, k+1, r)

Performance Analysis

!

We will only give a terse outline of the analysis. The full version is deferred to later lectures.

Performance Analysis

Let there be $n$ elements in the array.

Key obsevation:

Performance Analysis: Worst-case


We have enough to set-up an equation to estimate the number of instructions of quicksort(L, a, b):

Let $|L[a\dots b]| = n$.

$$\begin{eqnarray} T_\mathrm{quicksort}(n) &=& n + 2\cdot T_\mathrm{quicksort}(n-1) \end{eqnarray}$$


!

This leads to a (poor) performance characteristics of: $\approx n^2$

!

We will show how to solve such equations (known as recurrence equations) in the next section of this course.

Performance Analysis: average case

Quicksort as the name suggests is actually quite quick (most of the time…)


Revisiting k = partition(L, p, q).

The pivot value should be somewhere in the middle of the subarray. Namely: $k\approx p+q/2$, and so $k-1-p \approx n/2$, and $q-k-1\approx n/2$.


Revisiting the recurrence equation:

$$\begin{eqnarray} T_\mathrm{quicksort}(n) &=& n + 2\cdot T_\mathrm{quicksort}(n/2) \end{eqnarray}$$


This leads to a satisfying performance characteristics of: $\approx n\log(n)$

Summary

!

Challenge

Is QUICKSORT a stable sorting algorithm?

Recall:

Stable sorting requires an additional condition on the permutation:

$$ \forall i,j\in [0, \mathrm{length}(x)],\ i < j\ \mathrm{and}\ f(x[i], x[j]) = 0 \implies \pi(i) < \pi(j) $$

back
© KEN PU, 2016