Algorithms: Difference between revisions

From David's Wiki
 
Line 38: Line 38:
Given: compare(a,b) to compare 2 numbers. A number k.
Given: compare(a,b) to compare 2 numbers. A number k.
Goal: Return the k'th largest number.
Goal: Return the k'th largest number.
===Median finding===
[https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/ 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 <math>O(n) + O(n/2) + ... = O(n)</math>
* Worst Case <math>O(n)</math>
===Quickselect===
* Worst Case <math>O(n^2)</math>
* Average Case <math>O(n)</math>
;Notes
* Using a good <math>O(n)</math> pivot finding algorithm (See finding the median in O(n)) will reduce the worst case to <math>O(n)</math>


==Graph Algorithms==
==Graph Algorithms==

Latest revision as of 18:05, 11 December 2019

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