4
\$\begingroup\$

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]);
            }
        }   
   }
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is there some reason you can't use std::sort() (or std::ranges::sort()) from the <algorithm> library? Or are you intentionally reinventing-the-wheel? \$\endgroup\$ Feb 11, 2023 at 10:38
  • \$\begingroup\$ And is vector here an alias of std::vector, or something else? You'll get better reviews if you provide code that's complete, with the necessary headers or other definitions for it to compile. \$\endgroup\$ Feb 11, 2023 at 10:41
  • 5
    \$\begingroup\$ Have you considered Counting Sort? With only 3 distinct values, you can turn large arrays into a very compact histogram, which you can expand back into a sorted array if you want. If the 3 values are in a small known range, you can index an array of counts, otherwise switch or if/else if/else. (I'd recommend against a std::unordered_map hash table for only 3 elements.) See Micro Optimization of a 4-bucket histogram of a large array or list for how to count very fast with SIMD for 32-bit elements. \$\endgroup\$ Feb 11, 2023 at 20:26
  • \$\begingroup\$ @TobySpeight it's std::vector. And I am "reinventing the wheel" if you want to put it that way. \$\endgroup\$
    – xyf
    Feb 11, 2023 at 21:03

5 Answers 5

6
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ I was clear in the description that the vector would only contain 0,1,2. Not sure what wasn't clear about the acceptable domain of input values... \$\endgroup\$
    – xyf
    Feb 11, 2023 at 6:35
  • 1
    \$\begingroup\$ @xyf you were clear about that in the post you created on codereview.stackexchange.com... but nowhere in your code do you actually document that. That's all that J_H has suggested you should do: your function's signature and documentation (and implementation) should make it obvious to readers of your code, and users of your function's public API while coding, what it does. \$\endgroup\$
    – minseong
    Feb 11, 2023 at 17:46
  • \$\begingroup\$ This sounds more like counting sort, no? \$\endgroup\$
    – Rish
    Feb 11, 2023 at 18:23
  • 5
    \$\begingroup\$ An array of K counters is Counting Sort. Radix Sort is when you make multiple passes using a range of bits to divide into buckets, e.g. group based on top 8 bits, then within those buckets group based on the next-lowest 8 bits. Counting Sort is sort of a special case of Radix Sort where you use the whole number to index a bucket, but unlike Radix Sort (@G.Sliepen) there are no other bits to record so you can just count instead of growing a list. \$\endgroup\$ Feb 11, 2023 at 20:34
  • 3
    \$\begingroup\$ @xyf Your question is actually fine and a good question, but maybe you have unreasonable expectations of this site. Answerers have gone out of their way to give you a code review: recommending that your source code clarifies acceptable inputs is a code review. I think it shouldn't matter whether feedback that can help you is in the form of written prose or code examples, sometimes writing is even more appropriate. Why do you not value answers that are not working blocks of code? \$\endgroup\$
    – minseong
    Feb 11, 2023 at 21:52
6
\$\begingroup\$

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.

\$\endgroup\$
13
  • 3
    \$\begingroup\$ That's en.wikipedia.org/wiki/Counting_sort not Radix Sort, as discussed in comments under J_H's answer. Re: choice of var name: I'd avoid i for the loop over nums, e.g. for (auto num : nums) { ++counts[num]; }. Normally i is a loop counter for counted loops, not an arbitrary integer loaded from another array. \$\endgroup\$ Feb 11, 2023 at 20:37
  • 1
    \$\begingroup\$ @pacmaninbw: I think you meant to comment under the question, not this answer. \$\endgroup\$ Feb 11, 2023 at 20:40
  • 1
    \$\begingroup\$ For high-performance histogramming of a very small number of unique values, see See Micro Optimization of a 4-bucket histogram of a large array or list for how to count very fast with SIMD for 32-bit elements, in that case C++ with AVX2. With two pcmpeq/psubd in the loop to count 0s and 1s, you can derive the count for 2 from size - ones - zeros; Zen 2 or Ice Lake could potentially handle 8 ints per clock cycle. \$\endgroup\$ Feb 11, 2023 at 20:43
  • 1
    \$\begingroup\$ For highly-redundant data like a large array of 3 unique values, a compact data structure like a 3-entry histogram is often usable instead of a sorted array, so I'd recommend making that available as an output of this function, or split to multiple functions so you can just histogram without wasting time expanding again. \$\endgroup\$ Feb 11, 2023 at 20:45
  • 1
    \$\begingroup\$ @xyf: Yours has a bunch of data-dependent branching, which is relatively slow on modern high-performance CPUs compared to loads/stores that hit in L1d cache. Some CPUs (Zen 2 and Zen 4, and Ice Lake) can even remove the store/reload forwarding latency bottleneck of a standard scalar histogram incrementing the same memory location multiple times in a row, by optimizing store-forwarding for the same address (accessed with the same addressing-mode). agner.org/forum/viewtopic.php?t=41 / chipsandcheese.com/2022/11/08/… \$\endgroup\$ Feb 12, 2023 at 4:42
3
\$\begingroup\$

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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ For 3 distinct values, using a simple array of counters is a nice approach. It doesn't scale well, though, as the "random access" property is lost for larger Ns, but that can be recovered by switching to a Fenwick Tree -- my favorite exotic data-structure -- which can give O(log N) read/write. \$\endgroup\$ Feb 17, 2023 at 15:41
  • 1
    \$\begingroup\$ Nice idea to have iterators for it that work like the expanded array; you'd also want direct access to the histogram and/or a prefix-sum for algorithms that can be tweaked to deal with that. I'd been picturing returning that for direct use by callers that could be adapted for it. You'd probably also want to provide a function that can std::fill the histogram back into a sorted array, for any callers you haven't specialized for histograms and which can't use operator*. \$\endgroup\$ Feb 17, 2023 at 19:08
  • \$\begingroup\$ The count loop can be optimized to only count 0 and 1 elements, with count[2] = nums.size() - count[0] - count[1] after the loop. \$\endgroup\$ Feb 17, 2023 at 19:08
  • \$\begingroup\$ Yes, although nums.size() doesn't necessarily exist for a std::ranges::input_range - but we could overload that constructor for std::ranges::sized_range, or just maintain a count as we loop. \$\endgroup\$ Feb 18, 2023 at 9:45
  • \$\begingroup\$ Yes, I realised that afterwards @G.Sliepen. Now fixed. Don't need to find a counter for the T I think, because we naturally have the index that as we test each value. \$\endgroup\$ Feb 18, 2023 at 16:14
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Aren't you doing unnecessary swaps? if the input is [0,0,0,0,0,0,0,0,2,1], you'd be swapping all the 0s for no real purpose \$\endgroup\$
    – xyf
    Feb 12, 2023 at 19:08
  • \$\begingroup\$ @xyf yes, that's what my last sentence was about. One could optimize this, but that would only be an improvement for certain inputs. If you add a 1 to the beginning of your example you need to do those swaps anyway. \$\endgroup\$
    – Carsten S
    Feb 13, 2023 at 1:24
  • \$\begingroup\$ You wouldn't need to do that many swaps, though, if you think beyond Bubble Sort logic for getting a 1 to the other side of a long run of 0s. If you scan until a non-zero, you can swap the 1 with the last 0, leaving the intervening 0s in place. (If compilers were smarter, checking 16 or 32 bytes at a time for the first non-zero element with AVX2 could go much faster than swapping; with real compilers only somewhat faster.) If that idea only helps at the very start of the array, it might be worth leaving it out if you know that tends not to happen in your real data. (@xyf) \$\endgroup\$ Feb 17, 2023 at 19:18
0
\$\begingroup\$

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++;
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ So you agree with my answer :) \$\endgroup\$
    – Carsten S
    Feb 18, 2023 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.