Benchmarking de Métodos de Classificação - Estrutura de Dados

classify.rb

def bubble_sort(array)
  n = array.length
  swapped = true

  while swapped do
   swapped = false

   (n - 1).times do |i|
     if array[i] > array[i + 1]
       array[i], array[i + 1] = array[i + 1], array[i]
       swapped = true
     end
   end
  end

  array
end

def selection_sort(array)
  a = array
  n = a.size - 1

  n.times do |i|
    index_min = i

    (i + 1).upto(n) do |j|
      index_min = j if a[j] < a[index_min]
    end

    # Yep, in ruby I can do that, no aux variable. w00t!
    a[i], a[index_min] = a[index_min], a[i] if index_min != i
  end
end

def insertion_sort(num)
  for j in 1..(num.length - 1)
    key = num[j]
    i = j - 1

    while i >= 0 and num[i] > key
      num[i + 1] = num[i]
      i = i - 1
    end

    num[i + 1] = key
  end
end

array = Array.new(10000) { rand(1...10000) }

bubble_sort_shuffle = []
selection_sort_shuffle = []
insertion_sort_shuffle = []
bubble_sort_sorted = []
selection_sort_sorted = []
insertion_sort_sorted = []
bubble_sort_reverse = []
selection_sort_reverse = []
insertion_sort_reverse = []

20.times do
  ## Bubble Sort
  array.shuffle!
  time = Time.now
  bubble_sort(array)
  bubble_sort_shuffle << Time.now - time

  ## Selection Sort
  array.shuffle!
  time = Time.now
  selection_sort(array)
  selection_sort_shuffle << Time.now - time

  ## Insertion Sort
  array.shuffle!
  time = Time.now
  insertion_sort(array)
  insertion_sort_shuffle << Time.now - time

  ## Bubble Sort
  array.sort!
  time = Time.now
  bubble_sort(array)
  bubble_sort_sorted << Time.now - time

  ## Selection Sort
  array.sort!
  time = Time.now
  selection_sort(array)
  selection_sort_sorted << Time.now - time

  ## Insertion Sort
  array.sort!
  time = Time.now
  insertion_sort(array)
  insertion_sort_sorted << Time.now - time

  ## Bubble Sort
  array.sort!.reverse!
  time = Time.now
  bubble_sort(array)
  bubble_sort_reverse << Time.now - time

  ## Selection Sort
  array.sort!.reverse!
  time = Time.now
  selection_sort(array)
  selection_sort_reverse << Time.now - time

  ## Insertion Sort
  array.sort!.reverse!
  time = Time.now
  insertion_sort(array)
  insertion_sort_reverse << Time.now - time
end

def avarage(values)
  (values.map{ |x| x }.inject(:+).to_f / values.size)
end

puts 'SHUFFLE'
puts 'Bubble: ' + avarage(bubble_sort_shuffle).to_s
puts 'Selection: ' + avarage(selection_sort_shuffle).to_s
puts 'Insertion: ' + avarage(insertion_sort_shuffle).to_s
puts
puts 'SORTED'
puts 'Bubble: ' + avarage(bubble_sort_sorted).to_s
puts 'Selection: ' + avarage(selection_sort_sorted).to_s
puts 'Insertion: ' + avarage(insertion_sort_sorted).to_s
puts
puts 'REVERSE'
puts 'Bubble: ' + avarage(bubble_sort_reverse).to_s
puts 'Selection: ' + avarage(selection_sort_reverse).to_s
puts 'Insertion: ' + avarage(insertion_sort_reverse).to_s