# Algorithm
## Sorting
### 1.Selection Sort
> ### Idea:
> 1. Select the lowest card in the "unsorted" pile
> 2. Move it to the top of the "sorted" pile
> 3. Repeat steps 1 and 2 until there are no cards left in the "unsorted" pile

Selection Sort can happen in place — meaning we don't need a new vector to store the results
Selection Sort is `unstable sort`
> ### Time complexity
> O(n^2)
### Implementation in C++
#### Descending Order

// Soring Data
std::vector<int> data{10, 2, 4, 1, 3, 5, 6, 11};
    
// Initialize the largest
int largest = 0;
    
// Selection Sort Algorithm
for(size_t i = 0; i<data.size(); ++i){
    largest = i;
    for(size_t j = i+1; j<data.size(); ++j){
        if(data[j] > data[largest]){
            largest = j;
        }
    }
    if(data[i] < data[largest]){
        int temp = data[i];
        data[i] = data [largest];
        data[largest] = temp;
    }
} 

#### Ascending Order

// Soring Data
std::vector<int> data{10, 2, 4, 1, 3, 5, 6, 11};
    
// Initialize the smallest
int smallest = 0;
    
// Selection Sort Algorithm
for(size_t i = 0; i<data.size(); ++i){
    smallest = i;
    for(size_t j = i+1; j<data.size(); ++j){
        if(data[j] < data[smallest]){
            smallest = j;
        }
    }
    if(data[i] > data[smallest]){
        int temp = data[i];
        data[i] = data [smallest];
        data[smallest] = temp;
    }
} 

### 2. Stable Sort vs Untable Sort
#### In a stable sort, two vlaues of the same rank are guaranteed to be in the same order as they were prior to the sort, eg:

### 3. Other Sorting Algorithms
#### Insertion Sort (stable)
> unstable sort
> Time Complexity O(n^2)
#### Bubble Sort (stable)
> stable sort
> Time Complexity O(n^2)
> In-place

Implementation

#include <iostream>
#include <vector>

std::ostream& operator<<(std::ostream& out, std::vector<int>& data){
    for(const auto ele: data){
        out << ele << " ";
    }
    return out;
}

void bubble_sort_a(std::vector<int>& data){
    // bubble Sort: ascending order
    for(size_t i=1; i<data.size(); ++i){
        for(size_t j=0; j<data.size() - i; ++j){
            if(data[j] > data[j+1]){
                int temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
    }
}

void bubble_sort_d(std::vector<int>& data){
    // bubble Sort: descending order
    for(size_t i=1; i<data.size(); ++i){
        for(size_t j=0; j<data.size() - i; ++j){
            if(data[j] < data[j+1]){
                int temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
    }
}

int main()
{
    std::vector<int> data{2, 5, 0, 9, 7, 2, 4, 5, 10, 3};
    std::cout << "Before Sorting: " << std::endl;
    std::cout << data << std::endl;
    
    bubble_sort_d(data);
    
    std::cout << "After Sorting: " << std::endl;
    std::cout << data << std::endl;
    
    bubble_sort_a(data);
    
    std::cout << "After Sorting: " << std::endl;
    std::cout << data << std::endl;
    
    return 0;
}

#### Merge Sort (stable)
#### Quicksort
> unstable sort
> Time Complexity

quick_sort(std::vector<int>& data, ){

}

int partition(){

}

+ Big O categroies
+ O(1)
+ Constant Time
+ O(log n)
+ Logrithmic Time
+ O(n)
+ Linear Time
+ O(n log n)
+ O(n log n) Time
+ O(n^2)
+ Quadratic Time
+ Big-O Visualized
+ Big-O and Data Structure
+ Vector
+ Queue
+ Stack
+ Map
+ Sorting algorithm in terms of Big O
+ Selection sort (not stable): O(n2)
+ Bubble sort (stable): O(n2)
+ Insertion sort (stable): O(n2)
+ Merge sort (stable): O(n log n)
+ Quicksort (not stable): Usually O(n log n), can devolve into O(n2)
+ Recursion
+ Searching
+ Linear Search
+ Binary Search