Bubble Sort in Ruby

Overview

Bubble Sort is an extremely simple and generally poor-performing algorithm for sorting which iterates through a list and swaps values that are in the wrong order. This process is repeated until the list is fully sorted. It has a worst-case and average complexity of O(n^2).

Concise

def bubble_sort(a)
  s = false

  (a.length-1).times do |i|
    if a[i] > a[i+1]
      a[i], a[i+1] = a[i+1], a[i]
      s = true
    end
  end
  p a

  if s
    bubble_sort(a)
  else
    return a
  end
end

a = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
p a

s = bubble_sort(a)
puts s.inspect
bubble_sort.rb

Verbose

# Bubble Sort in Ruby
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def bubble_sort(numbers)

  # Set an initial value of false for swapped, because nothing has been swapped.
  swapped = false

  # Iterate through the array, swapping each value if it is larger than
  # the next value in the array. If the values are swapped, set our swapped
  # variable to true so that we know another pass is needed.
  (numbers.length-1).times do |i|
    if numbers[i] > numbers[i+1]
      numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
      swapped = true
    end
  end
  p numbers

  if swapped
    bubble_sort(numbers)
  else
    return numbers
  end
end

# Generate array of ten random integers.
unsorted = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
puts unsorted.inspect

# Sort.
sorted = bubble_sort(unsorted)
puts sorted.inspect
bubble_sort_verbose.rb

Sample Input and Output

$ ruby bubble_sort.rb
[3, 2, 7, 6, 5, 9, 4, 1, 8, 0]
[2, 3, 6, 5, 7, 4, 1, 8, 0, 9]
[2, 3, 5, 6, 4, 1, 7, 0, 8, 9]
[2, 3, 5, 4, 1, 6, 0, 7, 8, 9]
[2, 3, 4, 1, 5, 0, 6, 7, 8, 9]
[2, 3, 1, 4, 0, 5, 6, 7, 8, 9]
[2, 1, 3, 0, 4, 5, 6, 7, 8, 9]
[1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Further Reading