Need help understanding the syntax / logic in a Ruby bubble sort solution
I need help understanding some of the syntax and logic in this programmatic solution.
def bubble_sort(arr)
sorted = false
until sorted
sorted = true
(arr.count - 1).times do |i|
if arr[i] > arr[i + 1]
arr[i], arr[i + 1] = arr[i + 1], arr[i]
sorted = false
end
end
end
arr
end
In particular, I found it difficult to understand the until
and sorted = true
and loop part sorted = false
. I read a bit here and I think what I get is that if the array still needs to be modified, it is sorted
set to false
and the loop continues. But I would appreciate it if someone could explain this to me just one more time.
It looks like the time loop runs only once for each element of the array minus one and then replaces the positions. How does the cycle work before?
source to share
The loop .times
performs a single pass through the array, comparing each element with its neighbor and swapping them if they are in the wrong order.
The outer loop until sorted
repeats this process until nothing changes. At this point, the array is sorted.
The variable sorted
records if we changed any elements during our last pass over the array. If we did, the array would change, and we're not done yet. On the other hand, if no element has been replaced, sorted = false
it is not executed, it sorted
remains true
and we can exit the outer loop.
source to share
You are correct that it iterates through the array, checking the values and swapping if necessary - if a swap was done in the process, it considers the array unsorted and sets sorted = false. If so, the while loop will ensure that all new pass through the array to rerun the process. The only time the loop stops so far is when there were no swaps during the pass. At the start of each one until the sort loop is set to true because it assumes this will be the last pass - unless a swap is produced that sets sorted = false then it will perform at least one pass.
Have a look at http://visualgo.net/sorting.html# if you want a neat animation to visualize what's going on in the various sorting algorithms.
source to share