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?
(Link is to a game that a friend and I built in under 24 hours as a way of learning Easel js
(Link is to FLINT which I contributed C code to, usually in 24 hour chunks as a sprint or bug squash)
(Link is to a project I built for a radio station in under 24 hours, a way to learn backbone js.)
(Link is to a weekend project built with a buddy called "Drunken Doodle")
(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.
Analysis
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?
Worst-Case
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) \).
Best-Case
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).
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
Estimations
Big-Oh
RAM model
Logs
Arrays vs Lists
Heaps
Stacks vs Queues vs Priority Queues
Binary Search Trees
Hashing
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