> See also:
> - [[Data Structures]]
> - [[C Programming Language]]
# Sorting Algorithms
> [!example]- **Algorithm Visualizing Tools**
> - [Hacker Earth](https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/visualize/)
> - [Algorithm Vision Knights](https://algorithmviewer.com/#/)
An algorithm is considered a **stable algorithm** if the organization of its elements with *identical values* (tied during comparison) *maintain their relative position* from the original order.
- This may not seem important for simple integer arrays, however when sorting structures there will often be multiple values stored within each element, so maintaining their order when a tie occurs between one of their values is important.
```
aa
```
## Iterative Methods
> Sometimes called “*naive*” or “*primitive*” algorithms
> [!info] **Bubble Sort**
> - Iterative Method
> ---
| Best | Average | Worst |
| --- | --- | --- |
| $\Theta (N)$ | $\Theta (N^2)$ | $\Theta (N^2)$ |
> ---
> Compares adjacent elements and swaps them when out of order until a pass is completed with no swaps.
> > *The smaller elements “bubble up” to the top and the larger elements “sink” to the bottom.”*
> [!info] **Selection Sort**
> - Iterative Method
> ---
| Best | Average | Worst |
| --- | --- | --- |
| $\Theta (N^2)$ | $\Theta (N^2)$ | $\Theta (N^2)$ |
> ---
> Look for the smallest value in an unsorted array and move it to the end of a new, sorted array.
> > "*“Repeatedly iterate through the unsorted array and select the smallest (or largest)”*"
> [!info] **Insertion Sort**
> - Iterative Method
> ---
| Best | Average | Worst |
| --- | --- | --- |
| $\Theta (N)$ | $\Theta (N^2)$ | $\Theta (N^2)$ |
> ---
> Starts with an empty “sorted” array and iterates through all unsorted elements, inserting them accordingly into the “sorted” array.
## Recursive Methods (Divide and Conquer)
> See also: [[Recursion]]
> [!error] **Quick Sort**
> - Recursive Method
> ----
| Best | Average | Worst |
| --- | --- | --- |
| $\Theta (N \cdot \log N)$ | $\Theta (N \cdot \log N)$ | $\Theta (N^2)$ |
> ---
> Will first select a pivot position and group other elements using a low and high pointer. Moves the high and low arrays to different sides of the pivot
> [!error] **Merge Sort**
> - Recursive Method
> ---
| Best | Average | Worst |
| --- | --- | --- |
| $\Theta (N \cdot \log N)$ | $\Theta (N \cdot \log N)$ | $\Theta (N \cdot \log N)$ |
> ---
> **Summary:** *"Divide & Conquer"*
>
> Begins by splitting the array into many smaller arrays, until each sub-array only contains
>
> One common implementation of **merge sort** is to use two separate functions, one for the initial setup and another to perform the recursive aspects of the algorithm.
>
> 1. The first function is repeatedly called recursively until the array can no longer be split ($n \le 1$). The algorithm will reach it's *base case*
> 2. When an