Rubyの簡単なコーディング問題にバブルソート法を実装しようとしているのですが、うまくいきません。最初の要素の値を見て、それを2番目の要素の値と比較し、それに応じて交換するという考えは理解していますが、実際の問題ではそれを行うことができないようです. これがRubyでどのように機能するかについて、簡単な例を提供してくれる人はいますか?
質問する
19645 次
14 に答える
14
whileループを使用したバブルソートの正しい実装
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
于 2013-01-18T07:55:23.257 に答える
7
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]
于 2013-01-30T20:33:33.093 に答える
2
これが私のバージョンのトップアンサーです。ループごとではなく、配列の size を 1 回だけ呼び出します。要素が配列の最後に移動すると、要素は比較されません。
while ループは 1 ループ早く終了します。アレイ全体を調べて、スワップを 1 回だけ行ったら完了です。そのため、スワップが 0 の場合は別のことを行う必要はありません。
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
このテストの実行にかかる時間は 25% 短縮されます。
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
于 2013-02-23T01:37:28.847 に答える
2
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
私は確かにbubblesortよりも優れたランタイムを持つものをお勧めします:)
于 2012-06-18T21:38:39.667 に答える
1
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
于 2013-05-25T18:29:51.083 に答える
0
演算子 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
于 2014-09-11T10:29:28.167 に答える
0
クラス配列
a = [6, 5, 4, 3, 2, 1]
n = a.長さ
0..n-1 の j に対して
for i in 0..n - 2 - j
もし a[i]>a[i+1]
tmp = a[i]
a[i] = a[i+1]
a[i+1] = tmp
終わり
終わり
終わり
a.inspect を入れます
終わり
于 2015-01-26T11:18:21.417 に答える
0
もうひとつ、ちょっと違うネーミング。
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
于 2016-08-13T00:29:57.003 に答える
0
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
于 2013-04-16T05:15:49.800 に答える
0
これが私のコードです。(arr.length-1) を使用するのが好きです。for ループには、until、while、for、upto、loop do などの反復も使用できます。さまざまなことを試して、それがどのように機能するかを確認するのは楽しいことです。
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
于 2013-10-18T06:19:57.303 に答える