Algorithms: Difference between revisions
(Created page with "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==== ====Insert...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 4: | Line 4: | ||
Given: compare(a,b) to compare 2 numbers. | Given: compare(a,b) to compare 2 numbers. | ||
Goal: Sort a list of numbers from smallest to largest. | Goal: Sort a list of numbers from smallest to largest. | ||
===O(n^2) Algorithms=== | ===<math>O(n^2)</math> Algorithms=== | ||
====Bubble Sort==== | ====Bubble Sort==== | ||
====Insertion Sort==== | ====Insertion Sort==== | ||
| Line 26: | Line 26: | ||
Algorithm: | Algorithm: | ||
===O( | ===<math>O(n \log n)</math> Algorithms=== | ||
====Merge Sort==== | ====Merge Sort==== | ||
====Heap Sort==== | ====Heap Sort==== | ||
| 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
- 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)\)