My C++ sorting algorithm for vector

Question

As I'm learning c++, I decided to implement my own sorting algorithm. As I'm a beginner I didn't use any template to be able to use them for different types of variable and they can only sort item in a vector. I implemented bubble sort, selection sort, insertion sort, merge sort and quick sort. I'm not asking you to review all my code but you can if you want to, any advice on something that strike you are welcome. Here is my code :

#include <iostream>
#include <vector>

void display_vector(const std::vector<int>& to_display);

void bubble_sort(std::vector<int>& to_sort);
void bubble_sort_optimized(std::vector<int>& to_sort);
void selection_sort(std::vector<int>& to_sort);
void insertion_sort(std::vector<int>& to_sort);
std::vector<int> merge_sort(std::vector<int>& to_sort);
void quick_sort_rec(std::vector<int>& to_sort, int start, int end);
inline void quick_sort(std::vector<int>& to_sort);
int ind_min(const std::vector<int>& v, const int& i);
int partition(std::vector<int>& v, int start, int end);
std::vector<int> merge(std::vector<int>& v1, std::vector<int>& v2);
std::vector<int> get_from_to(std::vector<int>& v, unsigned int start, unsigned int end);

int main()
{
    std::vector<int> vector_to_sort = { -5,2,4,1,8,3,8,9,1,10 };
    std::vector<int> sorted_vector;

    quick_sort(vector_to_sort);

    display_vector(vector_to_sort);
}


void bubble_sort(std::vector<int>& to_sort)
{
    //For the i-iteration we loop the n-(i+1) value and swap if two following value are not sorted
    for (unsigned int i = 1; i < to_sort.size(); ++i)
    {
        for (unsigned int k = 0; k < to_sort.size() - i; ++k)
        {
            if (to_sort[k] > to_sort[k + 1])
            {
                int value = to_sort[k];
                to_sort[k] = to_sort[k + 1];
                to_sort[k + 1] = value;
            }
        }
    }
    //Time complexity : O(n^2) where n is the size of the vector in any case
}


void bubble_sort_optimized(std::vector<int>& to_sort)
{
    unsigned int i = 1;
    bool sorted = false;
    while (i < to_sort.size() && !sorted)
    {
        sorted = true;
        for (unsigned int k = 0; k < to_sort.size() - i; ++k)
        {

            if (to_sort[k] > to_sort[k + 1])
            {
                int value = to_sort[k];
                to_sort[k] = to_sort[k + 1];
                to_sort[k + 1] = value;
                sorted = false;
            }
        }
    }
    //Time complexity : O(n^2) where n is the size of the vector in the worse case, in the best case O(n)
}



void selection_sort(std::vector<int>& to_sort)
{
    //For the i-iteration we find the index superior or egal to i of the minimal value in the vector and we put it in at the i-place
    for (unsigned int i = 0; i < to_sort.size(); ++i)
    {
        int ind_swap = ind_min(to_sort, i);
        int temp = to_sort[i];
        to_sort[i] = to_sort[ind_swap];
        to_sort[ind_swap] = temp;
    }
    //Time complexity : O(n^2) where n is the size of the vector in the worst case, in the best case O(n)
}


void insertion_sort(std::vector<int>& to_sort)
{
    //For the i-iteration we suppose the vector to be sort for the i-1 first value we insert the i-value into the i-1 value to keep it sort
    for (unsigned int i = 1; i < to_sort.size(); ++i)
    {
        int value = to_sort[i];
        int k = i;
        while (k > 0 && to_sort[k - 1] > value)
        {
            to_sort[k] = to_sort[k - 1];
            k--;
        }
        to_sort[k] = value;

    }
    //Time complexity : O(n^2) where n is the size of the vector in the worst case, in the best case O(n)
}

int ind_min(const std::vector<int>& v, const int& i)
{
    int min = v[i];
    int ind_min = i;

    for (unsigned int k = i + 1; k < v.size(); ++k)
    {
        if (v[k] < min)
        {
            min = v[k];
            ind_min = k;
        }
    }

    return ind_min;
}



std::vector<int> merge_sort(std::vector<int>& to_sort)
{
    if (to_sort.size() <= 1)
    {
        return to_sort;
    }
    else
    {
        unsigned int mid = to_sort.size() / 2;
        std::vector<int> left;
        std::vector<int> right;
        left.reserve(mid);
        right.reserve(to_sort.size() - mid);

        left = get_from_to(to_sort, 0, mid);
        right = get_from_to(to_sort, mid, (unsigned int) to_sort.size());

        left = merge_sort(left);
        right = merge_sort(right);

        return merge(left, right);
    }
    //Time complexity : O(n*ln(n)) where n is the size of the vector
}

std::vector<int> merge(std::vector<int>& v1, std::vector<int>& v2)
{
    unsigned int n1 = v1.size();
    unsigned int n2 = v2.size();
    unsigned int i1 = 0;
    unsigned int i2 = 0;

    std::vector<int> merged;

    while (i1 < n1 and i2 < n2)
    {
        if (v1[i1] < v2[i2])
        {
            merged.push_back(v1[i1]);
            ++i1;
        }
        else
        {
            merged.push_back(v2[i2]);
            ++i2;
        }
    }

    while (i1 < n1)
    {
        merged.push_back(v1[i1]);
        ++i1;
    }
    while (i2 < n2)
    {
        merged.push_back(v2[i2]);
        ++i2;
    }
    return merged;
}

std::vector<int> get_from_to(std::vector<int>& v, unsigned int start, unsigned int end)
{

    if (start == end)
    {
        std::cout << "get_from_to ERROR start index = end index";
        return std::vector<int>();
    }
    std::vector<int> extrated;
    extrated.reserve(end - start - 1);
    for (unsigned int k = start; k < end; ++k)
    {
        extrated.push_back(v[k]);
    }
    return extrated;
}


void quick_sort_rec(std::vector<int>& to_sort, int start, int end)
{
    if (start == end)
    {
        return;
    }
    else
    {
        int p = partition(to_sort, start, end);
        quick_sort_rec(to_sort, start, p);
        quick_sort_rec(to_sort, p + 1, end);
    }
}

inline void quick_sort(std::vector<int>& to_sort)
{
    quick_sort_rec(to_sort, 0, to_sort.size());
}

int partition(std::vector<int>& v, int start, int end)
{
    int value = v[start];
    int p = start;
    for (int k = start + 1; k < end; ++k)
    {
        if (v[k] < value)
        {
            v[p] = v[k];
            v[k] = v[p + 1];
            v[p + 1] = value;
        }
    }
    return p;
}


void display_vector(const std::vector<int>& to_display)
{
    for (unsigned int i = 0; i < to_display.size() -1 ; ++i)
    {
        std::cout << to_display[i] << ", ";
    }
    std::cout << to_display[to_display.size() - 1] << '\n';
}

PS : Forgive my English, I'm French but I will try my best to be able to respond to your advice.

Answer 1

Let's go through the functions and see what can be improved.

main

The sorted_vector variable is not used. Remember to enable compiler warnings.

You only test the quick_sort function. Consider testing other functions as well.

bubble_sort

The correct type to index a std::vector<int> is std::vector<int>::size_type. std::size_t (defined in header <cstddef>) is also fine, but unsigned int is not appropriate.

Instead of looping to to_sort.size() - i, why not simply set i to the correct bound?

Use std::swap (defined in header <utility>) to swap two values instead of manually introducing a third variable.

In bubble_sort_optimized, i doesn't increase, so the function does unnecessary work.

selection_sort

This function can be simplified with std::iter_swap (defined in header <utility>) and std::min_element (defined in header <algorithm>):

void selection_sort(std::vector<int>& to_sort)
{
    for (auto it = to_sort.begin(); it != to_sort.end(); ++it) {
        std::iter_swap(it, std::min_element(it, to_sort.end()));
    }
}

The ind_min function can be removed.

merge_sort

The function has a strange interface — it mutates the input vector and returns a new vector.

The get_from_to function is also not useful, because std::vector already has the functionality:

void merge_sort(std::vector<int>& to_sort)
{
    if (to_sort.size() <= 1) {
        return;
    }
    auto mid = to_sort.begin() + to_sort.size() / 2;
    std::vector left(to_sort.begin(), mid);
    std::vector right(mid, to_sort.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(), to_sort.begin());
}

Note that std::merge (defined in header <algorithm>) does the job of merge.

quick_sort

You are using int to index the vector — that's even worse than unsigned int.

You don't have to mark quick_sort inline — unless you are implementing the function in a header, in which case all non-template functions need to be inline in order to prevent ODR violations.

display_vector

This function has a bug: the function accesses invalid memory if to_display is empty, in which case to_display.size() - 1 returns SIZE_MAX (which is typically 4294967295 or 18446744073709551615) instead of -1, since to_display.size() is an unsigned value! The empty case needs to be handled specially anyway. For other cases, use std::ostream_iterator (defined in header <iterator>):

void display_vector(const std::vector<int>& to_display)
{
    if (to_display.empty()) {
       return;
    }
    std::copy(to_display.begin(), to_display().end() - 1,
              std::ostream_iterator<int>{std::cout, ", "});
    std::cout << to_display.back() << '\n';
}

Answer 2

Thank you for not using using namespace std;.

Enclosing all blocks of code in {} is a good practice that I promote, so thank you for that good practice as well.

In C and C++ you don't really need that large block of function declarations at the top if all the functions are in the proper order, but in some cases this is a matter of style, in other cases if 2 functions call each other function prototypes are necessary.

Missing Header File

To use and as the logical AND operator the header file iso646.h should be included, otherwise it might be better to use && as the logical AND operator. Not all C++ compilers include this by default.

Proper Testing of Sort Functions

If you really want to properly test the functions you should have a vector that has the properly sorted values to compare the returned values of the a sort function.

Not All Functions are Used

This is sometimes a sign that the code is not ready for review or Ready for Use by Others (RFUBO). In this case I believe it is because the testing hasn't really been thought out and only one test will work at a time.

One way to correct this is to not use the input vector as the output. Instead each sort function can return a sorted vector rather than each function being void.

std::vector<int> bubble_sort(std::vector<int> to_sort);
std::vector<int>  insertion_sort(std::vector<int> to_sort);

bool vectors_are_equal(std::vector<int> sorted, std::vector<int> control)
{
    if (sorted.size() != control.size())
    {
        return false;
    }

    for (int i = 0; i < control.size(); i++)
    {
        if (sorted[i] != control[i])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    std::vector<int> vector_to_sort = { 10, 8, 4, 1, 8, 3, 2, 9, 1, -5 };
    std::vector<int> control = { -5, 1, 1, 2, 3, 4, 8, 8, 9, 10};

    std::vector<int> sorted_vector = bubble_sort(vector_to_sort);
    std::cout << "Bubble Sort Test " << ((vectors_are_equal(sorted_vector, control)) ? "Passed" : "Failed") << "\n";
    display_vector("Bubble Sort", sorted_vector);
    std::cout << "\n";

    sorted_vector.clear();
    sorted_vector = insertion_sort(vector_to_sort);
    std::cout << "Insertion Sort Test " << ((vectors_are_equal(sorted_vector, control)) ? "Passed" : "Failed") << "\n";
    display_vector("Insertion Sort", sorted_vector);

}

It might be interesting to add timing to the tests to see what's faster. It might also be interesting to use a random number generator to populate the vector_to_sort, and larger ranges of numbers would also be interesting.

Note I've changed the order of some of the values in the vector_to_sort so that there are a couple of worst case scenarios.

Much code duplication of testing could be corrected by a function that takes the name and a function pointer of the sort to be tested.

Inline Functions

The C++ keyword inline is obsolete, current optimizing compilers do a much better job of inlining functions as necessary.