bench_quicksort.rb

# Simple quicksort benchmark, once for a small array and once for a very large array
require 'benchmark'

$small_array = [4477, 4347, 3978, 4030, 3991, 1544, 2339, 2258, 1198, 1636, 1272, 1450, 117, 4734, 2319, 727, 3228, 4628, 817, 3997, 2943, 2635, 519, 3588, 870, 1389, 4176, 1595, 798, 3036, 589, 3052, 2603, 4898, 2386, 202, 4304, 4771, 1681, 3520, 941, 3618, 4284, 2083, 3156, 4001, 4894, 4727, 4576, 1244, 1358, 4104, 3322, 4748, 2353, 4759, 1113, 521, 3980, 884, 149, 4033, 2723, 426, 2585, 2893, 4177, 1366, 3634, 3579, 3884, 3737, 152, 422, 204, 4421, 4201, 1513, 2408, 612, 1564, 2499, 2924, 2764, 720, 443, 3547, 1927, 3930, 549, 4245, 191, 93, 2493, 2062, 1191, 3753, 784, 4203, 1756, 4890, 2819, 4225, 4546, 4556, 4091, 1372, 411, 4592, 907, 2129, 4658, 94, 4467, 1528, 4574, 4535, 4325, 3057, 4962, 2989, 3468, 130, 4241, 3881, 1509, 18, 4231, 681, 3896, 1733, 4218, 4596, 4687, 3069, 663, 2051, 4276, 3449, 2833, 1070, 2426, 308, 3077, 4136, 1138, 3189, 1441, 4689, 46, 167, 4850, 4870, 2593, 4044, 1981, 4806, 3029, 4883, 2893, 1323, 4623, 4098, 2803, 1515, 373, 3754, 4852, 3851, 2863, 1422, 4380, 903, 4491, 4231, 4704, 4432, 994, 1560, 185, 2082, 4337, 3000, 1749, 3513, 3306, 1577, 1223, 3896, 288, 844, 1726, 3269, 4282, 703, 4604, 4188, 854, 4549, 325, 2631, 2639, 3792, 199, 2671, 2449, 1013, 1704, 3089, 937, 4371, 947, 88, 4906, 3210, 965, 4482, 3346, 1756, 4956, 250, 763, 3979, 4310, 1138, 1725, 4471, 2359, 2979, 1664, 1745, 229, 3835, 896, 1474, 4654, 1545, 2409, 4289, 1337, 3895, 1530, 3517, 3378, 4709, 350, 3687, 4518, 1814, 3413, 2282, 1302, 3953, 1209, 1914, 3065, 3847, 3380, 263, 4818, 1851, 1799, 4524, 4161, 4939, 2206, 2584, 1957, 2114, 3607, 1433, 3855, 3815, 4865, 3951, 938, 4973, 1632, 1100, 1582, 4808, 4207, 2086, 2043, 2441, 3759, 1287, 4747, 4094, 4523, 65, 3408, 4657, 3886, 2721, 3397, 2331, 3292, 4239, 4257, 2869, 318, 2711, 1054, 4379, 233, 3935, 3383, 2270, 4638, 229, 3271, 2684, 3899, 4117, 4911, 1741, 456, 1700, 2511, 2997, 3327, 1508, 4366, 1689, 1210, 3252, 573, 2632, 3024, 1178, 2653, 1479, 3250, 848, 9, 1153, 4712, 4505, 1822, 42, 4825, 2054, 4302, 4310, 2735, 3970, 1892, 1706, 3849]

$big_array = $small_array * 100

def quicksort(l)
  if l == [] then 
    []
  else
    x, *xs = l

    quicksort(xs.select { |i| i <  x }) + [x] + 
      quicksort(xs.select { |i| i >= x })
  end
end

Benchmark.bm(25) do |b| 
  5.times { b.report("350-element quicksort") { quicksort($small_array) } }
  5.times { b.report("35k-element quicksort") { quicksort($big_array) } }
end