sort.rb

# Implemented bubble sort & radix sort
# Included benchmarking module & benchmarked both methods
# Included manual benchmarking for radix_sort

# Sort the array from lowest to highest
def bubble_sort(arr)
  return arr if arr.size <= 1 # already sorted
  swapped = true
  while swapped do
    swapped = false
    0.upto(arr.size-2) do |i|
      if arr[i] > arr[i+1]
        arr[i], arr[i+1] = arr[i+1], arr[i] # swap values
        swapped = true
      end
    end
  end
  arr
end

test = [8,2,23,1,45,21,2,23]
puts "Sorted array (bubble_sort) is: #{bubble_sort(test)}\n\n"

# Benchmarking bubble_sort (1000 iterations)
require 'benchmark'
bubble_sort_timing = Benchmark.measure {1000.times {bubble_sort(test)}}
traditional_sort_timing = Benchmark.measure {1000.times {test.sort}}
puts "Result of benchmarking bubble_sort:\t#{Benchmark.measure {1000.times {bubble_sort(test)}}}"
puts "Result of benchmarking the sort method:\t#{Benchmark.measure {1000.times {test.sort}}}\n"

# Alternative sorting method: Radix Sort
def radix_sort(array)
  temp = []
  sorted_array = []

  array.each do |x|
    # for each element in array, we build a new array temp[] and place the element's count at temp[element]
    # all other elements in array are nil
    if temp[x] == nil
      temp[x] = 1
    else
      temp[x] = temp[x] + 1
    end
  end

  temp.each_with_index do |x, i|
    # for each element in the temp array, we push the index (element in the original array) for count times in a new array
    if (x)
      x.times do
        sorted_array << i
        # sorted_array.to_a
      end
    end
  end
  sorted_array
end

puts "Sorted array (radix_sort) is: #{radix_sort(test)}\n\n"

# Benchmarking radix_sort (1000 iterations)
radix_sort_timing = Benchmark.measure {1000.times {bubble_sort(test)}}
puts "Result of benchmarking bubble_sort:\t#{Benchmark.measure {1000.times {radix_sort(test)}}}"
puts "Result of benchmarking the sort method:\t#{Benchmark.measure {1000.times {test.sort}}}\n"

# Manual benchmarking radix_sort
beginning = Time.now
1000.times {radix_sort(test)}
ending = Time.now
puts "Result of manual benchmarking radix_sort: #{ending - beginning}\n\n"

# Find the maximum
def maximum(arr)
  bubble_sort(arr).last
end

def minimum(arr)
  bubble_sort(arr).first
end

# expect it to return 42 below
result = maximum([2, 42, 22, 02])
puts "max of 2, 42, 22, 02 is: #{result}"

# expect it to return 2 below
result = minimum([2, 42, 22, 02])
puts "min of 2, 42, 22, 02 is: #{result}"

# expect it to return nil when empty array is passed in
result = maximum([])
puts "max on empty set is: #{result.inspect}"
result = minimum([])
puts "min on empty set is: #{result.inspect}"

result = maximum([-23, 0, -3])
puts "max of -23, 0, -3 is: #{result}"

result = maximum([6])
puts "max of just 6 is: #{result}"