Bubble sort algorithm

Bubble sort is a sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent numbers and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Jarkyn asked me to implement a solution for a Bubble sort algorithm kata. Even if I had understood the logic, it took me a while to figure out how to write the sudo code correctly. I paired with Mollie on that, and she was a huge help. After, I tried to write the tests and the code on my own. Even if the sudo code we wrote with Mollie was very much like the code I had to write, I found it very discouraging and frustrating and could barely write anything after two tests. I asked Daisy for help, and again, thanks to the pairing we did, things began clearer, and we found a solution. Below:

describe BubbleSort do

let(:bubblesort) { BubbleSort.new}
  it " should return the same array if the array is already sorted" do
   expect(bubblesort.sort([0,1])).to eq([0,1])
 end

it "takes an unsorted array of two elements and returns it   sorted" do
   expect(bubblesort.sort([3, 2])).to eq([2,3])
  end

it "takes an unsorted array of two different elements and returns it sorted" do
   expect(bubblesort.sort([2, 1])).to eq([1,2])
  end

it "takes an unsorted array of three different elements and returns it sorted" do
   expect(bubblesort.sort([3,1,2])).to eq([1,2,3])
  end

it "takes a descending order array and makes it ascending order" do
    expect(bubblesort.sort([5, 4, 3, 2, 1])).to eq([1, 2, 3, 4, 5])
  end
end

class BubbleSort

def sort(array)
    loop do
      swapped = false
      (array.size - 1).times do |index|
        if array[index] > array[index + 1]
          array[index], array[index + 1] = array[index + 1],         array[index]
          swapped = true
        end
      end
      break if swapped == false
    end
    array
  end
end

What is important to understand in this solution is that we have to have two loops (nested loops).

When we enter the first loop, we haven’t done any swaps yet so swapped = false, then we get to:

(array.size - 1).times do |index|

This will calculate how many passes, we have to go through the list.

If the array contains two numbers, i.e., [2,1] there will be one pass, we only need to compare 2 and 1 one times to sort them.

If the array contains four numbers [5,8,4,7], there will be three passes; we will compare 5 to 8 and 8 to 4 and finally 8 to 7.

Once we know that, we go to the conditional statement below and swap the adjacent numbers. This is called a parallel assignment

array[index], array[index + 1] = array[index + 1],array[index]

We just swapped numbers so swapped = true. We hit “end” and go back to the (array.size — 1).times do |index| and do what we just did before.

We will do it as long as we need to do it depending on the size of the array.

The array is sorted when the conditional statement is equal to false.

if array[index] > array[index + 1]  ---> not true

So, if it’s not true, we don’t swap numbers, if we don’t swap numbers, then swapped == false then we break the loop. We get out of the loop and we return the array sorted.