Bubble Sort

Bubble sort operates by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process causes the largest unsorted elements to migrate to their correct positions at the end of the array. While straightforward, its quadratic time complexity makes it inefficient for large datasets.

• Time Complexity: O(n²)
• Space Complexity: O(1)

#include <iostream>
#include <vector>
#include <utility>

void bubbleSort(std::vector<int>& data) {
    int n = data.size();
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (data[j] > data[j + 1]) {
                std::swap(data[j], data[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    std::vector<int> values = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(values);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Selection Sort

Selection sort divides the input into a sorted and an unsorted region. It repeatedly identifies the minimum element from the unsorted region and swaps it with the first unsorted element, expanding the sorted region by one. It is inherently unstable but requires no additional memory.

• Time Complexity: O(n²)
• Space Complexity: O(1)

#include <iostream>
#include <vector>
#include <utility>

void selectionSort(std::vector<int>& data) {
    int n = data.size();
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (data[j] < data[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            std::swap(data[i], data[min_idx]);
        }
    }
}

int main() {
    std::vector<int> values = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(values);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Insertion Sort

Insertion sort builds the final sorted array one item at a time. It picks an element and scans backward through the sorted portion, shifting elements right until the correct insertion point is found. This mechanism resembles organizing a hand of playing cards.

• Time Complexity: O(n²)
• Space Complexity: O(1)

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& data) {
    int n = data.size();
    for (int i = 1; i < n; ++i) {
        int key = data[i];
        int j = i - 1;
        while (j >= 0 && data[j] > key) {
            data[j + 1] = data[j];
            --j;
        }
        data[j + 1] = key;
    }
}

int main() {
    std::vector<int> values = {5, 1, 3, 8, 2, 6, 4, 9, 10, 7};
    insertionSort(values);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Shell Sort

Shell sort is an optimization of insertion sort that allows the exchange of elements far apart. It starts by sorting pairs of elements far apart from each other, then progressively reduces the gap between elements to be compared. By the time the gap is 1, the array is largely sorted, making the final insertion pass very efficient.

• Time Complexity: Ranges from O(n log n) to O(n²) depending on the gap sequence
• Space Complexity: O(1)

#include <iostream>
#include <vector>

void shellSort(std::vector<int>& data) {
    int n = data.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = data[i];
            int j;
            for (j = i; j >= gap && data[j - gap] > temp; j -= gap) {
                data[j] = data[j - gap];
            }
            data[j] = temp;
        }
    }
}

int main() {
    std::vector<int> values = {9, 8, 1, 3, 6, 5, 2, 7};
    shellSort(values);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Quick Sort

Quick sort employs a divide-and-conquer strategy. It selects a 'pivot' element and partitions the collection sothat all elements less than the pivot precede it, and those greater follow. This partitioning is recursively applied to the sub-arrays. Using the Hoare partition scheme, two pointers approach each other from opposite ends.

• Time Complexity: O(n log n) average, O(n²) worst-case
• Space Complexity: O(log n)

#include <iostream>
#include <vector>
#include <utility>

int partition(std::vector<int>& data, int low, int high) {
    int pivot = data[low + (high - low) / 2];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do { ++i; } while (data[i] < pivot);
        do { --j; } while (data[j] > pivot);
        if (i >= j) return j;
        std::swap(data[i], data[j]);
    }
}

void quickSort(std::vector<int>& data, int low, int high) {
    if (low < high) {
        int p = partition(data, low, high);
        quickSort(data, low, p);
        quickSort(data, p + 1, high);
    }
}

int main() {
    std::vector<int> values = {10, 7, 8, 9, 1, 5};
    quickSort(values, 0, values.size() - 1);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Merge Sort

Merge sort is a stable, divide-and-conquer algorithm. It splits the array into halves, recursively sorts them, and then merges the sorted halves back together. During the merge phase, two pointers traverse the sub-arrays, picking the smaller element at each step.

• Time Complexity: O(n log n)
• Space Complexity: O(n)

#include <iostream>
#include <vector>

void merge(std::vector<int>& data, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (data[i] <= data[j]) temp[k++] = data[i++];
        else temp[k++] = data[j++];
    }
    while (i <= mid) temp[k++] = data[i++];
    while (j <= right) temp[k++] = data[j++];
    for (int idx = 0; idx < k; ++idx) data[left + idx] = temp[idx];
}

void mergeSort(std::vector<int>& data, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(data, left, mid);
        mergeSort(data, mid + 1, right);
        merge(data, left, mid, right);
    }
}

int main() {
    std::vector<int> values = {12, 11, 13, 5, 6, 7};
    mergeSort(values, 0, values.size() - 1);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Heap Sort

Heap sort involves building a max-heap from the input data. The largest element (at the root) is repeatedly swapped with the last element of the heap, and the heap size is reduced by one. The heapify process then restores the heap property.

• Time Complexity: O(n log n)
• Space Complexity: O(1)

#include <iostream>
#include <vector>
#include <utility>

void heapify(std::vector<int>& data, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && data[left] > data[largest]) largest = left;
    if (right < n && data[right] > data[largest]) largest = right;
    if (largest != i) {
        std::swap(data[i], data[largest]);
        heapify(data, n, largest);
    }
}

void heapSort(std::vector<int>& data) {
    int n = data.size();
    for (int i = n / 2 - 1; i >= 0; --i) heapify(data, n, i);
    for (int i = n - 1; i > 0; --i) {
        std::swap(data[0], data[i]);
        heapify(data, i, 0);
    }
}

int main() {
    std::vector<int> values = {12, 11, 13, 5, 6, 7};
    heapSort(values);
    for (int v : values) std::cout << v << " ";
    return 0;
}

Counting Sort

Counting sort is a non-comparison-based algorithm that counts the occurrences of each distinct value. It is highly efficient when the range of potential items (the key values) is significantly smaller than the number of items.

• Time Complexity: O(n + k) where k is the range of input
• Space Complexity: O(n + k)

#include <iostream>
#include <vector>
#include <algorithm>

void countingSort(std::vector<int>& data) {
    if (data.empty()) return;
    int max_val = *std::max_element(data.begin(), data.end());
    int min_val = *std::min_element(data.begin(), data.end());
    int range = max_val - min_val + 1;

    std::vector<int> count(range, 0), output(data.size());
    for (int x : data) count[x - min_val]++;
    for (int i = 1; i < range; ++i) count[i] += count[i - 1];
    for (int i = data.size() - 1; i >= 0; --i) {
        output[count[data[i] - min_val] - 1] = data[i];
        count[data[i] - min_val]--;
    }
    for (int i = 0; i < data.size(); ++i) data[i] = output[i];
}

int main() {
    std::vector<int> values = {4, 2, 2, 8, 3, 3, 1};
    countingSort(values);
    for (int v : values) std::cout << v << " ";
    return 0;
}