fork download
copy 
  1. def score(a)
  2. 	return a.map.with_index{|x,i| (x-i).abs}.inject(&:+)
  3. end
  4.  
  5. def qsort(a, cmp)
  6. 	return a if a.size <= 1
  7.  
  8. 	pivot, lt, gt = a[0], [], []
  9. 	a[1..-1].each{|x| (cmp[x,pivot] ? lt : gt) << x}
  10. 	return qsort(lt, cmp) + [pivot] + qsort(gt, cmp)
  11. end
  12.  
  13. def msort(a, cmp)
  14. 	return a if a.size <= 1
  15.  
  16. 	a1 = msort(a[0...a.size/2], cmp)
  17. 	a2 = msort(a[a.size/2..-1], cmp)
  18. 	aa = []
  19. 	aa << (cmp[a1[0],a2[0]] ? a1 : a2).shift while a1.size>0 && a2.size>0
  20. 	return aa + a1 + a2
  21. end
  22.  
  23. def bsort1(a, cmp)
  24. 	a = a.dup
  25. 	for s in 0...a.size
  26. 		for i in 0...a.size-s-1
  27. 			a[i], a[i+1] = a[i+1], a[i] unless cmp[a[i], a[i+1]]
  28. 		end
  29. 	end
  30. 	return a
  31. end
  32.  
  33. def bsort2(a, cmp)
  34. 	a = a.dup
  35. 	for s in 0...a.size
  36. 		for i in 0...a.size-1
  37. 			a[i], a[i+1] = a[i+1], a[i] unless cmp[a[i], a[i+1]]
  38. 		end
  39. 	end
  40. 	return a
  41. end
  42.  
  43. def ssort(a, cmp)
  44. 	a = a.dup
  45. 	h = 1
  46. 	h = 3*h+1 while (3*h+1)*2 < a.size
  47.  
  48. 	while h>0
  49. 		for i in h...a.size
  50. 			k = i-h
  51. 			while k>=0
  52. 				a[k], a[k+h] = a[k+h], a[k] unless cmp[a[k], a[k+h]]
  53. 				k -= h
  54. 			end
  55. 		end
  56. 		h = (h-1)/3
  57. 	end
  58. 	return a
  59. end
  60.  
  61. N   = 100
  62. qs  = 0.0
  63. ms  = 0.0
  64. bs1 = 0.0
  65. bs2 = 0.0
  66. ss  = 0.0
  67. cmp = lambda{|x,y| rand(10)==0 ? rand(2)==0 : x<y}
  68. N.times do
  69. 	a = [*0...52].shuffle
  70. 	qs += score(qsort(a, cmp))
  71. 	ms += score(msort(a, cmp))
  72. 	bs1 += score(bsort1(a, cmp))
  73. 	bs2 += score(bsort2(a, cmp))
  74. 	ss += score(ssort(a, cmp))
  75. end
  76. puts "q #{qs/N}"
  77. puts "m #{ms/N}"
  78. puts "b1 #{bs1/N}"
  79. puts "b2 #{bs2/N}"
  80. puts "s #{ss/N}"
  81. # your code goes here
Success #stdin #stdout 0.74s 7432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
q 174.9
m 174.34
b1 117.78
b2 5.2
s 7.24
https://ideone.com/DLdlOG
language:
Ruby (ruby 2.5.5)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!