# Algorithms

$$\newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits}$$

Algorithms

## Sorting

Given: compare(a,b) to compare 2 numbers. Goal: Sort a list of numbers from smallest to largest.

### $$\displaystyle O(n^2)$$ Algorithms

#### Insertion Sort

Basic Idea:

• Maintain a subarray which is always sorted

Algorithm:

• Grab a number from the unsorted portion and insert it into the sorted portion
• Repeat until no more numbers are in the unsorted subarray

#### Selection Sort

Basic Idea:

• Maintain a subarray which is always sorted.
• Every number in the sorted subarray will be smaller than the smallest number in the unsorted subarray.

Algorithm:

• Find the smallest number in the unsorted portion and insert it into the sorted portion
• Repeat until no more numbers are in the unsorted subarray.

#### Quicksort

Basic Idea:

• Divide an conquer.
• Very fast. Average case O(nlogn).
• Good for multithreaded systems.

Algorithm:

## Selection

Given: compare(a,b) to compare 2 numbers. A number k. Goal: Return the k'th largest number.

### Median finding

• See CLRS
• Idea: Reinterpret your data as a 2D array of size 5 x (n/5)
• Find the median of each column of 5 elements
• Sort the columns by their medians
• Now you can eliminate the upper left (1/4) of elements and the lower right (1/4) of elements
• Recursively iterate on the remaining (1/2) of elements
• Each iteration takes O(n). Consecutive iterations are on n/2 data so we have $$\displaystyle O(n) + O(n/2) + ... = O(n)$$
• Worst Case $$\displaystyle O(n)$$

### Quickselect

• Worst Case $$\displaystyle O(n^2)$$
• Average Case $$\displaystyle O(n)$$
Notes
• Using a good $$\displaystyle O(n)$$ pivot finding algorithm (See finding the median in O(n)) will reduce the worst case to $$\displaystyle O(n)$$