Dutch National flag solution in C++

Question

this week I learned about QuickSort and used the technique to solve the Dutch National Flag problem. I would appreciate it if someone would review my code and give feedback.

The Dutch national flag problem is a computer science programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

Code:

pair<int, int> Partition(vector<int> &nums, int low, int high) {
  int pivotElement = nums.at(low), lt = low, gt = high, i = low + 1;
  while (i <= gt) {
    // case of left parition
    if(pivotElement > nums.at(i)) {
      std::swap(nums.at(i), nums.at(lt));
      ++lt;
    } // below if the case of right partition
    else if (pivotElement < nums.at(i)) {
      std::swap(nums.at(i), nums.at(gt));
      --gt;
    }
    ++i;
  }
  return std::make_pair(lt, gt);
}

void DutchFlag(vector<int> &nums, int low, int high) {
  pair<int, int> p = std::make_pair(0, 0);
  if(low < high) {
    p = Partition(nums, low, high);
    DutchFlag(nums, low, p.first);
    DutchFlag(nums, p.second, high);
  }
}

int main() {
  std::vector<int> nums = {0, 1, 2, 2, 2, 1, 0, 0};
  DutchFlag(nums, 0, nums.size() - 1);
  std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, " "));
}

Answer 1

That's pretty good! Some small points...

Motivation

As, some of the comments point out, standard algorithms exist for std::sort and std::partition. You seem to be doing this in order to learn about algorithm implementation. That's fine and good for learning. Please be aware that in general / commercial / production code you should probably not be writing this and should use the above standard library functions instead.

Completeness

As some other comments point out, please try to post complete code. ie include the #include statements so that the code compiles and runs as posted.

Form / style / minor

• It is generally discouraged to use using namespace std;; which would be required to make your code work, because that includes a whole namespace and can cause clashes.
• Generally avoid declaring more than one variable on one line.
• The size() of containers returns std::size_t, which is usually an unsigned long. If you enable -Wall -Wextra (on gcc / clang) during compilation this will often give you warnings when you are comparing with int. Your code as posted as actually OK on this front, but it is still good practice to use std::size_t for those integers which represent an index into a vector or similar (bigger max value too, for very large vectors). I usually write a using std::size_t to avoid having to repeat std:: for each variable declaration.
• using at() is slower than operator[] because it does bounds checking. This might be what you intended, but given the "closed" nature of the algorithm it should be possible to use operator[] without errors or undefined behaviour.
• You could use try using default params to DutchFlag() for low/high to avoid the caller having to specify 0, size() in the external API.
• In general C++ and the STL tend to use Iterators and not vector indeces. So it would be more idiomatic for DutchFlag to take begin(), end() iterators.
• C++ (like python) also uses the "one past the end" convention for a range of iterators, so DutchFlag (as written) should probably be taking 0, size() and some of your <= should change to <.

Algorithm

I am not an expert on the Dutch flag algo. Clearly a plain quicksort, which you have implemented, works. Are there some efficiencies which can be gained from the knowledge that there are lots of repeats and only 3 possible values? If there are, you should probably try to achieve some of those. Otherwise this is just quicksort? See the example code on std::partition reference page.

For example, one might imagine an algorithm where you just have a local int counts[3]{0} run through the unsorted data and counts[v]++. Then produce an answer which repeats each value count[v] number of times. This is O(N) as opposed to quicksort which is generally O(NlogN).

Something along these lines:

#include <array>
#include <iostream>
#include <iterator>
#include <vector>

using std::size_t;

void DutchFlag(std::vector<int>& nums) {
  auto counts = std::array<size_t, 3>{0};

  for (auto n: nums) ++counts[n];

  auto start = std::begin(nums);
  for (int i = 0; i < 3; ++i) {
    auto end = std::next(start, counts[i]);
    std::fill(start, end, i);
    start = end;
  }
}

int main() {
  std::vector<int> nums = {0, 1, 2, 2, 2, 1, 0, 0};
  DutchFlag(nums);
  std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, " "));
}

It depends on what your motivation is, but such an algorithm would likely be faster for very large inputs and the code is probably simpler (than implementing quicksort by hand).