C++ implementations of common sorting algorithms

Sorting Algorithms.cpp

//Author: Eshwary Mishra 2023

/**
 * This file will give implementations for common sorting algorithms implemented in C++
 * 
 * For simplicity, we will use a vector for our lists. It should be noted that this can be copy
 * paste replaced for any list type that implements the [a] operator for finding an element at position
 * a and the internal element implements the <, >, and == operators. If either is not the case, then
 * the implementation must be modified.
 * 
 * Selection sort - Holds first element in place and swaps it with the smallest element in the list. Repeats for second, third, etc.
*/

#include <vector>

/**
 * Most sorting algorithms need a swap function
*/
static void swap(std::vector<int>& list, int index_a, int index_b)
{
    int temp = list[index_a];
    list[index_a] = list[index_b];
    list[index_b] = temp;
}

/**
 * Selection sorts the list. Selection sort holds the first element in place swaps it with the lowest 
 * remaining element in the list. This process is repeated until the list is fully sorted
 * 
 * O(n^2)
*/
static const std::vector<int> selection_sort(const std::vector<int>& list)
{
    //Do not modify original, we create a new sorted version instead
    std::vector<int> new_list = list;

    for(int i = 0; i < new_list.size(); ++i)
    {
        //Find the minimum element in the array
        int current_smallest_element_index = i;

        //Start at current pass + 1 since we need one element of buffer
        for(int j = i + 1; j < new_list.size(); ++j)
        {
            if(new_list[j] < new_list[current_smallest_element_index])
                current_smallest_element_index = j;
        }

        //After finding the current smallest element, swap the smallest element with the one held in place
        if(current_smallest_element_index != i)
            swap(new_list, current_smallest_element_index, i);
    }

    return new_list;
}

/**
 * Quicksort requires a helper function to partition the array
 * This function returns the location of the pivot
*/
static const int partition(std::vector<int>& list, int start, int end)
{
    int pivot = list[end];
    int i = start - 1;

    for(int j = start; j <= end - 1; ++j)
    {
        if(list[j] < pivot)
        {
            i++;
            swap(list, j, i);
        }
    }

    i++;
    swap(list, i, end);
    return i;
}

/**
 * Quick sorts the list. Quicksort is a recursive algorithm that follows the divide and conquer technique
 * 
 * Best: O(nlog(n))
 * Average: O(nlog(n))
 * Worst: O(n^2)
*/
static const void quick_sort(std::vector<int>& list, int start, int end)
{
    //If our starting index is equal to or has surpassed the ending index, then the algorithm is finished
    if(start >= end)
        return;
    
    int pivot = partition(list, start, end);
    quick_sort(list, start, pivot - 1);
    quick_sort(list, pivot + 1, end);
}