Algorithms

From David's Wiki
Jump to navigation Jump to search

Algorithms

Sorting

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

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:

O(nlogn) 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.

Graph Algorithms

Greedy

Dynamic Programming

Search

Binary Search