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..." |
|||
| 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==== | ||
Revision as of 17:59, 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:
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.