Sort a vector containing only three distinct values

Question

I have a program that sorts the vector containing only 0,1,2 in the sequential order so the input array of [0,2,1,2,1] would generate an output [0,1,1,2,2].

Following is the functional code however I feel like considering the input [0,0,0,0,0,0,0,0,0,2,2,1], i and left are being iterated over the same elements and I feel we could reduce the iteration to one. I thought of setting i to left as long as left > i but I ended up running into an infinite loop (where left and right would keep i not get past the finish line).

Any ways to improve it?

    void SortNums(vector<int>& nums) 
    { 
        int right = nums.size()-1;
        int left = 0;

        for (int i=0; i < nums.size() && left < right; i++)
        {
            while (left < right && nums[left] == 0) left++;
            while (left < right && nums[right] == 2) right--;
            
            if (left >= right) break;
            
            if (i > left && nums[i] == 0) 
            {
                std::swap(nums[left], nums[i--]);
            }
            if (i < right && nums[i] == 2)
            {
                std::swap(nums[i--], nums[right]);
            }
        }   
   }

Answer 1

however I feel like considering the input [0,0,0,0,0,0,0,0,0,2,2,1], i and left are being iterated over the same elements

            while (left < right && nums[left] == 0) left++;
            while (left < right && nums[right] == 2) right--;

Those are some interesting hard-coded magic numbers.

The code doesn't spell out that the acceptable domain of input values is {0, 1, 2}, yet that is the operative assumption. I would find this code easier to read (e.g. identifiers like SortNums) if it described the use case for focusing on small integers. As it is, "num" and "int" suggests a much larger range.

---

Let us be explicit that the input values shall be integers ranging from 0 .. K. And the output shall be a sorted copy of the input.

Then an O(N log N) algorithm is a fool's game, when we can play to win! Use radix sort to solve it in O(N) time complexity and (at worst) O(K) space complexity, with K << N typically.

Here, allocate K counters, and make a linear pass over the input, incrementing the appropriate counter for each value. Then the output phase is simple. For the i-th counter, output a bunch of i values.

---

In short you are solving a restricted problem, which does not encompass what the general "sort" literature tackles.

Answer 2

Provide self-contained code

You are missing headers, and namespaces:

#include <utility>
#include <vector>

void SortNums(std::vector<int>& nums) {
    ...
}

Compile with warnings

On Clang and GCC, this means -Wall -Wextra -Werror.

Ensure correct integer types

The size of a std::vector is std::size_t, an unsigned integer, not int.

The indexes which you use to index over std::vector should also be std::size_t.

Note: comparisons between signed and unsigned integers can give weird results, the compiler would have warned about this.

Switch to a better type (C++20)

In the end, you never manipulate the vector size, or capacity. In fact, your function would work on any slice of int, regardless of whether they're from an array, a vector, or something else.

From C++20 onwards, you should use std::span<int> as an argument, instead.

Cache the vector size

The compiler may or may not be able to optimize nums.size(). It'll depend whether it manages to prove that the writes performed through nums[...] may or may not alter the size.

It's thus best practice to cache the size (or end iterator) when doing such iteration.

for (std::size_t i = 0, max = nums.size(); i < max && left < right; ++i) {
}

Use pre-increment

Use pre-increment when post-increment is unnecessary. While in practice for integral types the generated code will be the same, for complex iterators this is not the case, thus it's a good habit to get into.

Always wrap blocks with brackets

Always use brackets around blocks after a while, if, etc...

Apple's GOTO FAIL bug would have been easier to spot with the proper use of brackets, for example.

Use a better algorithm

Having a limited number of values is the text-book usecase for Counting Sort.

Assuming that we are specializing for [0, 2], this means:

#include <cassert>

#include <algorithm>
#include <span>
#include <utility>

void SortNums(std::span<int> nums) {
    //  The best way to document pre-conditions, is to enforce them.
    assert(std::all_of(nums.begin(), nums.end(),
        [](int i) { return 0 <= i && i <= 2; });

    std::size_t counts[3] = { 0, 0, 0 };

    for (auto i : nums) { ++counts[i]; }

    auto it = nums.begin();
    for (int i = 0; i < 3; ++i) {
        it = std::fill_n(it, counts[i], i);
    }
}

This algorithm has O(N) time complexity (two linear passes over the data) and O(1) extra space complexity.

It also likely triggers auto-vectorization of the write pass, and may trigger auto-vectorization of the read pass.

Answer 3

Consider a drastic change of interface - instead of sorting elements in-place, it might be better to return a histogram object with vector-like access:

histogram sorted(const std::input_range& auto nums);

We could implement the histogram as

#include <iterator>
#include <numeric>
#include <ranges>

// Special case histogram class that counts values that are 0, 1 or 2.
class histogram_012
{
    std::array<std::size_t,3> count{{ 0, 0, 0 }};

public:
    struct const_iterator
    {
        using difference_type = std::ptrdiff_t;
        using value_type = int;
        using pointer = int*;
        using reference = int&;
        using iterator_category = std::input_iterator_tag;

        const histogram_012 *p;
        std::size_t pos;

        constexpr auto operator<=>(const const_iterator& other) const = default;

        const_iterator& operator++()
        {
            ++pos; return *this;
        }

        auto operator*() const
        {
            // This is just for exposition; it's not efficient
            auto n = pos;
            int  i = 0;
            for (auto c: p->count) {
                if (n < c) { return i; }
                n -= c;
                ++i;
            }
            // out-of-range (undefined)
            return 0;
        }
    };

    template<std::ranges::input_range C>
    requires std::is_same_v<int, std::ranges::range_value_t<C>>
    explicit constexpr histogram_012(C const& nums)
    {
        std::size_t total = 0;
        for (int n: nums) {
            count[0] += (n == 0);
            count[1] += (n == 1);
            ++total;
        }
        count[2] = total - count[0] - count[1];
    }

    // Minimal container interface - this needs completing
    constexpr auto size() const { return std::accumulate(count.begin(), count.end(), std::size_t{}); }
    constexpr const_iterator begin() const { return {this, 0}; }
    constexpr const_iterator end() const { return {this, size()}; }
};

and sorted() as

constexpr auto sorted(auto const& nums) { return histogram_012{nums}; }

Simple demo:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
    std::vector<int> values = {0,2,1,2,1};
    auto const sorted_values = sorted(values);
    std::copy(sorted_values.begin(), sorted_values.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';
}

Credit to Peter Cordes for suggesting this approach, in comments to other answers.

An exercise for the interested reader is to create a generalised version that histograms a fixed set of values of a given type, i.e.

template<std::equality_comparable T, T... values> class histogram

Answer 4

I agree with the others that it would be best to just count the number of zeros, ones, and twos, and then to fill the vector accordingly. However, you asked how to simplify your loop, so I will present a solution that is similar in spirit to yours. My goal is to show how to reason about a loop like this and to ensure correctness (and termination, i.e. not to run into an infinite loop): Write down the invariants and ensure that you keep them and also make progress for each iteration.

    void SortNums(vector<int>& nums) 
    { 
        std::size_t right = nums.size();
        std::size_t left = 0;
        std::size_t i = 0;

        // We will keep these invariants all through the function
        // (with N = nums.size()):
        //     0 <= left <= i <= right <= N
        //     nums[k] == 0   for 0 <= k < left
        //     nums[k] == 1   for left <= k < i
        //     nums[k] == 2   for right <= k < N
        // The array will be sorted when  i == right.

        while (i < right)  // each iteration decreases right-i by 1
        {
            switch (nums[i])
            {
            case 0:
                // If  left == i, then we just need to increase
                // left and i.
                // If  left < i, then nums[left] == 1 and we want
                //    nums[left++] = 0;
                //    nums[i++] = 1;
                // The following works in both cases.
                std::swap(nums[left++], nums[i++]);
                break;
            case 1:
                ++i;
                break;
            case 2:
                std::swap(nums[i], nums[--right]);
                break;
            default:
                throw std::logic_error(
                    "element not 0,1,2 in SortNums");
            }
        }   
   }

As indicated in the comment, there will be exactly sums.size() iterations of the loop.

Regarding some style details, I don't know whether I would use pre-/post-increments in expressions, but you did, so I kept to that style. I have changed the index variables from int to size_t. There is an argument to be made for signed index variables, but int might not be large enough. Note that having unsigned index variable, I had to avoid - 1, so my right differs from yours by one. But I would have wanted that anyways, because now all of the intervals in the invariants are of the form ... <= k < ... as is customary. One could also use iterators instead of indexes, it is a matter of taste:

    auto left = nums.begin();
    auto right = nuts.end();
    auto it = left;

The comment in case 0 shows that there are some unnecessary reads of nums[left] there. One could optimise that but it would be at the expense of brevity, so I thought that it would be besides the point.

Answer 5

One way to optimize the implementation is to avoid iterating over the same elements multiple times. Here's a modified implementation that uses only one loop:

void SortNums(vector<int>& nums) 
{ 
    int left = 0, right = nums.size()-1, i = 0;
    
    while (i <= right)
    {
        if (nums[i] == 0)
        {
            std::swap(nums[i], nums[left]);
            left++;
            i++;
        }
        else if (nums[i] == 2)
        {
            std::swap(nums[i], nums[right]);
            right--;
        }
        else
        {
            i++;
        }
    }
}