---
# System prepended metadata

title: Algorithm

---

# 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

```c++=
// 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
```c++=
// 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:
![Screenshot 2024-04-01 at 10.57.14 PM](https://hackmd.io/_uploads/BkDHCfKkR.png)

### 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
```c++=
#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
```c++=
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