0
\$\begingroup\$

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, " "));
}
\$\endgroup\$
  • 2
    \$\begingroup\$ #include <algorithm> #include <iostream> #include <iterator> #include <utility> #include <vector> using std::pair; using std::vector; \$\endgroup\$ – Deduplicator Jan 19 at 18:02
  • 1
    \$\begingroup\$ Is there any reason not to use std::sort in your code? Or, if you want to avoid std::sort for some reason, why not use std::partition? \$\endgroup\$ – Quuxplusone Jan 19 at 18:03
5
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Thank you Oliver for the points. I am writing this code to learn about algorithms hence did not use STL. I usually do not do using namespace std;, only did using vector; using pair in the code. Thanks for all the other tips and for going through my code. I will keep the tips in mind. I will make sure that I am writing the complete code so that it compiles, I did not write the includes. \$\endgroup\$ – Rahul Wadhwani Jan 19 at 21:09
  • 1
    \$\begingroup\$ @RahulWadhwani Great. I noticed that you have a couple of other open questions which have reasonable answers, but you have not accepted any answers on those. Please ensure your "click the tick" if you receive an answers which is reasonably complete and useful. \$\endgroup\$ – Oliver Schönrock Jan 19 at 21:31
  • 1
    \$\begingroup\$ Thanks for noticing. I have selected answers on the rest of the questions. \$\endgroup\$ – Rahul Wadhwani Jan 20 at 15:20
  • \$\begingroup\$ @RahulWadhwani Great. Well done. I added an alternative algorithm with O(N) complexity. See above. \$\endgroup\$ – Oliver Schönrock Jan 20 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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