Review/Sorting Algorithms.txt at main · theseus27/Review · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
Breadth First
    - Searches a tree (or graph) by levels of the tree, starting at the root
    - Finds each node on same level, moving left to right
    - Last evaluated is bottom right node

    - Optimal for searching a tree that is wider than it is deep
    - Uses a queue to store information about tree
    - Uses more memory bc stores pointers
    - Tends to be a looping algorithm
    - O(V + E) where V = vertices, E = edges

Depth First
    - Searches tree (or graph) by searching depth, starting at root
    - Traverses left down a tree until can't go further
    - When reaches end of branch, traverses back up trying right child of nodes on that branch, and if possible left children of rights
    - Right most node is evaluated last

    - Optimal for searching a tree deeper than it is wide
    - Uses a stack to push nodes onto
    - Less memory intensive than breadth first
    - Tends to be a recursive algorithm
    - O([E] + [V]) where V = vertices, E = edges

Merge Sort
    - Comparison based sorting algorithm
    - Divides dataset into groups of at most 2
    - Moves smaller number to left of pair
    - Compares left most elements of 2 leftmost pairs creating a sorted group of four with the smallest numbers on the left and largest on the right
    - Process is repeated until there is only one store

Quick Sort*
    - Divides dataset in half by selecting middle element and putting all smaller elements to the left and larger to the right
    - Repeats on left side until is only comparing two elements
    - Repeats on right side until only comparing two elements
    - Computer architecture favors Quick Sort
        - Is often faster in practice than Merge Sort and other O(n log n)

Bubble Sort
    - Iterates left to right comparing every couplet, moving smaller element to left
    - Repeats this process until it no longer moves an element to the left
    - Simple to implement but relatively inefficient
    - moves one space to the right at a time

Heap Sort
    -

Tim Sort
    -

Insertion Sort
    -

Selection Sort
    -

Radix Sort
    -

Counting Sort
    -

Binary Search
    -

Time Complexities:
    Merge Sort:     O(n log n)
    Quick Sort:     O(n log n)
    Bubble Sort:    O(n^2)

    O(n + k): Bucketsort, Radixsort, Countingsort
    O(n log n): Quicksort, Mergesort, Timsort, Heapsort, Treesort, Cubesort
    O(n^2): Bubblesort, Insertionsort, Selectionsort

    *Heapsort uses O(1) space complexity
    *Quicksort uses O(log(n)) space complexity

Greedy Algorithms
    - Selects only information that meets a certain criteria
    1. Candidate set, from which solution is created
    2. Selection function, chooses best candidate to be added to solution
    3. Feasibility function, determines if candidate can contribute to solution
    4. Objective function, assigns a value to a solution, or partial solution
    5. Solution function, indicates when we have discovered a complete solution

    - Used to find fastest, non-optimal solution
    - Used on data sets where a small proportion of information meets the desired result
    - Can help reduce Big O