Newbie question on bubble sort algorithm

Hi: I’m a complete beginner to Ruby. All I know is what I’ve read on
Chris P.'s web tutorial. I’m trying to write code to sort a sequence
of numbers using the bubble sort algorithm:

sequence = [4, 2, 3, 1]
class Array
def swap!(a,b)
self[a], self[b] = self[b], self[a]
self
end
end
checkE = [0]
checkS = [1]
while checkE != checkS
posn = sequence.length - 1
checkS = sequence
while posn > 0
if sequence[posn] < sequence[posn-1]
sequence.swap!(posn,posn-1)
end
posn = posn - 1
end
checkE = sequence
end
puts sequence.join(’, ')

I found the swap method online and just copied it, but it seems to work.
I’m trying to use checkS and checkE to see if the sequence is the same
after the bubble algorithm has run as it is at the beginning, since then
I know it’s finished. But I’m doing something wrong and I can’t figure
out what. It just runs through the algorithm and then stops, instead of
running the loop. I’m sure there is a much more sophisticated way to do
this, but I’d be really grateful if someone can point out what I’m doing
wrong in this code. Very many thanks in advance for any help.

Simon

Hi,

The while loop stops after the first iteration, because you make checkS
and checkE both point to the sequence array. So checkE != checkS will be
false.

If you want to compare the array elements before and after each run, you
will have to make a new array by cloning the current one and apply the
swap! method to the clone:

old_array = []
new_array = sequence
while new_array != old_array
old_array = new_array.clone
i = new_array.length - 1
while i > 0
if new_array[i] < new_array[i - 1]
new_array.swap! i, i - 1
end
i -= 1
end
end
p new_array

However, it’s more efficient to use a flag which tells if the swap!
method has been used in the last run:

is_sorted = false
until is_sorted
is_sorted = true
i = sequence.length - 1
while i > 0
if sequence[i] < sequence[i - 1]
sequence.swap! i, i - 1
is_sorted = false
end
i -= 1
end
end
p sequence

Jacques

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs