This is a very simplistic sorting algorithm that iterates through each item in the list comparing each item with its neighbor. Over and over again until the list is sorted.

This type of sort works fine for small lists. As the input size grows the time to sort grows as well.

steps

  1. iterate through each item in the list.
  2. compare the item with its neighbor.
  3. swap the elements if they are in the wrong order.
  4. iterate through the list again and again until no more swapping occurs.

example

In this example the code loops until no more swapping occurs.

class BubbleSort
  def sort(items)
    return items if items.size <= 1

    swapped = false
    loop do
      items.size.times do |n|
        if (items[n] <=> items[n+1]) == 1
          items[n], items[n+1] = items[n+1], items[n]
          swapped = true
        end
      end
      break unless swapped
      swapped = false
    end
    items
  end
end
comments powered by Disqus