Using the Bubble sort method for an array in Ruby

问题:

I'm trying to implement the Bubble sort method into an easy coding problem for Ruby, but I'm having some trouble. I understand the idea is to look at the value of the first element and compare it to the value of the second element and then swap them accordingly, but I can't seem to do it in an actual problem. Would anyone be willing to provide a brief example of how this might work in Ruby?

回答1:

Correct implementation of the bubble sort with a while loop

def bubble_sort(list)
  return list if list.size <= 1 # already sorted
  swapped = true
  while swapped do
    swapped = false
    0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
        list[i], list[i+1] = list[i+1], list[i] # swap values
        swapped = true
      end
    end    
  end

  list
end

回答2:

arr = [4,2,5,1]
loop until arr.each_cons(2).with_index.none?{|(x,y),i| arr[i],arr[i+1] = y,x if x > y}
p arr #=> [1, 2, 4, 5]

回答3:

Source

def bubble_sort(list)
  return list if list.size <= 1 # already sorted

  loop do
    swapped = false
    0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
        list[i], list[i+1] = list[i+1], list[i] # swap values
        swapped = true
      end
    end
    break unless swapped
  end

  list
end

Although I would certainly recommend something with a better run-time than bubblesort :)

回答4:

Here's my version of the top answer. It calls size on the array only once instead of every loop. It doesn't compare elements once they have moved to the end of the array.

And the while loop quits one loop sooner. You're done once you've gone through the whole array and only did one swap, so no need to do another with 0 swaps.

def bubble_sort(list)
  iterations = list.size - 2

  return list unless iterations > 0 # already sorted

  swaps = 2

  while swaps > 1 do
    swaps = 0

    0.upto(iterations) do |i|
      if list[i] > list[i + 1]
        list[i], list[i + 1] = list[i + 1], list[i] # swap values
        swaps += 1
      end
    end

    iterations -= 1
  end

  list
end

Running this test takes 25% less time.

that_array = this_array = [22,66,4,44,5,7,392,22,8,77,33,118,99,6,1,62,29,14,139,2]
49.times {|variable| that_array = that_array + this_array}
bubble_sort that_array

回答5:

Just re-writing @VanDarg's code to use a while loop (note: code not tested... run at your own peril)

def bubble_sort(list)
  return list if list.size <= 1 # already sorted

  swapped = true
  while swapped
    swapped = false # maybe this time, we won't find a swap
    0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
        list[i], list[i+1] = list[i+1], list[i] # swap values
        swapped = true # found a swap... keep going
      end
    end
  end

  list
end

Edit: updated swapped-values because bubble sort keeps sorting while there are still swaps being made - as soon as it finds no more swaps, it stops sorting. Note, this does not follow @Doug's code, but does conform with @cLuv's fix

回答6:

def bubble_sort array 
  array.each do
    swap_count = 0
    array.each_with_index do |a, index|
      break if index == (array.length - 1)
      if a > array[index+1]
        array[index],array[index+1] = array[index +1], array[index]
        swap_count += 1
      end
    end
    break if swap_count == 0 # this means it's ordered
  end
  array
end

回答7:

The straight forward:

def bubble_sort(n)
  return n if n.length <= 1

  0.upto(n.length - 1) do |t|
    0.upto(n.length - 2 - t) do |i|
      if n[i] > n[i + 1]
        n[i], n[i + 1] = n[i + 1], n[i]
      end
    end
  end

  n
end

回答8:

If you don't want to use this funny swapping line (IMO):

    arr[i], arr[j] = arr[j], arr[i]

here's my take:

def bubble_sort(arr)
  temp = 0

  arr.each do |i|
    i = 0
    j = 1
    while (j < arr.length)
      if arr[i] > arr[j]
        temp = arr[i] 
        arr[i] = arr[j]
        arr[j] = temp 
        p arr
      end
    i+=1
    j+=1
    end
  end  
 arr
end

回答9:

Old school

def bubble_sort(random_numbers)
for i in 0..random_numbers.size 
  for j in i+1..random_numbers.size-1    
    random_numbers[i], random_numbers[j] = random_numbers[j], random_numbers[i] if(random_numbers[i] > random_numbers[j])
  end
end
random_numbers
end

回答10:

class Array
a = [6, 5, 4, 3, 2, 1]
n = a.length

for j in 0..n-1
    for i in 0..n - 2 - j
           if a[i]>a[i+1]
                tmp = a[i]
                a[i] = a[i+1]
                a[i+1] = tmp
          end
     end
end

puts a.inspect
end

回答11:

Here's my take using the operator XOR:

def bubble(arr)
     n = arr.size - 1
     k = 1
     loop do
          swapped = false
          0.upto(n-k) do |i|
              if arr[i] > arr[i+1]
                 xor = arr[i]^arr[i+1]
                 arr[i] = xor^arr[i]
                 arr[i+1] = xor^arr[i+1]
                 swapped = true  
              end 
          end 
          break unless swapped
          k +=1 
     end
   return arr
end  

回答12:

Another, slightly different naming.

def bubble_sort(list)
  return list if list.size <= 1
  not_sorted = true

  while not_sorted
    not_sorted = false

    0.upto(list.size - 2) do |i|
      if list[i] > list[i + 1]
        list[i], list[i + 1] = list[i + 1], list[i]
        not_sorted = true
      end
    end
  end
  list
end

回答13:

 def bubbleSort(list)
  sorted = false
  until sorted
    sorted = true
    for i in 0..(list.length - 2)
      if list[i] > list[i + 1]
        sorted = false
        list[i], list[i + 1] = list[i + 1], list[i]
      end
    end
  end
  return list
end

回答14:

Here is my code. I like using the (arr.length-1). For loops you can also use such iterations such as until, while, for, upto, loop do, etc. Fun to try different things to see how it functions.

def bubble_sort(arr)  #10/17/13 took me 8mins to write it

return arr if arr.length <= 1

sorted = true

    while sorted
     sorted = false
     (arr.length-1).times do |i|
        if arr[i] > arr[i+1]
          arr[i], arr[i+1] = arr[i+1], arr[i]
          sorted = true
        end
       end
     end
    arr
    end