Counting swaps for sorting statistics - what with swaps with only two assignments instead of three

1
votes

While helping out a student with his classes, I implemented the dual pivot quicksort algorithm 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.

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?

Counting every swap as 1, the Cn in Cn * N * log2(N) is around 0.48 on short lists (<100 elements) and around 0.55 on longer lists of several million elements. That is just the theoretical minimum as calculated by Vladimir Yaroslavskiy.

Counting the lighter swaps as 2/3 instead, the number of needed swaps is almost equal for any list size and is around 0.36 (stdev around 0.015).

The Cn for the number of comparisons is on average around 1.3 for lists of 2 million records, which is less then the theoretical 1.38 (from 2*N*ln(N)), and lower for shorter lists, i.e. for 1024 elements, it's around 1.21

That is for lists with 100% unique numbers and randomly ordered with Python's random.shuffle().

So my question is:

Is it ok to count the lighter swaps as such, and is the result indeed promising or not?

Also interesting is:

  • the more equal elements in the list, the faster is sorts. Cn is 0.03 and 0.1 for swaps and comparisons respectively for a 2 million list of all equal elements.
  • Cn for sorted and reversed sorted lists are almost the same for all sizes: 0.3 and 1 for the swaps (counted with 2/3) and comparisons respectively.

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?

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.

Added May 5: I improved the algorithm especially for sorted lists. Here are the resutls for 20 runs for each. Are this good results?

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
1
algorithmsorting
How can we swap two numbers with two assignment? – Sayakiss
@Sayakiss When sorting, moving a record into the right place does not always need a swap with another value. Good example is when moving a list 1 position, one doesn't need to swap each element. – Jan Boonen

1 Answers

3
votes

I have chosen to count the assignments executed on the elements to be sorted, instead of 'swaps'. Assignements and comparisons of indexes are not counted.

I converted the code Vladimir Yaroslavskiy included in his document (Last updated: September 22, 2009) to Python and added the counters the same way as I did in my own implementation. The code is included at the end.

Any comments are welcome.

Here are the results, the averages of 10 runs.

The columns labeled VY are the results for the implementation by Vladimir, the columns labeled by JB are these of my own implementation.

 Length        F  Function call  Assignements   Comparisons    Maximum Stack
 of list          per N          per N.log2(N)  per N.log2(N)  per log2(N)

Random.shuffle(), unique number
Version             VY     JB      VY     JB      VY     JB      VY     JB
      64        1  0.170  0.266   1.489  1.029   1.041  1.028   0.417  0.633
     256        1  0.171  0.270   1.463  1.016   1.066  1.138   0.575  0.812
    1024        1  0.167  0.275   1.451  1.046   1.089  1.165   0.690  1.010
    4096        1  0.164  0.273   1.436  1.069   1.119  1.189   0.800  1.075
   16384        1  0.166  0.273   1.444  1.077   1.117  1.270   0.843  1.221
   65536        1  0.166  0.273   1.440  1.108   1.126  1.258   0.919  1.281
  262144        1  0.166  0.273   1.423  1.102   1.134  1.278   0.950  1.306
 1048576        1  0.166  0.273   1.426  1.085   1.131  1.273   0.990  1.290

Sorted, unique numbers
Version             VY     JB      VY     JB      VY     JB      VY     JB
      64        1  0.203  0.203   1.036  0.349   0.643  0.586   0.333  0.333
     256        1  0.156  0.156   0.904  0.262   0.643  0.609   0.375  0.375
    1024        1  0.118  0.355   0.823  0.223   0.642  0.740   0.400  0.500
    4096        1  0.131  0.267   0.840  0.181   0.679  0.732   0.500  0.500
   16384        1  0.200  0.200   0.926  0.152   0.751  0.726   0.500  0.500
   65536        1  0.150  0.150   0.866  0.131   0.737  0.722   0.500  0.500
  262144        1  0.113  0.338   0.829  0.124   0.728  0.781   0.500  0.556
 1048576        1  0.147  0.253   0.853  0.108   0.750  0.774   0.550  0.550

Reversed order, unique numbers
Version             VY     JB      VY     JB      VY     JB      VY     JB
      64        1  0.203  0.203   1.320  0.836   0.841  0.802   0.333  0.333
     256        1  0.156  0.156   1.118  0.703   0.795  0.783   0.375  0.375
    1024        1  0.118  0.312   1.002  0.631   0.768  0.852   0.400  0.500
    4096        1  0.125  0.267   0.977  0.569   0.776  0.861   0.500  0.500
   16384        1  0.200  0.200   1.046  0.516   0.834  0.852   0.500  0.500
   65536        1  0.150  0.150   0.974  0.475   0.813  0.844   0.500  0.500
  262144        1  0.113  0.338   0.925  0.459   0.795  0.896   0.500  0.556
 1048576        1  0.145  0.253   0.938  0.430   0.811  0.890   0.550  0.550

Random, with increasing frequency of the numbers.
The last row is a list of the same number
Version             VY     JB      VY     JB      VY     JB      VY     JB
   65536        1  0.166  0.273   1.429  1.051   1.113  1.251   0.881  1.156
   65536        2  0.167  0.270   1.404  1.075   1.112  1.238   0.894  1.194
   65536        4  0.168  0.273   1.373  1.039   1.096  1.213   0.906  1.238
   65536        8  0.151  0.245   1.302  1.029   1.069  1.199   0.900  1.262
   65536       16  0.132  0.127   1.264  0.970   1.020  1.150   0.912  1.188
   65536       32  0.090  0.064   1.127  0.920   0.950  1.099   0.856  1.119
   65536       64  0.051  0.032   1.000  0.845   0.879  0.993   0.819  1.019
   65536      128  0.026  0.016   0.884  0.792   0.797  0.923   0.725  0.931
   65536      256  0.013  0.008   0.805  0.704   0.728  0.840   0.675  0.856
   65536      512  0.006  0.004   0.690  0.615   0.652  0.728   0.588  0.669
   65536     1024  0.003  0.002   0.635  0.557   0.579  0.654   0.519  0.625
   65536     2048  0.002  0.001   0.541  0.487   0.509  0.582   0.438  0.463
   65536     4096  0.001  0.000   0.459  0.417   0.434  0.471   0.369  0.394
   65536     8192  0.000  0.000   0.351  0.359   0.357  0.405   0.294  0.300
   65536    16384  0.000  0.000   0.247  0.297   0.253  0.314   0.206  0.194
   65536    32768  0.000  0.000   0.231  0.188   0.209  0.212   0.125  0.081
   65536    65536  0.000  0.000   0.063  0.125   0.063  0.125   0.062  0.000

Here is the code of Vladimirs sort in Python:

DIST_SIZE = 13
TINY_SIZE = 17

def dualPivotQuicksort(a, left, right, nesting=0):
  global assignements, comparisons, oproepen, maxnesting
  oproepen += 1
  maxnesting = max(maxnesting, nesting)

  length = right - left
  if length < TINY_SIZE: # insertion sort on tiny array
    # note by JB: rewritten to minimize the assignements
    for i in xrange(left+1, right+1):
      key = a[i]
      assignements += 1

      while i > left:
        comparisons += 1
        if key < a[i - 1]:
          assignements += 1
          a[i] = a[i-1]
          i -= 1
        else:
          break

      assignements += 1
      a[i] = key

    return

  # median indexes
  sixth = length / 6
  m1 = left + sixth
  m2 = m1 + sixth
  m3 = m2 + sixth
  m4 = m3 + sixth
  m5 = m4 + sixth
  assignements += 9*3
  comparisons += 9
  ## 5-element sorting network
  if a[m1] > a[m2]: a[m1],a[m2] = a[m2],a[m1]
  if a[m4] > a[m5]: a[m4],a[m5] = a[m5],a[m4]
  if a[m1] > a[m3]: a[m1],a[m3] = a[m3],a[m1]
  if a[m2] > a[m3]: a[m2],a[m3] = a[m3],a[m2] 
  if a[m1] > a[m4]: a[m1],a[m4] = a[m4],a[m1] 
  if a[m3] > a[m4]: a[m3],a[m4] = a[m4],a[m3] 
  if a[m2] > a[m5]: a[m2],a[m5] = a[m5],a[m2] 
  if a[m2] > a[m3]: a[m2],a[m3] = a[m3],a[m2] 
  if a[m4] > a[m5]: a[m4],a[m5] = a[m5],a[m4]

  # pivots: [ < pivot1 | pivot1 <= && <= pivot2 | > pivot2 ]
  assignements += 2
  pivot1 = a[m2]
  pivot2 = a[m4]

  comparisons += 1
  diffPivots = pivot1 != pivot2

  assignements += 2
  a[m2] = a[left]
  a[m4] = a[right]

  # center part pointers
  less = left + 1
  great = right - 1

  # sorting
  if (diffPivots):
    k = less
    while k <= great:
      assignements += 1
      x = a[k]

      comparisons += 2
      if (x < pivot1):
        comparisons -= 1
        assignements += 2
        a[k] = a[less]
        a[less] = x
        less += 1

      elif (x > pivot2):
        while k < great:
          comparisons += 1
          if a[great] > pivot2:
            great -= 1
          else:
            break

        assignements += 3
        a[k] = a[great]
        a[great] = x
        great -= 1
        x = a[k]

        comparisons += 1
        if (x < pivot1):
          assignements += 2
          a[k] = a[less]
          a[less] = x
          less += 1

      k += 1

  else:
    k = less
    while k <= great:
      assignements += 1
      x = a[k]

      comparisons += 1
      if (x == pivot1):
        k += 1
        continue

      comparisons += 1
      if (x < pivot1):
        assignements += 2
        a[k] = a[less]
        a[less] = x
        less += 1

      else:
        while k < great:
          comparisons += 1
          if a[great] > pivot2:
            great -= 1
          else:
            break

        assignements += 3
        a[k] = a[great]
        a[great] = x
        great -= 1
        x = a[k]

        comparisons += 1
        if (x < pivot1):
          assignements += 2
          a[k] = a[less]
          a[less] = x
          less += 1

      k += 1

  # swap
  assignements += 2
  a[left] = a[less - 1]
  a[less - 1] = pivot1

  assignements += 2
  a[right] = a[great + 1]
  a[great + 1] = pivot2

  # left and right parts
  dualPivotQuicksort(a, left, less - 2, nesting+1)
  dualPivotQuicksort(a, great + 2, right, nesting+1)

  # equal elements
  if (great - less > length - DIST_SIZE and diffPivots):
    k = less
    while k <= great:
      assignements += 1
      x = a[k]

      comparisons += 2
      if (x == pivot1):
        comparisons -= 1
        assignements += 2
        a[k] = a[less]
        a[less] = x
        less += 1

      elif (x == pivot2):
        assignements += 3
        a[k] = a[great]
        a[great] = x
        great -= 1
        x = a[k]

        comparisons += 1
        if (x == pivot1):
          assignements += 2
          a[k] = a[less]
          a[less] = x
          less += 1

      k += 1

  # center part
  if (diffPivots):
      dualPivotQuicksort(a, less, great, nesting+1)

This code is about 190 lines, my current implementation written with the same formatting is about 110 lines.

So any remarks are welcome.