sort_algorithms_benchmark_ips.cr

require "benchmark"

################################  Crystal scripts

def  chrono(text)
 s=Time.now
 yield
 e=Time.now
 d=(e.to_f-s.to_f)*1000
 if d>1
   puts "#{text} : #{d} ms"
 else
   puts "#{text} : #{d*1000} micro s"
 end
end

class  Array
 def *(c0: Int)
   l=self.clone
   return l if c0<=0
   c=c0-1
   while c>0
    if l.size>self.size && c>=(l.size/self.size)
       c=c-(l.size/self.size)
       l = l + l.clone
    else
       l = l  +  self.clone
       c-=1
    end
   end
   l
 end
end


##################### insertion sort

def isort(a)
  1.upto(a.length - 1) do |i|
    value = a[i]
    j = i - 1
    while j >= 0 &&  a[j] > value
      a[j+1] = a[j]
      j -= 1
    end
    a[j+1] = value
  end
  a
end

########################### quick sort

def qsort(a)
  return [0].clear unless a
  return isort(a)  if a.size<12
  pivot=a[a.size/2]
  h=a.group_by {|e| e<pivot ? 1 : 2 }
  return qsort(h[1]) + qsort(h[2]) if h.size==2
  ([a.size/10,10].max).times {
    pivot=h.values.first[rand(h.values.first.size/2)]
    h=a.group_by {|e| e<pivot ? 1 : 2 }
    #puts "."
    return qsort(h[1]) + qsort(h[2]) if h.size==2
    #p [pivot,h]
  }
  # puts "alert: qsort #{a.size}"
  isort(a)
end

##############################  Count sort

def csort(a,min=-1,max=-1)
  min,max=a.minmax unless min>=0
  if (max-min)<1000_002 && a.size<(max-min)*10
    s=Array.new((max-min+1),0)
    a.each {|e| s[e-min]+=1  }
    res=[0].clear
    s.each_with_index {|e,i| e.times  { res << (min+i)} }
    res
  else
    qsort(a) # data too big, csort can't e done
  end
end

############################# quick sort terminated by count  sort

def qcsort(a,min=-1,max=-1)
  return [0].clear unless a
  return isort(a)  if a.size<8
  min,max=a.minmax unless min>=0

  return csort(a,min,max)  if (max-min)<10_000 && (max-min)<(a.size*10)

  pivot=a[a.size/2]
  h=a.group_by {|e| e<pivot ? 1 : 2 }
  return qcsort(h[1],min,h[1].max) + qcsort(h[2],pivot,max) if h.size==2
  ([a.size/10,10].max).times {
    pivot=h.values.first[rand(h.values.first.size/2)]
    h=a.group_by {|e| e<pivot ? 1 : 2 }
    #puts "."
    return qcsort(h[1],min,h[1].max) + qcsort(h[2],pivot,max) if h.size==2
    #p [pivot,h]
  }
  # puts "alert: qsort #{a.size}"
  isort(a)
end

########################### double pivot sort

def dsort(a)
  return [0].clear unless a
  return a if a.size==0
  return isort(a) if a.size<24
  (0..3).to_a.each do |i|
    p1,p2=a[a.size/3-i],a[a.size-a.size/3+i]
    p1,p2=p2,p1 if p1>p2
    next if p1==p2
    h1=[0].clear
    h2=[0].clear
    h3=[0].clear
    a.each {|e|
      if e<p1
        h1 << e
      elsif e>=p1 && e<p2
        h2 << e
      else
       h3 << e
     end }
    return dsort(h1)+dsort(h2)+dsort(h3)
  end
  qsort(a)
end

######################### doubls pivot sort terminated by count sort

def dcsort(a,min=-1,max=-1)
  return [0].clear unless a
  return isort(a)  if a.size<24

  min,max=a.minmax unless min>=0
  return csort(a,min,max)  if (max-min)<10_000 && (max-min)<(a.size*10)
  (0..3).to_a.each do |i|
    p1,p2=a[a.size/3-i],a[a.size-a.size/3+i]
    p1,p2=p2,p1 if p1>p2
    next if p1==p2
    h1=[0].clear
    h2=[0].clear
    h3=[0].clear
    a.each {|e|
      if e<p1
        h1 << e
      elsif e>=p1 && e<p2
        h2 << e
      else
       h3 << e
     end }
    return dcsort(h1,min,h1.size>0 ? h1.max : min)+dcsort(h2,p1,p2)+dcsort(h3,p2,max)
  end
  qcsort(a)
end

##################################################################
#       T e s t          a n d         m e a s u r e s
##################################################################

[
(1..1000).map {|a| a/4 },
(1..10000).to_a.reverse,
(1..10000).to_a.shuffle,
[2]*100,
(0..20_000).map {|a| a*a} + (0..20_000).map {|a| a*a} ,
(1000..10000).to_a+(1..1000-1).to_a.shuffle,
(1000..100000).to_a+(1..1000-1).to_a.shuffle,
(0..20_000).map {|a| a*a}.shuffle ,
(0..1000_000).to_a.shuffle,
(0..3_000_000).to_a.shuffle,
].each {|a|
  ref = a.dup.sort

  puts "===== %s.. len=%d" % [a.first(10).join(", "),a.size]
  Benchmark.ips do |x|
    x.report("native") { p "error" unless a.dup.sort()==ref }
    x.report(" qsort") { p "error" unless qsort(a.dup)==ref }
    x.report(" dsort") { p "error" unless dsort(a.dup)==ref }
    x.report("qcsort") { p "error" unless qcsort(a.dup)==ref }
    x.report("dcsort") { p "error" unless dcsort(a.dup)==ref }
    x.report(" csort") { p "error" unless csort(a.dup)==ref }
  end
}

Results:

===== 0, 0, 0, 1, 1, 1, 1, 2, 2, 2.. len=1000
native 60114.21 (± 2465.03)  1.39× slower
 qsort  5182.48 (± 591.72) 16.09× slower
 dsort 13341.90 (± 1783.75)  6.25× slower
qcsort 83001.53 (± 5707.59)  1.00× slower
dcsort 83392.81 (± 5948.83)       fastest
 csort 81141.58 (± 7391.31)  1.03× slower
===== 10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991.. len=10000
native  6473.64 (± 432.01)  1.59× slower
 qsort   479.93 (± 13.28) 21.39× slower
 dsort  1082.62 (± 43.33)  9.48× slower
qcsort 10241.06 (± 488.80)  1.00× slower
dcsort 10212.33 (± 663.74)  1.01× slower
 csort 10267.70 (± 747.88)       fastest
===== 3209, 1034, 4344, 679, 4588, 3630, 8263, 7134, 5982, 6416.. len=10000
native  1715.76 (± 157.86)  5.99× slower
 qsort   237.44 (± 40.06) 43.26× slower
 dsort   599.06 (± 59.82) 17.14× slower
qcsort 10204.41 (± 248.85)  1.01× slower
dcsort 10270.43 (± 323.03)       fastest
 csort 10212.15 (± 315.84)  1.01× slower
===== 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.. len=100
native 904481.47 (± 31080.51)       fastest
 qsort 46848.74 (± 1735.97) 19.31× slower
 dsort 46476.94 (± 1698.45) 19.46× slower
qcsort 45256.33 (± 3643.11) 19.99× slower
dcsort 45766.68 (± 2333.19) 19.76× slower
 csort 45102.22 (± 3592.54) 20.05× slower
===== 0, 1, 4, 9, 16, 25, 36, 49, 64, 81.. len=40002
native     4.48 (±  0.08) 68.24× slower
 qsort    40.02 (±  1.21)  7.63× slower
 dsort   305.48 (±  7.29)       fastest
qcsort    31.01 (±  2.41)  9.85× slower
dcsort   276.70 (± 17.16)  1.10× slower
 csort    37.24 (±  2.39)  8.20× slower
===== 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009.. len=10000
native  4374.83 (± 203.50)  2.38× slower
 qsort   365.90 (± 11.50) 28.40× slower
 dsort  1102.64 (± 34.65)  9.43× slower
qcsort 10392.97 (± 387.17)       fastest
dcsort  9942.67 (± 694.88)  1.05× slower
 csort 10210.61 (± 295.88)  1.02× slower
===== 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009.. len=100000
native   486.86 (± 30.79)  2.17× slower
 qsort    37.14 (±  1.43) 28.49× slower
 dsort   104.22 (±  5.38) 10.15× slower
qcsort   148.22 (± 11.06)  7.14× slower
dcsort   309.66 (± 29.51)  3.42× slower
 csort  1058.31 (± 19.40)       fastest
===== 142730809, 293642496, 130507776, 103002201, 100200100, 93993025, 277155904, 91204, 148669249, 305131024.. len=20001
native   823.03 (± 34.63)       fastest
 qsort   115.09 (±  6.42)  7.15× slower
 dsort   300.42 (± 20.90)  2.74× slower
qcsort   103.53 (±  9.36)  7.95× slower
dcsort   299.17 (± 13.43)  2.75× slower
 csort   125.49 (±  2.55)  6.56× slower
===== 767189, 354820, 800006, 412318, 892588, 64994, 501415, 236361, 488053, 472002.. len=1000001
native    12.62 (±  0.75)  5.62× slower
 qsort     1.84 (±  0.05) 38.47× slower
 dsort     4.95 (±  0.23) 14.34× slower
qcsort     7.00 (±  0.21) 10.14× slower
dcsort    14.92 (±  0.84)  4.75× slower
 csort    70.94 (±  8.12)       fastest
===== 1174783, 427140, 233955, 1603027, 2075644, 290602, 2980841, 1391258, 1855716, 927563.. len=3000001
native     4.29 (±  0.06)       fastest
 qsort     0.62 (±  0.03)  6.94× slower
 dsort     1.55 (±  0.07)  2.76× slower
qcsort     2.04 (±  0.02)  2.10× slower
dcsort     4.17 (±  0.05)  1.03× slower
 csort     0.60 (±  0.01)  7.20× slower