Gareth McCaughan

# McIlroy's quicksort adversary, against a randomized quicksort

import math,random,sys
sys.setrecursionlimit(100000) # so bad qsort doesn't die

# A simple randomized quicksort.
# comparator takes array and two indices (the C version takes two pointers);
# it returns <0, ==0, >0 if p<q, p==q, p>q.
def qsort(a, i,j, comparator):
  # easy cases:
  if j<=i: return
  if j<=i+1:
    if comparator(a,i,j)>0:
      a[i],a[j] = a[j],a[i]
    return
  # choose a pivot at random
  k = random.randint(i,j)
  # partition
  a[k],a[j] = a[j],a[k] # pivot to end
  left=i
  for l in range(i,j):
    if comparator(a,l,j)<=0:
      a[left],a[l] = a[l],a[left]
      left += 1
  a[left],a[j] = a[j],a[left]
  qsort(a,i,left-1,comparator)
  qsort(a,left+1,j,comparator)

def good_tester(n):
  a = [random.random() for i in range(n)]
  comparisons = [0] # list hack to work around crappy scoping rules
  def _(a,i,j):
    comparisons[0] += 1
    return a[i]-a[j]
  qsort(a,0,n-1,_)
  return comparisons[0]

def evil_tester(n):
  gas = n-1
  # nsolid,candidate,comparisons are arrays to work around crappy scoping rules
  nsolid = [0]
  candidate = [0]
  comparisons = [0]
  a = [gas for i in range(n)]
  def freeze(a,i):
    a[i] = nsolid[0]
    nsolid[0] += 1
  def _(a,i,j):
    comparisons[0] += 1
    if a[i]==gas and a[j]==gas:
      if i==candidate[0]: freeze(a,i)
      else: freeze(a,j)
    if a[i]==gas: candidate[0]=i
    else: candidate[0]=j
    return a[i]-a[j]
  qsort(a,0,n-1,_)
  return comparisons[0]

print "good:"
for n in (10,100,1000,10000):
  m = good_tester(n)
  print n, m, m/(n*math.log(n))

print "evil:"
for n in (10,100,1000):
  m = evil_tester(n)
  print n, m, m/(n**2.)