Search code examples
rubybubble-sortenumerable

Is there a way to do Bubble Sort algorithm in Ruby using a while loop with an any method?


I'm trying to use a while loop with an any enumerable to optimize the Bubble Sort algorithm, but having trouble figuring out a way to make it work. Right now, I'm getting an error, but I want to know if conceptually I'm on the right track?

I've attached a few examples that the code should return for better context.

def bubble_sort(arr)
    while arr.any? { |ele, idx| ele > arr[idx + 1] }
        if arr[idx] > arr[idx + 1]
            arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
        end
    end
    return arr
end

p bubble_sort([2, 8, 5, 2, 6])      # => [2, 2, 5, 6, 8]
p bubble_sort([10, 8, 7, 1, 2, 3])  # => [1, 2, 3, 7, 8, 10]

Solution

  • def bubble_sort(arr)
      sorted = false
      while !sorted
        did_a_swap = false
        arr.each_index do |idx|
          next unless arr[idx + 1]
          if arr[idx] > arr[idx + 1]
            did_a_swap = true
            arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
          end
        end
        sorted = !did_a_swap
      end
      return arr
    end
    
    p bubble_sort([2, 8, 5, 2, 6])      # => [2, 2, 5, 6, 8]
    p bubble_sort([10, 8, 7, 1, 2, 3])  # => [1, 2, 3, 7, 8, 10]
    

    If you accept that you do a full pass through of the array every time there is at least one unsorted pair, then you can use while !sorted and define sorted as was there zero swaps this run?