Bubble sort in ruby

Ruby
1

I’m trying to understand the given solution to a programing problem that uses the bubble sort algorithm to sort through an array. I know there are other, probably much easier ways to satisfy the tests at the end of the program, but I need to understand how it’s solved in this given way.

# Write a function `bubble_sort(arr)` which will sort an array of
# integers using the "bubble sort"
# methodology. (http://en.wikipedia.org/wiki/Bubble_sort)
#
# Difficulty: 3/5
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


puts bubble_sort([]) == []



puts bubble_sort([1]) == [1]


puts bubble_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]

What I don’t understand:

  1. I haven’t used until loops much. But from my understanding they are a sort of reverse condition while loop. In other words the loop should until sorted = true. But on the very next line after the until loop starts, sorted is set to be true. So shouldn’t the loop just end?

  2. What’s happening inside the times loop? If the element preceding the element after it is of less value, this happens

    arr[i], arr[i + 1] = arr[i + 1], arr[i]
    sorted = false

What is actually happening here? I’ve never seen syntax where there’s commas in code. It looks like it’s also assigning the value of the array index to itself? Lost here.

Sorry if it seems like there’s a lot here I need help with. I tried looking up the syntax elsewhere but couldn’t find anything. This was in a series of programing problems I needed to solve and all of the previous ones were much less difficult for me to figure out. Here I’ve just been thrown for a loop so to speak and I’m lost. Thanks in advance

2

Your overall assessment is correct. This is a bit confusing because, as you quite perceptively pointed out, sorted is set to false immediately as the function begins. The reason for this, however, is that the logic contained in times (which is also a ‘loop’ construct; a Ruby ‘block’) will assert sorted to false while (in the English sense) there was a need to switch values (e.g. sort).
In other words, once the operation has traversed the entire array AND there was no longer a need to make a swap in order to “bubble” a lower value before its higher brethren the sort is finished.
Without that flag the loop would be infinite; even after there are no more values that need to be rearranged.
Think of the value sorted as “Was a sort operation performed?” and its inverse as “No more work needs to be done; we are sorted”

Put another way:
Each time the execution reaches the end of the until the value of sorted will only be true a swap of values was not necessary in that iteration.
[Re]setting it to true at the beginning of the loop ensures the flag will be useful.

This is why recursive functions are difficult to grasp.

This is taking advantage of [one of] the many shortcuts in the Ruby language that has made it very popular among developers. In Ruby you can make multiple assignments on a single line.

val_one, val_two, val_three = 1, 2, 3

This will result in val_one containing 1, val_two containing 2 and val_three containing 3

You are correct that commas, used in this way, are unusual in most programming languages.

3

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.