Quicksort, Randomization, Test Review

Andy Novocin


A 24 hour Hack-a-thon, 2pm to 2pm October 4th

24 hours that will change your life

What is possible?

Build a game (a la Ludum dare)

(Link is to a game that a friend and I built in under 24 hours as a way of learning Easel js

Contribute to a worthy open source library

(Link is to FLINT which I contributed C code to, usually in 24 hour chunks as a sprint or bug squash)

Craft a small business venture

(Link is to a project I built for a radio station in under 24 hours, a way to learn backbone js.)

Build a facebook app

(Link is to a weekend project built with a buddy called "Drunken Doodle")

Revisualize someone else's data

(Link is to an app I built (in 24 hours) so that my employees could identify art movements. Data is scraped from artcyclopedia.)

Just Do It

You won't regret it, I promise.

Daily Problem

Give an \( \mathcal{O}(n \log{k}) \) algorithm that merges \( k \) sorted lists with a total of \( n \) elements into one sorted list.

Advanced Challenge

To calculate the product of degree \(n\) polynomials, \( f \cdot g \) split them into two halves:

\( f = f_1 \cdot x^m + f_0 \) and \(g = g_1 \cdot x^m + g_0\)

It has been observed that three smaller multiplications will suffice rather than four.

\( f_1 g_1 (x^{2m} + x^m) - x^m (f_1 - f_0) (g_1 - g_0) + (x^m + 1) f_0 g_0 \)

1) Confirm that this scheme works.

2) Devise a divide-and-conquer algorithm from this scheme.

3) Use the master theorem to prove that the complexity is sub-quadratic.

Ask me for the google search term if you would like.

Quick Sort

Concept is to pick a random element as a pivot.

Partition the inputs into smaller than and greater than pivot.

Then recursively (magically) quick sort the two smaller stacks.

As Hungarian dance (watch the hats)

Memory space?

Our merge sort required a separate array to stack our answers into. (Clever solutions exist BTW.)

Quick sort uses swapping in place to never need extra memory.


I felt like coding it to understand how the in-place bits worked.


To partition I will do \( n - 1 \) comparisons.

In the left group I will do \( k - 1 \) comparisons and in the right group \( n - k - 2\) comparisons

Each time we recurse there will be \( \mathcal{O}(n) \) comparisons.

So how many recursions can we do?


Every time I select a pivot it will be the max or min.

So each recursion works on exactly one less element.

In that case \( \mathcal{O}(n^2) \).


Every time I select a pivot it will be the median.

So each recursion divides the problem into half-problems.

In that case \( \mathcal{O}(n \log_2{n})\).

a) Best, b) Avg, c) Worst

Average Analysis

If we describe the middle half of the elements as good enough

Then half of the selections will be good enough

Each of these will reduce my search space by at least 3/4.

Thus when \( (\frac{3}{4})^{g} n \leq 1 \) we will be in the base case.

This happens after \( g = \log_{4/3}{n} \) good selections (and \(b = \log_{4/3}{n} \) bad selections).

The sound of quicksort

Quick sort problems

1) In my implementation the pivot was always chosen as the right most element. Classify the worst case inputs to my code.

2)Can you suggest an approach which will make my code more robust?

3) Suppose that every chosen pivot separates 1% from 99% of the remaining numbers. What is the wost case complexity?

Sort Comparison with CPU cycles

Quicksort expected \( \mathcal{O}(n \log{n} ) \)

Mergesort \( \mathcal{O}(n \log{n} ) \)

Heapsort \( \mathcal{O}(n \log{n} ) \)

Insertion Sort \( \mathcal{O}(n^2) \)

Las-Vegas vs Monte Carlo

Las Vegas Algorithms will give correct output or failure.

Las Vegas Algorithms might not state anything other than finite running time.

Monte Carlo algorithms are typically fast and give no guarantee of correctness.

Used for quickly getting a feel for an otherwise difficult task.

Las Vegas Sorting

Quicksort is las vegas

So is BOGOSORT! (Shuffle the elements, check if sorted, repeat.)

Monte Carlo Estimating \( \pi/4 \)

Review Topics

Counter-Examples and Correctness
RAM model
Arrays vs Lists
Stacks vs Queues vs Priority Queues
Binary Search Trees
Divide and Conquer and Master Theorem
Sorting Galore: applications, insert, selection, merge, quick, heap
Binary Search

Work these:

1-17, 2-16, 3-11, 4-13, 1-11, 2-38, 3-4, 4-4, 1-3