Vector Sort Function

Question

I had heard about sorting for a while, but never actually gave it a try. So I decided to make an algorithm that would sort the members of a vector from least to greatest. Though this may seem pretty simple and/or silly, I actually put a lot of thought into it and wrote out tables/diagrams.

#include <iostream>
#include <vector>

namespace{
    typedef unsigned int uint;
}

std::vector<int> sort(std::vector<int>a)
{
    for (int i = 1; i < a.size(); ++i){
        for (int j = 0; j < a.size() - 1; ++j){
            if (a[j] > a[i]) std::swap(a[j], a[i]);
        }
    }

    return a;
}

int main()
{
    std::vector<int> a = { 17, 12, 1, 20, 4, 6, 94 };

    for (uint i = 0; i < a.size(); ++i){
        std::cout << sort(a)[i] << std::endl;
    }
}

I know there's probably some sort function part of the standard C++ library, but for a sort function from scratch, how efficient is this? What could I do to improve it?

Answer 1

It's not ideal to call sort() for each element. The first call already gives you the sorted vector, so each additional call just needlessly overwrites it. This approach would also be very slow if the vector were much larger.

Since you're already returning a vector, you just need to sort once and then print once:

int main()
{
    std::vector<int> a = { 17, 12, 1, 20, 4, 6, 94 };

    a = sort(a);

    for (auto& iter : a)
    {
        std::cout << iter << "\n";
    }
}

There's also no need for the typedef. To help ensure you're using the proper type, you can use auto instead. You should also replace the ints in sort() with auto. Having higher compiler warnings would've alerted you to this type mismatch.

Answer 2

Your sort() function takes a std::vector<int> parameter and returns a std::vector<int>, which means that calling sort() makes a copy of the entire vector. This is uncommon in C++, where operations are typically done in-place for performance. (If the caller wants a sorted copy, then it's the caller's responsibility to make a copy first.) To avoid copying, accept a std::vector<int>& instead. It's also common to return void to emphasize the fact that the sorting was done in place — that's what std::sort() does.

Speaking of performance, bubble sort (which is what you have written) is only recommended for small vectors, as its performance is O(n²).

There's no need to write your own typedef. vector::size() returns a vector::size_type, which is basically size_t. If you use it in main(), you should use it in sort() too, for consistency. Note that since you are using C++11, a range-based for loop would be preferable.

void sort(std::vector<int> &a) {
    for (size_t i = 1; i < a.size(); ++i) {
        for (size_t j = 0; j < a.size() - 1; ++j) {
            if (a[j] > a[i]) std::swap(a[j], a[i]);
        }
    }
}

int main() {
    std::vector<int> a = { 17, 12, 1, 20, 4, 6, 94 };
    sort(a);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cout << a[i] << '\n';
    }
}