Algorithms

From David's Wiki
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
\( \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

Bubble Sort

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:

\(\displaystyle O(n \log n)\) Algorithms

Merge Sort

Heap Sort

Linear Algorithms

Counting Sort

Radix Sort

Selection

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

Median finding

Reference

  • 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)\)

Graph Algorithms

Greedy

Dynamic Programming

Search

Binary Search