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]
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?