CODEWITHSUNDEEP
ruby
nini
nini

Reputation: 41

Please help me explain how to sort an array without using Array#sort Ruby

The bubble_sort method should accept an array of numbers and arrange the elements in increasing order. The method should return the array. I understand the swap part but don't really understand the flipping of true and false and the reason they're there at the first place. It would be great to explain it line by line to help me understand this.

Do not use the built-in Array#sort

def bubble_sort(arr)
    sorted = false

    while !sorted
        sorted = true
        (0...arr.length-1).each 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


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]

Upvotes: 1

Views: 105

Answers (2)

user1934428
user1934428

Reputation: 22356

The reason why you swapped something is that you knew by the time that the array is not sorted yet. In an already sorted array, you would never swap anything. sorted = false just records this fact.

Upvotes: 0

BobRodes
BobRodes

Reputation: 6175

Suppose we step through the code, using the first example. At the beginning, sorted is set to false. So the while loop kicks in, because !sorted is true. We start inside the loop by setting sorted back to true. Then we use #each to go through the array elements. We compare each element to the element following it. If the first element is greater than the next one, we flip them and set sorted to false.

If sorted is false, we repeat the while loop, again setting sorted to true and using #each to run through the array. If we go through the entire array without having to flip any elements, then sorted never gets set to false, we exit the loop, and the array is sorted.

In the first example, [2, 8, 5, 2, 6], it looks like this. First pass: 2 and 8 are left as is. 8 and 5 get flipped (and sorted gets set to false). 8 and 2 get flipped. 8 and 6 get flipped. Array now looks like [2, 5, 2, 6, 8].

Next pass: 2 and 5 are left as is. 5 and 2 get flipped (and sorted gets set to false). 5 and 6 are left as is. 6 and 8 are left as is. Array now looks like [2, 2, 5, 6, 8].

Next pass: array is in sorted order, nothing gets flipped, sorted doesn't get changed to false, we exit the loop and return the sorted array.

If you want to get a better idea of how it works, you can add the line p arr just before the end of the while loop. Then it will print out the changes that each pass through the loop makes.

I would also recommend that you install and learn how to use pry and pry-byebug. If you were able to step through this code, I think you would see how it works very quickly.

Upvotes: 0

Related Questions