algorithm - 计算排序统计数据的交换 - 只有两个分配而不是三个分配的交换

Question

在帮助一名学生上课时，我实现了双枢轴快速排序算法来准备类(class)并对此产生了兴趣。运行一些统计，然后解决最坏的情况，然后再次运行统计，再次解决下一个最坏的情况，重复这个过程几次，得到的代码不超过 80 行简单直接的 Python 代码(有点少于弗拉基米尔的代码)。新颖的部分是如何结合一些非常简单但有效的后处理来构建 3 个分区。现在我需要一些关于如何正确测试和统计数据的帮助。

特别是关于如何计算交换:大多数交换只执行两个赋值而不是三个。那么我必须将它们算作完全掉期，还是仅将它们算作“2/3”掉期是否公平？

将每次交换计算为1，Cn * N * log2(N) 中的Cn 约为0.48 在短列表(<100 个元素)上，在 数百万 元素的较长列表上大约 0.55。这只是 Vladimir Yaroslavskiy 计算出的理论最小值。

相反，将较轻的交换计算为 2/3，对于任何列表大小，所需交换的数量几乎相等，并且大约为 0.36(stdev 大约为 0.015 )。

对于 200 万 记录的列表，比较次数的 Cn 平均在 1.3 左右，低于理论值 1.38 (从 2*N*ln(N) 开始)，对于较短的列表，即 1024 个元素，它在 1.21

左右

这是针对具有 100% 唯一编号 和使用 Python 的 random.shuffle() 进行随机排序 的列表。

---

所以我的问题是:

这样计算较轻的掉期是否可以，结果是否确实有希望？

---

同样有趣的是:

• 列表中的元素越多，排序越快。 Cn 是 0.03 和 0.1 分别用于所有 相等元素的 200 万 列表的交换和比较.
• Cn sorted 和 reversed sorted lists 对于所有大小几乎相同:0.3 和 1 分别用于交换(用 2/3 计算)和比较。

我将很快发布一个包含更多统计信息的列表，其中包括最大堆栈深度、除交换和比较之外的递归调用次数。还有其他我应该算的东西吗？

此外，是否有一些“标准”测试套件包含各种情况(等号、部分排序等)的文件，可用于测试排序算法，并使结果与其他排序算法具有可比性。

---

---

5 月 5 日添加:我改进了算法，特别是对于排序列表。以下是每个运行 20 次的结果。这是好结果吗？

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

Answer 1

我选择计算对要排序的元素执行的分配，而不是“交换”。索引的赋值和比较不计算在内。

我将 Vladimir Yaroslavskiy 的文档(最后更新时间:2009 年 9 月 22 日)中包含的代码转换为 Python，并按照我在自己的实现中所做的相同方式添加了计数器。代码包含在最后。

欢迎任何评论。

这是结果，10 次运行的平均值。

标有VY的列是Vladimir实现的结果，标有JB的列是我自己实现的。

 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

这是 Python 中 Vladimirs 排序的代码:

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)

这段代码大约有 190 行，我目前使用相同格式编写的实现大约有 110 行。

所以欢迎任何评论。