title: How to get move, swap and compare count for quicksort in C++
body: <p>I wrote some code snippet in order to get move, swap and compare count for quicksort in C++, but it only gave me compare count. Didn't find a good answer in google. Can someone have a look at the following code and give me some clue? Thanks a lot.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  #include &lt;iomanip&gt;
  #include &lt;random&gt;
  #include &lt;utility&gt;
  #include &lt;iterator&gt;
  #include &lt;cstdlib&gt;
  #include &lt;chrono&gt;
  #include &lt;inttypes.h&gt;
  #include &lt;unistd.h&gt;
  uint64_t swapcnt, cmpcnt, defaultctorcnt, argctorcnt, copyctorcnt, assigncnt, movecnt;
  std::chrono::high_resolution_clock::time_point start, end;
  
  class MyData {
  public:
      MyData();
      MyData(int n);
      MyData(const MyData&amp; rhs) {argctorcnt++; data = rhs.data; }
      MyData(MyData&amp;&amp; rhs) {movecnt++; data = rhs.data; }
      MyData&amp; operator=(const MyData&amp; rhs) {copyctorcnt++; if(this==&amp;rhs) return *this; data=rhs.data; return *this;}
      MyData&amp; operator=(const MyData&amp;&amp; rhs) {movecnt++; if(this==&amp;rhs) return *this; data=rhs.data; return *this;}
    bool operator==(const MyData&amp; ohs) const {cmpcnt++; return data==ohs.data;}
      ~MyData();
      bool operator&lt;(const MyData&amp; oh) const;
      void set(int n){data=n;}
      void swap(MyData&amp; rhs) {
          int tmp = data;
          data = rhs.data;
          rhs.data = tmp;
          swapcnt++;
      }
  private:
      int data;
  };
  
  namespace std{
  template&lt;&gt;
  void swap(MyData&amp; lhs, MyData&amp; rhs) {
      swapcnt++;
      lhs.swap(rhs);
  }
  }
  
  MyData::MyData() {
      data=0;defaultctorcnt++;
  }
  
  MyData::MyData(int n) {
      data=n; argctorcnt++;
  }
  MyData::~MyData() {
  
  }
  bool MyData::operator&lt;(const MyData&amp; rhs) const {
      cmpcnt++;
      return data&lt;rhs.data;
  }
  
  template &lt;class ForwardIt&gt;
   void quicksort(ForwardIt first, ForwardIt last)
   {
      if(first == last) return;
      auto pivot = *std::next(first, std::distance(first,last)/2);
      ForwardIt middle1 = std::partition(first, last,
                           [pivot](const auto&amp; em){ return em &lt; pivot; });
      ForwardIt middle2 = std::partition(middle1, last,
                           [pivot](const auto&amp; em){ return !(pivot &lt; em); });
      quicksort(first, middle1);
      quicksort(middle2, last);
   }
  
  void clearcnts() {
      swapcnt=0, cmpcnt=0; defaultctorcnt=0, argctorcnt=0, copyctorcnt=0, assigncnt=0; movecnt=0;
  }
  
  template&lt;typename T&gt;
  void checkresult(std::string name, T&amp; datasorted, T&amp;  dataset2) {
      if(!std::equal(datasorted.begin(), datasorted.end(), dataset2.begin(), dataset2.end()))
          std::cout &lt;&lt;name &lt;&lt; " sort result " &lt;&lt; "not equal"&lt;&lt; std::endl;
      std::cout &lt;&lt; name &lt;&lt;"\t compare count "
              &lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(10)&lt;&lt; cmpcnt
              &lt;&lt; ", swap count " &lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(10)&lt;&lt; swapcnt
              &lt;&lt;", defaultctorcnt="&lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(2)&lt;&lt; defaultctorcnt
              &lt;&lt;", argctorcnt="&lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(10)&lt;&lt;argctorcnt
              &lt;&lt;", copyctorcnt=" &lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(10)&lt;&lt;copyctorcnt
              &lt;&lt;", assigncnt="&lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(2)&lt;&lt;assigncnt
              &lt;&lt;", movecnt="&lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(10)&lt;&lt;movecnt
              &lt;&lt;", total="&lt;&lt;std::dec&lt;&lt;std::setfill(' ')&lt;&lt;std::setw(10)&lt;&lt;swapcnt + cmpcnt + defaultctorcnt + argctorcnt + copyctorcnt + assigncnt+movecnt
              &lt;&lt;" in " &lt;&lt;std::setfill(' ')&lt;&lt;std::setw(6)&lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end - start).count() &lt;&lt; " ms"&lt;&lt;std::endl;
  }
  void sortn(int cnt) {
      std::vector&lt;MyData&gt; dataset(cnt);
      srand (time(NULL));
      for(auto&amp; data:dataset) // thanks to the answer from Rumburak
          data.set( rand());
      std::vector&lt;MyData&gt; datasorted=dataset;
      std::sort(datasorted.begin(), datasorted.end());
      {
          std::vector&lt;MyData&gt; dataset2=dataset;
          clearcnts();
      start = std::chrono::high_resolution_clock::now();
          quicksort(dataset2.begin(), dataset2.end());
      end = std::chrono::high_resolution_clock::now();
          checkresult("quicksort", datasorted, dataset2);
      }
  }
  
  int main(int argc, char* argv[]) {
      int cnt = 102400*54;
      if(argc&gt;1)
          cnt=atoi(argv[1]);
      std::cout &lt;&lt; "check compare and swap when sorting " &lt;&lt;cnt &lt;&lt; " objects" &lt;&lt; std::endl; //
      for(int i=0; i&lt;1; i++) {
          std::cout &lt;&lt; i &lt;&lt; "th execution\n";
          sortn(cnt);
          usleep(rand()%37+5);
      }
      return 0;
  }
  </code></pre>
  
  <p>To build the code: g++ -o qsortcnt -std=c++1y qsortcnt.cpp</p>
  
  <p>With the help from Rumburak, now the program seems produce reasonable output:
  Output of the program: quicksort        compare count  254998866, swap count   56669398, defaultctorcnt= 0, argctorcnt=  27611745, copyctorcnt=         0, assigncnt= 0, movecnt=         0, total= 339280009 in   4794 ms</p>
  
  <p>I am using gcc version 5.2.0 (GCC) in Cygwin on Windows 7.</p>