require 'benchmark'

def bubblesort( list )
 mylist = list.dup
 return mylist if mylist.size <= 1 # already sorted

 swapped = true
 while swapped
   swapped = false # maybe this time, we won't find a swap
   0.upto( mylist.size - 2 ) do |i|
     if mylist[i] > mylist[i + 1]
       mylist[i], mylist[i + 1] = mylist[i + 1], mylist[i] # swap values
       swapped = true # found a swap... keep going
     end
   end
 end

 mylist
end

def selectionsort( list )
 mylist = list.dup
 
 mylist.each_index do |x|
   index_of_min = x
   x.upto( mylist.size - 1 ) do |y|
     if mylist[index_of_min] > mylist[y]
       index_of_min = y
     end
   end
   
   mylist[x], mylist[index_of_min] = mylist[index_of_min], mylist[x]
 end
 
 mylist
end


numbers = []

5000.times { numbers.push Random.rand(0..100) }

puts "Testing bubble sort over 10 sorts with 5000 numbers"


time = Benchmark.realtime do
  10.times { new_numbers = bubblesort numbers }
end
average_bubblesort = time

puts "Testing selection sort over 10 sorts with 5000 numbers"

time = Benchmark.realtime do
 10.times { new_numbers = selectionsort numbers }
end
average_selectionsort = time


puts "Bubble sort average time over 10 sorts:    #{average_bubblesort / 10} seconds per sort"
puts "Selection sort average time over 10 sorts: #{average_selectionsort / 10} seconds per sort"

output

Testing bubble sort over 10 sorts with 5000 numbers
Testing selection sort over 10 sorts with 5000 numbers
Bubble sort average time over 10 sorts:    5.2923027 seconds per sort
Selection sort average time over 10 sorts: 1.5013859 seconds per sort

output

0.0004 seconds per sort (ruby sort)
0.1478085 seconds per sort (ruby implantation of quicksort)

def quicksort(list, p, r)
 mylist = list.dup
   if p < r then
       q = partition(mylist, p, r)
       quicksort(mylist, p, q-1)
       quicksort(mylist, q+1, r)
   end
   
   mylist
end

def partition(list, p, r)
   pivot = list[r]
   i = p - 1
   p.upto(r-1) do |j|
       if list[j] <= pivot
           i = i+1
           list[i], list[j] = list[j],list[i]
       end        
   end
   list[i+1],list[r] = list[r],list[i+1]
   return i + 1
end

numbers = []

5000.times { numbers.push Random.rand(0..100) }

time = Benchmark.realtime do
 10.times { new_numbers = numbers.sort }
end

puts "#{time / 10} seconds per sort (ruby sort)"

time = Benchmark.realtime do
 10.times { new_numbers = quicksort numbers, 0, numbers.size-1 }
end

puts "#{time / 10} seconds per sort (ruby implantation of quicksort)"

import random
randomlist= [random.randint(1,100) for _ in range(9000)]
totals=[0]*101
sortedoutput=[]
for number in randomlist:
   totals[number]+=1
for i, entry in enumerate(totals):
   for j in range(entry):
       sortedoutput.append(i)

 def radix_sort(base=10)
   ary = dup
   rounds = (Math.log(self.max.abs)/Math.log(base)).ceil
   rounds.times do |i|
     buckets = Hash.new {|h,k| h[k] = []}
     ary.each do |n|
       digit = (n/base**i) % base
       digit = digit + base unless n<0
       buckets[digit] << n
     end
     ary = buckets.values_at(*(0..2*base)).compact.flatten
     p [i, ary] if $DEBUG
   end
   ary
 end

def customsort(array)
 temp = Array.new
 mylist = []
 array.each do |x|
   if temp[x] == nil
     temp[x] = 1
   else
     temp[x] = temp[x] + 1
   end
 end
 temp.each_with_index do |x, i|
   if (x)
     x.times do
       mylist.push i
     end
   end
 end
 mylist
end

numbers = []

5000.times { numbers.push Random.rand(0..100) }

time = Benchmark.realtime do
 10.times { new_numbers = customsort numbers }
end

puts "#{time / 10} seconds per sort (radix sort)"