README.md

Create a directory in your /vagrant folder (while ssh'd into your Vagrant VM). Within that directory, clone your fork of this repo, which contains one ruby file sort.rb.

Spend the time necessary to read and fully understand what the code in sort.rb is doing. Google or discuss as necessary. Have an expectation of what will be output when you first run the code, then use the ruby command to run the sort.rb file from the terminal.

Task: Currently, the built-in Array#sort method is being used (line 3) to implement the logic for the sort method. As an exercise, instead of leveraging this built-in method, implement your own sort logic such that the resulting output from this ruby script stays the same. See http://en.wikipedia.org/wiki/Sorting_algorithm for different sorting algorithms. At a minimum implement Bubble Sort and Merge Sort.

As an extension, benchmark the different implementations versus the built in array.sort. Read about Ruby's benchmark here

sort.rb

# Sort the array from lowest to highest
def sort(arr)
  arr.sort
end

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

def minimum(arr)
  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}"


require 'benchmark'

def bubble1(arr)
  n = arr.length
  loop do
    swapped = false
    (1...n).each do |i|
      if arr[i-1] > arr[i] then
          arr[i] , arr[i-1] = arr[i-1] , arr[i]
        swapped = true
      end
    end  
    break if swapped == false
  end
  arr
end

def bubble2(arr)
  n = arr.length
  loop do
    newn = 0
    (1...n).each do |i|
      if arr[i-1] > arr[i] 
        arr[i] , arr[i-1] = arr[i-1] , arr[i]
        newn = i
      end
    end
    n = newn
    break if n == 0
  end
  arr
end






def merge_sort(arr)

  return arr if arr.length <= 1

  middle = (arr.length/2).floor

  left = arr[0..middle-1]
  right = arr[middle..arr.length-1]


  return merge(merge_sort(left),merge_sort(right))

end

def merge(left,right)

result = []

  loop do
    break if left.empty? && right.empty?

    if !left.empty? && !right.empty?
      if left[0] <= right[0]
        result.push(left[0])
        left = rest(left)
      else
        result.push(right[0])
        right = rest(right)
      end
    elsif !left.empty?
      result.push(left[0])
      left = rest(left)
    elsif !right.empty?
      result.push(right[0])
      right = rest(right)
    end

  end
  return result
end


def rest(arr)
  arr.pop(arr.length-1)
end




$debug = false
puts merge_sort([2,4,5,1,2]).inspect

class Array
  def bbl1
    bubble1(self)
  end
  def bbl2
    bubble2(self)
  end
  def mrg 
    merge_sort(self)
  end
end

randarray = (1..1000).map{|x| x*rand}

Benchmark.bm do |x|
  x.report  ("#sort")  {  randarray.sort  }
  x.report("bubble1")  {  randarray.bbl1  }
  x.report("bubble2")  {  randarray.bbl2  }
  x.report  ("merge")  {  randarray.mrg   }
end