Selection Sort

The selection algorithm operates by dividing the dataset into two conceptual regions: a sorted prefix and an unsorted suffix. During each pass, the method scans the unsorted region to locate the smallest value and swaps it with the leftmost unsorted element, effectively expanding the sorted prefix by one position.

• Mechanics: Iterate through the array starting from index zero. Track the index of the minimum value encountered. Once the full range is examined, exchange that minimum value with the element at the current starting position. Repeat for the remaining subarray.
• Performance Profile: Executes exactly O(n²) comparisons regardless of initial data distribution. Memory footprint remains constant at O(1) since operations occur directly within the provided container.
• Stability Characteristics: Classified as unstable. Swappping non-adjacent equal values can alter their original relative ordering.
• Optimal Use Cases: Environments with severe write-operation constraints. The algorithm performs at most n swaps, making it preferable over alternatives when writing to storage media is expensive.

#include <vector>
#include <utility>

void partitionAndSwapSort(std::vector<int>& dataset) 
{
    size_t totalElements = dataset.size();
    
    for (size_t pass = 0; pass < totalElements - 1; ++pass) 
    {
        size_t targetIndex = pass;
        
        for (size_t scan = pass + 1; scan < totalElements; ++scan) 
        {
            if (dataset[scan] < dataset[targetIndex]) 
            {
                targetIndex = scan;
            }
        }
        
        if (targetIndex != pass) 
        {
            std::swap(dataset[pass], dataset[targetIndex]);
        }
    }
}

Bubble Sort

This technique repeatedly traverses the collection, comparing neighboring pairs and swapping them whenever they appear out of sequence. Larger values progressively migrate toward the right boundary, resembling bubbles rising to the surface.

• Mechanics: Run sequential passes across the data. Within each pass, compare element i with element i+1. If the left value exceeds the right, perform a swapp. Conclude the pass once the largest remaining value settles at the end index.
• Performance Profile: Average and worst-case time complexity reaches O(n²). Best-case scenario drops to O(n) when the container is already ordered, detectable via an early-exit optimization flag.
• Stability Characteristics: Guaranteed stable. Swaps only occur between adjacent misordered elements, preserving the original sequence of identical keys.
• Optimal Use Cases: Pedagogical demonstrations and datasets that remain largely sorted throughout execution. High overhead limits practical deployment on large collections.

#include <vector>
#include <utility>

void adjacentComparisonSort(std::vector<int>& dataset) 
{
    size_t totalElements = dataset.size();
    bool didExchange = true;
    
    for (size_t limit = 0; limit < totalElements - 1 && didExchange; ++limit) 
    {
        didExchange = false;
        
        for (size_t idx = 0; idx < totalElements - limit - 1; ++idx) 
        {
            if (dataset[idx] > dataset[idx + 1]) 
            {
                std::swap(dataset[idx], dataset[idx + 1]);
                didExchange = true;
            }
        }
    }
}

Insertion Sort

Insertion methodology constructs the final ordered sequence incrementally. It treats the initial element as inherently sorted, then extracts subsequent items and slides larger preceding values rightward to create vacant slots for precise placement.

• Mechanics: Begin at the second position. Extract the current key value. Backtrack through the sorted segment, shifting elements greater than the key one position to the right. Once a smaller-or-equal element is ancountered or the boundary is reached, deposit the key.
• Performance Profile: Degrades to O(n²) under reversed inputs. Excels near O(n) performance when incoming data exhibits significant presorted patterns. Requires only O(1) auxiliary storage.
• Stability Characteristics: Naturally stable. The backward shifting mechanism maintains relative equality among duplicate keys.
• Optimal Use Cases: Real-time streaming data, hybrid sorting routines, and embedded systems where low cache misses and predictable memory access patterns outweigh raw throughput requirements.

#include <vector>

void buildSortedSequence(std::vector<int>& dataset) 
{
    size_t totalElements = dataset.size();
    
    for (size_t currentPos = 1; currentPos < totalElements; ++currentPos) 
    {
        int keyVal = dataset[currentPos];
        size_t moveBack = currentPos - 1;
        
        while (moveBack >= 0 && dataset[moveBack] > keyVal) 
        {
            dataset[moveBack + 1] = dataset[moveBack];
            --moveBack;
        }
        
        dataset[moveBack + 1] = keyVal;
    }
}