Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. The algorithm terminates early if no swaps occur during a pass, indicating the array is sorted. Time complexity: O(n²) average and worst case, O(n) best case. Space complexity: O(1).

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

void bubbleSort(std::vector<int>& data) {
    int size = data.size();
    if (size < 2) return;
    
    bool swapped;
    for (int pass = size - 1; pass > 0; --pass) {
        swapped = false;
        for (int idx = 0; idx < pass; ++idx) {
            if (data[idx] > data[idx + 1]) {
                int temp = data[idx];
                data[idx] = data[idx + 1];
                data[idx + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    srand(time(nullptr));
    std::vector<int> data;
    for (int i = 0; i < 10; ++i) {
        data.push_back(rand() % 100);
    }
    
    std::cout << "Original: ";
    for (const auto& val : data) std::cout << val << " ";
    std::cout << "\n";
    
    bubbleSort(data);
    
    std::cout << "Sorted: ";
    for (const auto& val : data) std::cout << val << " ";
    std::cout << "\n";
    
    return 0;
}

Selection Sort

Selection sort divides the array into sorted and unsorted regions. It repeatedly selects the smallest element from the unsorted region and swaps it with the first unsorted element. The dual-pointer optimization finds both minimum and maximum elements in each pass. Time complexity: O(n²). Space complexity: O(1).

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

void dualSelectionSort(std::vector<int>& array) {
    int left = 0, right = array.size() - 1;
    while (left < right) {
        int minIdx = left, maxIdx = left;
        for (int i = left; i <= right; ++i) {
            if (array[i] < array[minIdx]) minIdx = i;
            if (array[i] > array[maxIdx]) maxIdx = i;
        }
        
        if (minIdx != left) {
            int temp = array[left];
            array[left] = array[minIdx];
            array[minIdx] = temp;
        }
        
        if (maxIdx == left) maxIdx = minIdx;
        
        if (maxIdx != right) {
            int temp = array[right];
            array[right] = array[maxIdx];
            array[maxIdx] = temp;
        }
        
        ++left;
        --right;
    }
}

int main() {
    srand(time(nullptr));
    std::vector<int> array;
    for (int i = 0; i < 10; ++i) {
        array.push_back(rand() % 100);
    }
    
    std::cout << "Before: ";
    for (const auto& val : array) std::cout << val << " ";
    std::cout << "\n";
    
    dualSelectionSort(array);
    
    std::cout << "After: ";
    for (const auto& val : array) std::cout << val << " ";
    std::cout << "\n";
    
    return 0;
}

Insertion Sort

Insertion sort builds the sorted array one element at a time by inserting each new element into its proper position within the previously sorted subarray. It performs well on nearly sorted data. Time complexity: O(n²) average and worst case, O(n) best case. Space complexity: O(1).

#include <iostream>
#include <cstdlib>
#include <ctime>

void insertionSort(int elements[], int length) {
    for (int pos = 1; pos < length; ++pos) {
        int currentVal = elements[pos];
        int walker = pos - 1;
        while (walker >= 0 && elements[walker] > currentVal) {
            elements[walker + 1] = elements[walker];
            --walker;
        }
        elements[walker + 1] = currentVal;
    }
}

int main() {
    srand(time(nullptr));
    const int SIZE = 10;
    int elements[SIZE];
    
    for (int i = 0; i < SIZE; ++i) {
        elements[i] = rand() % 100;
    }
    
    std::cout << "Pre-sort: ";
    for (int i = 0; i < SIZE; ++i) std::cout << elements[i] << " ";
    std::cout << "\n";
    
    insertionSort(elements, SIZE);
    
    std::cout << "Post-sort: ";
    for (int i = 0; i < SIZE; ++i) std::cout << elements[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Shell Sort

Shell sort improves insertion sort by sorting elements at specific intervals (gaps), gradually reducing the gap until the entire array is sorted. This allows elements to move longer distances early in the process. Time complexity: O(n log n) to O(n²) depending on gap sequence. Space complexity: O(1).

#include <iostream>
#include <cstdlib>
#include <ctime>

void shellInsertion(int dataset[], int count, int gap) {
    for (int outer = gap; outer < count; ++outer) {
        int value = dataset[outer];
        int inner = outer - gap;
        while (inner >= 0 && dataset[inner] > value) {
            dataset[inner + gap] = dataset[inner];
            inner -= gap;
        }
        dataset[inner + gap] = value;
    }
}

void shellSort(int dataset[], int count) {
    for (int gap = count / 2; gap > 0; gap /= 2) {
        shellInsertion(dataset, count, gap);
    }
}

int main() {
    srand(time(nullptr));
    const int COUNT = 10;
    int dataset[COUNT];
    
    for (int i = 0; i < COUNT; ++i) {
        dataset[i] = rand() % 100;
    }
    
    std::cout << "Original: ";
    for (int i = 0; i < COUNT; ++i) std::cout << dataset[i] << " ";
    std::cout << "\n";
    
    shellSort(dataset, COUNT);
    
    std::cout << "Sorted: ";
    for (int i = 0; i < COUNT; ++i) std::cout << dataset[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Quick Sort

Quick sort employs a divide-and-conquer strategy by selecting a pivot element and partitioning the array into two subarrays: elements less than the pivot and elements greater than the pivot. It recursively sorts the subarrays. Time complexity: O(n log n) average, O(n²) worst case. Space complexity: O(log n) due to recursion.

#include <iostream>
#include <cstdlib>
#include <ctime>

int partitionArray(int array[], int start, int end) {
    int pivotValue = array[start];
    int lower = start + 1;
    int upper = end;
    
    while (lower <= upper) {
        while (lower <= upper && array[upper] >= pivotValue) upper--;
        while (lower <= upper && array[lower] <= pivotValue) lower++;
        
        if (lower < upper) {
            int temp = array[lower];
            array[lower] = array[upper];
            array[upper] = temp;
        }
    }
    
    array[start] = array[upper];
    array[upper] = pivotValue;
    return upper;
}

void quickSort(int array[], int start, int end) {
    if (start < end) {
        int splitPoint = partitionArray(array, start, end);
        quickSort(array, start, splitPoint - 1);
        quickSort(array, splitPoint + 1, end);
    }
}

int main() {
    srand(time(nullptr));
    const int CAPACITY = 10;
    int array[CAPACITY];
    
    for (int i = 0; i < CAPACITY; ++i) {
        array[i] = rand() % 100;
    }
    
    std::cout << "Unsorted: ";
    for (int i = 0; i < CAPACITY; ++i) std::cout << array[i] << " ";
    std::cout << "\n";
    
    quickSort(array, 0, CAPACITY - 1);
    
    std::cout << "Sorted: ";
    for (int i = 0; i < CAPACITY; ++i) std::cout << array[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Merge Sort

Merge sort divides the array into halves, recursively sorts each half, and then merges the sorted halves. It guarantees O(n log n) performance and is stable. Time complexity: O(n log n) in all cases. Space complexity: O(n) for the temporary arrays.

#include <iostream>
#include <cstdlib>
#include <ctime>

void mergeArrays(int array[], int leftBound, int midPoint, int rightBound) {
    int leftLength = midPoint - leftBound + 1;
    int rightLength = rightBound - midPoint;
    
    int* leftArray = new int[leftLength];
    int* rightArray = new int[rightLength];
    
    for (int i = 0; i < leftLength; ++i)
        leftArray[i] = array[leftBound + i];
    for (int j = 0; j < rightLength; ++j)
        rightArray[j] = array[midPoint + 1 + j];
    
    int leftIdx = 0, rightIdx = 0, mergedIdx = leftBound;
    
    while (leftIdx < leftLength && rightIdx < rightLength) {
        if (leftArray[leftIdx] <= rightArray[rightIdx]) {
            array[mergedIdx] = leftArray[leftIdx++];
        } else {
            array[mergedIdx] = rightArray[rightIdx++];
        }
        ++mergedIdx;
    }
    
    while (leftIdx < leftLength) array[mergedIdx++] = leftArray[leftIdx++];
    while (rightIdx < rightLength) array[mergedIdx++] = rightArray[rightIdx++];
    
    delete[] leftArray;
    delete[] rightArray;
}

void mergeSort(int array[], int leftBound, int rightBound) {
    if (leftBound < rightBound) {
        int midPoint = leftBound + (rightBound - leftBound) / 2;
        mergeSort(array, leftBound, midPoint);
        mergeSort(array, midPoint + 1, rightBound);
        mergeArrays(array, leftBound, midPoint, rightBound);
    }
}

int main() {
    srand(time(nullptr));
    const int SIZE = 10;
    int array[SIZE];
    
    for (int i = 0; i < SIZE; ++i) array[i] = rand() % 100;
    
    std::cout << "Initial: ";
    for (int i = 0; i < SIZE; ++i) std::cout << array[i] << " ";
    std::cout << "\n";
    
    mergeSort(array, 0, SIZE - 1);
    
    std::cout << "Sorted: ";
    for (int i = 0; i < SIZE; ++i) std::cout << array[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Heap Sort

Heap sort builds a max-heap from the array, then repeatedly extracts the maximum element and places it at the end of the array. It uses the heapify operation to maintain the heap property. Time complexity: O(n log n) in all case. Space complexity: O(1).

#include <iostream>
#include <cstdlib>
#include <ctime>

void exchange(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int heap[], int index, int size) {
    int largest = index;
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;
    
    if (leftChild < size && heap[leftChild] > heap[largest])
        largest = leftChild;
    
    if (rightChild < size && heap[rightChild] > heap[largest])
        largest = rightChild;
    
    if (largest != index) {
        exchange(&heap[index], &heap[largest]);
        heapify(heap, largest, size);
    }
}

void heapSort(int heap[], int size) {
    for (int i = size / 2 - 1; i >= 0; --i)
        heapify(heap, i, size);
    
    for (int i = size - 1; i > 0; --i) {
        exchange(&heap[0], &heap[i]);
        heapify(heap, 0, i);
    }
}

int main() {
    srand(time(nullptr));
    const int LENGTH = 10;
    int heap[LENGTH];
    
    for (int i = 0; i < LENGTH; ++i) heap[i] = rand() % 100;
    
    std::cout << "Before: ";
    for (int i = 0; i < LENGTH; ++i) std::cout << heap[i] << " ";
    std::cout << "\n";
    
    heapSort(heap, LENGTH);
    
    std::cout << "After: ";
    for (int i = 0; i < LENGTH; ++i) std::cout << heap[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Counting Sort

Counting sort works by counting the occurrences of each unique element, then calculating the positions of each element in the sorted output. It requires integer keys within a specific range. Time complexity: O(n + k) where k is the range of input. Space complexity: O(k).

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

void countingSort(int input[], int inputSize) {
    int maxElement = *std::max_element(input, input + inputSize);
    int* countArray = new int[maxElement + 1]();
    
    for (int i = 0; i < inputSize; ++i) {
        countArray[input[i]]++;
    }
    
    int outputIndex = 0;
    for (int value = 0; value <= maxElement; ++value) {
        while (countArray[value] > 0) {
            input[outputIndex++] = value;
            countArray[value]--;
        }
    }
    
    delete[] countArray;
}

int main() {
    srand(time(nullptr));
    const int CAPACITY = 10;
    int input[CAPACITY];
    
    for (int i = 0; i < CAPACITY; ++i) input[i] = rand() % 100;
    
    std::cout << "Input: ";
    for (int i = 0; i < CAPACITY; ++i) std::cout << input[i] << " ";
    std::cout << "\n";
    
    countingSort(input, CAPACITY);
    
    std::cout << "Output: ";
    for (int i = 0; i < CAPACITY; ++i) std::cout << input[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Bucket Sort

Bucket sort distributes elements into buckets based on they values, sorts each bucket individually (often using another sorting algorithm), and then concatenates the buckets. It performs well when the input is uniformly distributed. Time complexity: O(n + k) average, O(n²) worst case. Space complexity: O(n + k).

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

void bucketSort(int data[], int dataSize) {
    const int bucketCount = 10;
    std::vector<int> buckets[bucketCount];
    
    for (int i = 0; i < dataSize; ++i) {
        int bucketIndex = data[i] / 10;
        buckets[bucketIndex].push_back(data[i]);
    }
    
    for (int i = 0; i < bucketCount; ++i) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }
    
    int dataIndex = 0;
    for (int i = 0; i < bucketCount; ++i) {
        for (int value : buckets[i]) {
            data[dataIndex++] = value;
        }
    }
}

int main() {
    srand(time(nullptr));
    const int LENGTH = 10;
    int data[LENGTH];
    
    for (int i = 0; i < LENGTH; ++i) data[i] = rand() % 100;
    
    std::cout << "Unsorted: ";
    for (int i = 0; i < LENGTH; ++i) std::cout << data[i] << " ";
    std::cout << "\n";
    
    bucketSort(data, LENGTH);
    
    std::cout << "Sorted: ";
    for (int i = 0; i < LENGTH; ++i) std::cout << data[i] << " ";
    std::cout << "\n";
    
    return 0;
}

Radix Sort

Radix sort processes digits from least significant to most significant, using a stable sub-sorting algorithm (typically counting sort) for each digit position. It works for integers or strings with fixed-length keys. Time complexity: O(d × (n + k)) where d is digit count. Space complexity: O(n + k).

#include <iostream>
#include <cstdlib>
#include <ctime>

int findMaximum(int numbers[], int count) {
    int maximum = numbers[0];
    for (int i = 1; i < count; ++i) {
        if (numbers[i] > maximum) maximum = numbers[i];
    }
    return maximum;
}

void countingSortForRadix(int numbers[], int count, int exponent) {
    int output[count];
    int digitCounts[10] = {0};
    
    for (int i = 0; i < count; ++i) {
        digitCounts[(numbers[i] / exponent) % 10]++;
    }
    
    for (int i = 1; i < 10; ++i) {
        digitCounts[i] += digitCounts[i - 1];
    }
    
    for (int i = count - 1; i >= 0; --i) {
        int digit = (numbers[i] / exponent) % 10;
        output[digitCounts[digit] - 1] = numbers[i];
        digitCounts[digit]--;
    }
    
    for (int i = 0; i < count; ++i) numbers[i] = output[i];
}

void radixSort(int numbers[], int count) {
    int maxValue = findMaximum(numbers, count);
    for (int exponent = 1; maxValue / exponent > 0; exponent *= 10) {
        countingSortForRadix(numbers, count, exponent);
    }
}

int main() {
    srand(time(nullptr));
    const int TOTAL = 10;
    int numbers[TOTAL];
    
    for (int i = 0; i < TOTAL; ++i) numbers[i] = rand() % 1000;
    
    std::cout << "Initial: ";
    for (int i = 0; i < TOTAL; ++i) std::cout << numbers[i] << " ";
    std::cout << "\n";
    
    radixSort(numbers, TOTAL);
    
    std::cout << "Final: ";
    for (int i = 0; i < TOTAL; ++i) std::cout << numbers[i] << " ";
    std::cout << "\n";
    
    return 0;
}