compare sorting algo

rubysort.rb

require_relative 'utils' # define : chrono(comment) { code de measure }

###################### bubble sort

def bsort(a)
  0.upto(a.size-1) { |i|
    i.upto(a.size-1) {|j| a[i],a[j]=a[j],a[i] if a[j]<a[i] }
  }
  a
end

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

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

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

def qsort(a)
  return [] 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

############################## naive sort

def tsort(a,min=nil,max=nil)
  min,max=a.minmax unless min
  if (max-min)<1000_002 && a.size<(max-min)*10
    s=[nil]*(max-min)
    a.each {|e| t=s[e-min] ; t==nil ? s[e-min]=e : Array===t ? t << e : s[e-min]=[t,e]}
    s.each_with_object([]) {|e,res| 
      if e 
        if Array===e then e.each {|ee|res << ee}  else res << e end
      end
    }
  else
    qsort(a)
  end
end

############################# quick sort terminated by naive sort

def qtsort(a,min=nil,max=nil)
  return [] unless a
  return isort(a)  if a.size<8
  min,max=a.minmax unless min
 
  return tsort(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 qtsort(h[1],min,h[1].max) + qtsort(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 qtsort(h[1],min,h[1].max) + qtsort(h[2],pivot,max) if h.size==2
    #p [pivot,h]
  }
  puts "alert: qsort #{a.size}"
  isort(a)
end

########################### double pivbot sort 

def dsort(a)
  return [] unless a
  return isort(a) if a.size<24
  (0..a.size/3).to_a.each do |i|
    p1,p2=a[a.size/3-i],a[(a.size*2)/3+i]
    p1,p2=p2,p1 if p1>p2
    h=a.group_by {|e| e<p1 ? 1 : (e>=p1 && e<=p2) ? 2 : e>p2 ? 3 : 0}
    return dsort(h[1])+dsort(h[2])+dsort(h[3]) if h.size==3
  end
  qsort(a)
end

######################### doubl pivot terminated by naive sort

def dtsort(a,min=nil,max=nil)
  return [] unless a
  return isort(a)  if a.size<12

  min,max=a.minmax unless min
  return tsort(a,min,max)  if (max-min)<10_000 && (max-min)<(a.size*10)
  (0..a.size/3-1).to_a.each do |i|
    p1,p2=a[a.size/3-i],a[(a.size*2)/3+i]
    p1,p2=p2,p1 if p1>p2
    h=a.group_by {|e| e<p1 ? 1 : (e>=p1 && e<=p2) ? 2 : e>p2 ? 3 : 0}
    return dtsort(h[1],min,h[1].max)+dtsort(h[2],p1,p2)+dtsort(h[3],h[3].min,max) if h.size==3
  end
  qsort(a)
end

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

[
(1..100).to_a,
(1..1000).map {|a| a/4 },
(1..10000).to_a.reverse,
(1..10000).to_a.shuffle,
(0..20_000).map {|a| a*a} * 2,
(1000..10000).to_a+(1..1000-1).to_a.shuffle,
(1000..100000).to_a+(1..1000-1).to_a.shuffle,
(0..1000_000).to_a.shuffle,
(0..20_000).map {|a| a*a}.shuffle ,
].each {|a|
  puts "===== %s.. len=%d" % [a.first(10).join(", "),a.size]
  ref=a.sort
  chrono("ruby  ") { a.sort }
  chrono("qsort ") { p "error" unless qsort(a)==ref }
  chrono("dsort ") { p "error" unless dsort(a)==ref }
  chrono("qtsort") { p "error" unless qtsort(a)==ref }
  chrono("dtsort ") { p "error" unless dtsort(a)==ref }
  chrono("tsort ") { p "error" unless tsort(a)==ref }
}

===== 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.. len=100
ruby Duration: 0.0 micro s.
qsort Duration: 0.0 micro s.
dsort Duration: 0.0 micro s.
qtsort Duration: 0.0 micro s.
dtsort Duration: 0.0 micro s.
tsort Duration: 0.0 micro s.
===== 0, 0, 0, 1, 1, 1, 1, 2, 2, 2.. len=1000
ruby Duration: 0.0 micro s.
qsort Duration: 999.9275207519531 micro s.
dsort Duration: 1.9998550415039062 ms
qtsort Duration: 0.0 micro s.
dtsort Duration: 1.0001659393310547 ms
tsort Duration: 0.0 micro s.
===== 10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991.. len=10000
ruby Duration: 999.9275207519531 micro s.
qsort Duration: 25.001049041748047 ms
dsort Duration: 24.0020751953125 ms
qtsort Duration: 4.999876022338867 ms
dtsort Duration: 4.999876022338867 ms
tsort Duration: 5.001068115234375 ms
===== 1697, 8428, 187, 7790, 9708, 7714, 1613, 7734, 5582, 6404.. len=10000
ruby Duration: 1.9998550415039062 ms
qsort Duration: 39.002180099487305 ms
dsort Duration: 26.001930236816406 ms
qtsort Duration: 4.999876022338867 ms
dtsort Duration: 5.000114440917969 ms
tsort Duration: 3.999948501586914 ms
===== 0, 1, 4, 9, 16, 25, 36, 49, 64, 81.. len=40002
ruby Duration: 6.000041961669922 ms
qsort Duration: 274.0161418914795 ms
dsort Duration: 88.00482749938965 ms
qtsort Duration: 332.0188522338867 ms
dtsort Duration: 117.00606346130371 ms
tsort Duration: 278.0160903930664 ms
===== 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009.. len=10000
ruby Duration: 1.0008811950683594 ms
qsort Duration: 24.001121520996094 ms
dsort Duration: 16.000986099243164 ms
qtsort Duration: 4.999876022338867 ms
dtsort Duration: 5.000114440917969 ms
tsort Duration: 4.00090217590332 ms
===== 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009.. len=100000
ruby Duration: 16.000986099243164 ms
qsort Duration: 274.0159034729004 ms
dsort Duration: 197.01099395751953 ms
qtsort Duration: 133.00681114196777 ms
dtsort Duration: 125.00810623168945 ms
tsort Duration: 47.00183868408203 ms
===== 962087, 680532, 759023, 528375, 305961, 307643, 740923, 266607, 617584, 299870.. len=1000001
ruby Duration: 238.01302909851074 ms
qsort Duration: 5.993342876434326 sec
dsort Duration: 4.446254253387451 sec
qtsort Duration: 2815.1607513427734 ms
dtsort Duration: 2467.1409130096436 ms
tsort Duration: 574.0327835083008 ms
===== 7595536, 24206400, 3222025, 331531264, 28026436, 372104100, 751689, 183954969, 16670889, 360050625.. len=20001
ruby Duration: 3.999948501586914 ms
qsort Duration: 76.0040283203125 ms
dsort Duration: 74.00393486022949 ms
qtsort Duration: 105.00621795654297 ms
dtsort Duration: 91.00604057312012 ms
tsort Duration: 76.0040283203125 ms