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.
- worst case: O(n^2) (this is really bad for large lists)
- iterate through each item in the list.
- compare the item with its neighbor.
- swap the elements if they are in the wrong order.
- iterate through the list again and again until no more swapping occurs.
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