SUNY Geneseo Department of Computer Science

Quicksort

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

Misc

Last algorithm on problem set

Innermost loop repeats limit times, doing 1 multiplication
- Innermost loop takes "limit" units of work total
This is work each iteration of middle loop does
- So middle loop does n*limit units of work total
This, plus 1 more multiplication, is work outer loop does in each iteration
- i.e., each iteration does n * limit + 1
But "limit" depends on which iteration outer loop is in, so sum instead of multiply
- limit = i*n
So work in each iteration = i*n*n + 1
Sum this as i ranges from 0 to n-1

Sections 10.1 and 10.2

General idea: partitioning
- Split list into smaller pieces to sort
- Because solving two small problems is faster than solving one big one if time is greater than Θ(n)
Algorithm and proof of correctness
- Divide list into 2 sections with larger values in one and smaller in other
- Recursively sort each section
Pivot and choosing one
- Pivot = value that defines "small" and "large"
Details of partitioning

An alternative partitioning algorithm

Start with the same loop invariant as in the book...
- For all i such that first ≤ i < uFirst, contents[i] ≤ v and for all j such that uLast < j ≤ last, v ≤ contents[j]
But find a different way to restore it when uFirst reaches an element greater than the pivot, or uLast reaches an element less than the pivot.
Key idea: alternately advance uFirst and uLast, swapping the values they index when both index values that should be in the other partition. Finally, swap pivot and element indexed by uLast.

[Partitioning in Quicksort]

Quicksort's performance

Read section 10.3