oaktree

Insertion Sort - Ruby

Mar 11th, 2016
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #! /usr/bin/env ruby
  2. def sorted?(arr)
  3.     for i in 1...arr.length
  4.         return false if arr[i] < arr[i-1]
  5.     end
  6.  
  7.     return true
  8. end
  9. # ignore, just input
  10. puts "give me a string"
  11. str = gets.chomp.split('')
  12. strlen = str.length
  13. # stop ignoring
  14.  
  15. # PAY ATTENTION HERE
  16. # if the element to the left bigger than the element we are looking at, str[i]
  17. # we need to put str[i] where it belongs.
  18. # and we do this by temporarily storing the value of str[i] and then shifting
  19. # all the elements of the array/str that are bigger than str[i] to the right
  20. # until we arrive at str[i]'s new, rightful place
  21. while !sorted?(str)
  22.  
  23.     for i in 1...strlen #exclusive range
  24.  
  25.         if str[i-1] > str[i]
  26.             hold = str[i] # store value to INSERT  
  27.  
  28.             pos = i
  29.  
  30.             while pos > 0 && str[pos - 1] > hold
  31.                 str[pos] = str[pos - 1] # shift up
  32.                 pos -= 1
  33.  
  34.                 # stop if we have shifted all the elements that are BOTH greater than str[i] AND
  35.                 # to the left of str[i]
  36.             end
  37.            
  38.             # put str[i] in its rightful spot, just left of the last element we shifted, or the original spot of
  39.             # the last element we shifted
  40.             str[pos] = hold
  41.         end
  42.  
  43.     end
  44.  
  45. end
  46. puts str.join('')
RAW Paste Data