Skip to main content
added 3 characters in body
Source Link
Matthieu M.
  • 6.4k
  • 1
  • 20
  • 34

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

#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::fillfill_n(it, it + counts[i], i);
        it += counts[i];
    }
}

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

#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) {
        std::fill(it, it + counts[i], i);
        it += counts[i];
    }
}

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

#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);
    }
}
Source Link
Matthieu M.
  • 6.4k
  • 1
  • 20
  • 34

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 Radix 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) {
        std::fill(it, it + counts[i], i);
        it += counts[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.