Hi guys, I’m new to programming and to Ruby in general and I was seeking help with understanding how bubble sort works. So an example I found started off with setting the variable sorted = false, then constructing a while loop that executes while !sorted. Sorted starts out as false, so how does the while loop execute with the not sorted(true) condition, when I initialized the variable to false?
here’s the snippet of my code
def bubble_sort
[4] pry(main)* sorted = false
[4] pry(main)* while !sorted
[4] pry(main)* sorted = true
[4] pry(main)* (0…self.length-1).each do |index|
[4] pry(main)* if self[index] > self[index+1]
[4] pry(main)* self[index],self[index+1] = self[index+1],self[index]
[4] pry(main)* sorted = false
[4] pry(main)* end
[4] pry(main)* end
[4] pry(main)* end
[4] pry(main)* self
[4] pry(main)* end
Your method looks kind of like this:
Array.define_method(:bubble_sort) do
sorted = false
while !sorted
sorted = true
(0...self.length - 1).each do |index|
if self[index] > self[index + 1]
self[index], self[index+1] = self[index+1], self[index]
sorted = false
end
end
end
self
end
Your code woks fine as expected.
Array.new(10) { rand(1..10) }.tap { |x| x.dup.bubble_sort.eql?(x.sort).display } # writes true
I think you have the problem in understanding the while !sorted part, your question is how the while loop is executed when the sorted gets to false?
Actually when the sorted is set to true, the while loop breaks here. You see the sorted variable is continuously set to true after the while loop is started. Then there’s another each loop which iterates again over the array items, if the element n is greater than element n + 1, it swaps them in the array. The cycle repeats. At the end, when the if condition is not executed, the sorted is set to true, and the while !sorted loop breaks.
Although your method works fine, still you can make it a bit simpler. You don’t need those flags to be set to true or false.
Here’s a small implementation of the bubble sort algorithm:
Array.define_method(:bubble_sort!) do
# Let's keep the pass to 0, and assign s to the size to avoid calculating it in the loop continuously
l, s = -1, size - 1
until (l += 1) == s
i = -1
# Iterate over each element, and swap the value if the value is greater than the next one
self[i], self[i.next] = at(i.next), at(i) if at(i) > at(i.next) until (i += 1) == s
end
itself
end
# Test
unsorted, sorted = *Array.new(2_000) { srand }.yield_self { |x| [x, x.dup.sort] }
# Running code in atom runner (for atom) and code runner (for visual studio code) don't synchronize the output. Let's do that...
STDOUT.sync = true
puts('Sorting') || unsorted.bubble_sort! && puts('Sorted')
p unsorted.eql?(sorted) # => true
I am using the until loop because while and until loops are the fastest loops in Ruby.
Bubble sort is also slower than merge sort and quick sort algorithms. It’s good to know how it works, but it’s not worth implementing in a professional environment…
Here I did a benchmark between bubble sort, merge sort, and the Array#sort method:
You can run the code on your system, and experience the difference yourself!
Hope this helps!