oaktree

Bubble Sort - Ruby

Mar 6th, 2016
140
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #! /usr/bin/env ruby
  2.  
  3. # get input
  4. puts "give me a string"
  5. str = gets.chomp.split('')
  6. strlen = str.length
  7. # end get input
  8.  
  9. changes_made = false #optimization to reduce time complexity
  10.  
  11. for i in 0..(strlen - 2) # vvv
  12. # 0 thru two less than the length of str, because we never need to see the last element explicitly
  13. # because we reach later on with str[j+1]
  14.  
  15.     for j in 0..(strlen - 2)
  16.  
  17.         if str[j] > str[j+1]
  18.             str[j],str[j+1] = str[j+1],str[j] # Ruby way to swap vars
  19.             changes_made = true # record that a change was made in this runthrough
  20.         end
  21.  
  22.     end
  23.  
  24.     break if !changes_made
  25.     # if there were no changes this run, the list is sorted
  26.     # why continue "sorting" if we've already done the job?
  27.  
  28.     # if there was a change made, set that to false and run through again,
  29.     # unless, of course, we've already gone through
  30.     changes_made = false
  31. end
  32.  
  33. puts str.join('') #print out the result, but first make it a string and not an array
RAW Paste Data