#!/usr/bin/env ruby
# Author : Emad Elsaid (https://github.com/blazeeboy)
# 
# this script is a small practice in implementing 
# simple sorting algorithms in ruby, i converted
# the sorting algorithms from wikipedia pages

class Array
  # Insertion sort is a simple sorting algorithm that builds 
  # the final sorted array (or list) one item at a time. 
  # It is much less efficient on large lists than more advanced 
  # algorithms such as quicksort, heapsort, or merge sort.
  # **wikipedia**
  def insertion_sort!

    (1...size).each do |i|
      j = i
      while j > 0 and self[j-1] > self[j]
          self[j], self[j-1] = self[j-1], self[j]
          j = j - 1
      end
    end

  end

  # selection sort is a sorting algorithm, specifically an in-place 
  # comparison sort. It has O(n2) time complexity, making it 
  # inefficient on large lists, and generally performs worse 
  # than the similar insertion sort. Selection sort is noted for 
  # its simplicity, and it has performance advantages over more 
  # complicated algorithms in certain situations, 
  # particularly where auxiliary memory is limited.
  # **wikipedia**
  def selection_sort!
     
    (0...size).each do |j|
      # find index of minimum element in the unsorted part 
      iMin = j
      (j+1...size).each do |i|
        iMin = i if self[i] < self[iMin]
      end
      
      # then swap it
      self[j], self[iMin] = self[iMin], self[j]
    end
  end

end

# lets try our algorithms
x = (1..10).to_a.shuffle
p 'before sort : ', x
x.insertion_sort!
p 'after sort : ', x

x.shuffle!
p 'before sort : ', x
x.selection_sort!
p 'after sort : ', x