Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
11 Cards in this Set
- Front
- Back
Insertion Sort |
for i = 1 to end x = a[i] j = i - 1 while a[j] > x and j >= 0 a[j+1] = a[j] j-- end while a[j] = x end for Best: O(n) (array in order) Worst: O(n^2) (array in reverse) Average: O(n^2) Very bad for large arrays because average time is O(n^2) Very good for small arrays and when array is nearly sorted (because algorithm is adaptive) |
|
Merge Sort |
Break array up into single element lists Combine them into 2s, then 4s, etc smallest elements first of which ever two are being combined Worst/Best/Average Case: O(nlogn) Good for linked lists because the algorithm operates sequentially, plus it is easy to break apart/combine nodes |
|
Bucket Sort |
Create n number of buckets Add each element to appropriate bucket Sort the elements in each bucket Combine the buckets Best: O(n + k) (k is number of buckets) Worst: O(n^2) Average: O(n + k) Implemented with insertion sort because of the small lists Good when array is distributed into buckets evenly Bad when all elements are in the same bucket |
|
Quick Sort |
Best: O(nlogn) Worst: O(n^2) Average: O(nlogn) Good for when data is very unsorted Good for when you care about average performance |
|
Heap Sort |
Build Max Heap Swap first element with last MaxHeapify HeapSort(0, n- 1) BuildMaxHeap for i = floor(n/2) to 0 MaxHeapify Best: O(nlogn) Worst: O(nlogn) Average: O(nlogn) Good for when you care about worst-case performance |
|
Dynamic Programming |
Used to find optimal solution Represents time vs. memory tradeoff |
|
Local Alignment |
Strings differ in length, short patches of similarity |
|
Global Sequence |
Good for same length strings which are similar throughout |
|
Needleman Wunsch = LCS if.. |
g = 0 s(xi, yj) = 1 if xi = yj s(xi, yj) = -∞ if xi ≠ yj |
|
Radix Sort |
Sort by LSD or MSD if there is a tie, whichever comes first in array wins Performance: O(kN) Good for integers and fixed size strings |
|
Counting Sort |
Find min and max value Create array of length max - min Create array that holds count of each number Create sumcount array which is runsum of count Put each number in array associated with occurence in sumcount For example if 12 has sum count of 5, 12 goes in position 5 |