## 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