# Concise campaign of sorting algorithm

### 1. Bubble Sort
The first sort we learn

int *bubble_sort(int *array, int array_size) {
    for (int pass = 1; pass < array_size; pass++) {                                        // scan from first to last
        for (int compare_index = 0; compare_index < array_size - pass; compare_index++) {  // compare the two elements to see which one is greater
            if (array[compare_index] > array[compare_index + 1]) {
                swap(&array[compare_index], &array[compare_index + 1]);  // swap two elements if the next element is smaller than the compare one
            }
        }
    }
    return *array;
}

void swap(int *address_a, int *address_b) {  // swap two elements
    int temp = *address_a;
    *address_a = *address_b;
    *address_b = temp;
}

### 2. Insertion Sort
Slow but easy

int *insertion_sort(int *array, int array_size) {
    for (int compare_index = 1; compare_index < array_size; compare_index++) {
        int key = array[compare_index];  // set key from first to last
        int compare_key;
        for (compare_key = compare_index - 1; compare_key >= 0 && array[compare_key] > key; compare_key--) {
            array[compare_key + 1] = array[compare_key];  // move left if array[compare_key] is greater than the key
        }
        array[compare_key + 1] = key;  // move key back
    }
    return *array;
}

### 3. Selection Sort
Slow but easy

int *selection_sort(int *array, int array_size) {
    for (int compare_index = 0; compare_index < array_size; compare_index++) {
        int min = array[compare_index];  // set min as the first element
        int min_index = compare_index;   // set min_index as the first index
        for (int find_min = compare_index + 1; find_min < array_size; find_min++) {
            if (array[find_min] < min) {
                min = array[find_min];  // set new min as the element which is smaler than the original one
                min_index = find_min;   // set new min_index as the element_index
            }
        }
        swap(&array[compare_index], &array[min_index]);  // swap the array[compare_index] with the min one
    }
    return *array;
}

void swap(int *address_a, int *address_b) {  // swap two elements
    int temp = *address_a;
    *address_a = *address_b;
    *address_b = temp;
}

### 4. Quick Sort
Slow a bit and a bit hard

void quickSort(int* arr, int start, int end) {
    if (start < end) {                           // if start == end, the sort ends
        int pivot = partition(arr, start, end);  // find the pivot point

        quickSort(arr, start, pivot - 1);  // sort the array on the left side of the pivot
        quickSort(arr, pivot + 1, end);    // sort the array on the right side of the pivot
    }
}

int partition(int* arr, int start, int end) {
    int pivot = arr[end];        // set pivot as the end element
    int left_index = start - 1;  // locate the left_index

    for (int compare_index = start; compare_index < end; compare_index++) {
        if (arr[compare_index] < pivot) {
            left_index++;
            swap(&arr[left_index], &arr[compare_index]);  // move left if &arr[compare_index] is smaller than the pivot
        }
    }
    swap(&arr[left_index + 1], &arr[end]);  // left_index + 1 == the location of pivot, swap pivot with the element at left_index + 1
    return left_index + 1;                  // return the location of pivot
}

void swap(int* address_a, int* address_b) {  // swap two elements
    int temp = *address_a;
    *address_a = *address_b;
    *address_b = temp;
}