# Sorting Algorithm

## Bubble Sort

Bubble Sort is a simple sorting algorithm, that always compare to adjacent elements, and swaps them if they are in the wrong order.

Now we have a list: `[3,1,2,5,4]`

How Bubble sort works as follows:

- Compare 3 and 1: swap, result: `[1,3,2,5,4]`
- Compare 3 and 2: swap, result: `[1,2,3,5,4]`
- Compare 3 and 5: no need to swap
- Compare 5 and 4: swap, result: `[1,2,3,4,5]`

**Why call Bubble sort?**
Bubble sort move forward the value that bigger than (ascending order) the adjacent element, the value like bubble floating up slowly.

int arr[] = {3,1,2,5,4};
int n = sizeof(arr) / sizeof(int);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int t = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = t;
        }
    }
}

## Selection Sort

Selection Sort is a simple sorting algorithm, that always select the minimum value and swap to the current position.

Now we have a list: `[3,1,2,5,4]`

How Selection sort works as follow:

- Select 1: swap, result: `[1,3,2,5,4]`
- Select 2: swap, result: `[1,2,3,5,4]`
- Select 4: swap, result: `[1,2,3,4,5]`

int arr[] = {3,1,2,5,4};
int n = sizeof(arr) / sizeof(int);
for (int i = 0; i < n - 1; i++) {
    int val = arr[i + 1], index = i + 1;
    for (int j = i + 1; j < n; j++) {
        if (val > arr[j]) {
            val = arr[j];
            index = j;
        }
    }
    if (val < arr[i]) {
        arr[index] = arr[i];
        arr[i] = val;
    }
}

## Insertion Sort

Insertion Sort is a simple sorting algorithm, it checks the value against the largest value in the sorted list. If the current value is larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position. This makes insertion sort efficient for small datasets and nearly sorted arrays.

Now we have a list: `[3,1,2,5,4]`

How Selection sort works as follow:

- `[1,3,2,5,4]`
- `[1,2,3,5,4]`
- `[1,2,3,4,5]`

for (int i = 1; i < n; i++) {
    int t = arr[i], j = i - 1;
    for (; arr[j] > t && j >= 0; j--) {
        arr[j + 1] = arr[j];
    }
    arr[j + 1] = t;
}