title: Counting swaps for sorting statistics - what with swaps with only two assignments instead of three
body: <p>While helping out a student with his classes, I implemented the <strong>dual pivot quicksort algorithm</strong> to prepare a session and got intriged. After running some statistics, then solving the worst case situation, then running stats again, and again solving the next worst case situation, and repeating this process several times, the resulting code is no more then 80 lines of simple straightforward Python code (a bit less then Vladimir's code). The novel part is how the 3 partitions are constructed in combination with some very simple yet effective post processing of them. Now I need some help on how to test and make statistics properly.</p>
  
  <p>Especially about how to count the swaps: most of the swaps only perform two assignements instead of three. So must I count them as full swaps or, is it fair to count them only as a '2/3' swap?</p>
  
  <p>Counting every swap as <code>1</code>, the <code>Cn</code> in <code>Cn * N * log2(N)</code> is around <code>0.48</code> on short lists (<strong>&lt;100 elements</strong>) and around <code>0.55</code> on longer lists of <strong>several million</strong> elements. That is just the <strong>theoretical minimum</strong> as calculated by <strong>Vladimir Yaroslavskiy</strong>.</p>
  
  <p>Counting the lighter swaps as <code>2/3</code> instead, the number of needed swaps is almost equal for any list size and is around <code>0.36</code> (stdev around <code>0.015</code>).</p>
  
  <p>The <code>Cn</code> for the number of comparisons is on average around <code>1.3</code> for lists of <strong>2 million</strong> records, which is less then the theoretical 1.38 (from 2*N*ln(N)), and lower for shorter lists, i.e. for <strong>1024 elements</strong>, it's around <code>1.21</code></p>
  
  <p>That is for lists with <strong>100% unique numbers</strong> and <strong>randomly ordered</strong> with Python's <code>random.shuffle()</code>. </p>
  
  <hr>
  
  <p><strong>So my question is</strong>:  </p>
  
  <p>Is it ok to count the lighter swaps as such, and is the result indeed promising or not?</p>
  
  <hr>
  
  <p>Also interesting is:</p>
  
  <ul>
  <li>the more equal elements in the list, the faster is sorts. <code>Cn</code> is <code>0.03</code> and <code>0.1</code> for swaps and comparisons respectively for a <strong>2 million</strong> list of all <strong>equal elements</strong>.</li>
  <li><code>Cn</code> for <strong>sorted</strong> and <strong>reversed sorted lists</strong> are almost the same for all sizes: <code>0.3</code> and <code>1</code> for the swaps (counted with <code>2/3</code>) and comparisons respectively.</li>
  </ul>
  
  <p>I will post a list with more statistics shortly which includes maximum stack depth, number of recursive calls besides the swaps and comparisons. Are there other things I should count?</p>
  
  <p>Also, are there some 'standard' test suites with files of all kinds of situations (with equals, partially sorted etc.) one can use to test a sorting algorithm, and to make the results comparable with other sorting algorithms.</p>
  
  <hr>
  
  <hr>
  
  <p>Added May 5:
  I improved the algorithm especially for sorted lists.
  Here are the resutls for 20 runs for each.
  Are this good results?</p>
  
  <pre><code>New statistics:
  Random.shuffle(), unique number
    Length        Swaps/Nlog2(N)      Comparisons/Nlog2(N)   Maximum Stack/log2(N)
        16        0.367               0.922                  0.250
        64        0.360               1.072                  0.500
       256        0.342               1.122                  0.625
      1024        0.358               1.156                  0.800
      4096        0.359               1.199                  0.917
     16384        0.359               1.244                  1.071
     65536        0.360               1.244                  1.125
    262144        0.360               1.269                  1.167
   1048576        0.362               1.275                  1.200
  
  Sorted, unique numbers
    Length        Swaps/Nlog2(N)      Comparisons/Nlog2(N)   Maximum Stack/log2(N)
        16        0.172               0.531                  0.250
        64        0.117               0.586                  0.333
       256        0.087               0.609                  0.375
      1024        0.075               0.740                  0.500
      4096        0.060               0.732                  0.500
     16384        0.051               0.726                  0.500
     65536        0.044               0.722                  0.500
    262144        0.041               0.781                  0.556
   1048576        0.036               0.774                  0.550
   2097152        0.035               0.780                  0.571
  
   Reversed order, unique numbers
     Length        Swaps/Nlog2(N)     Comparisons/Nlog2(N)   Maximum Stack/log2(N)
        16        0.344               0.828                  0.250
        64        0.279               0.812                  0.333
       256        0.234               0.788                  0.375
      1024        0.210               0.858                  0.500
      4096        0.190               0.865                  0.500
     16384        0.172               0.855                  0.500
     65536        0.158               0.846                  0.500
    262144        0.153               0.900                  0.556
   1048576        0.143               0.892                  0.550
   2097152        0.140               0.895                  0.571
  </code></pre>