【Ruby】【アルゴリズム】改めてソート。コードの変り様！

一ヶ月と一週間前、10個のクイックソートに38秒かかってた
と過去を暴露していたけど

果たしていまはどれくらい綺麗にかけるようになってるのか。
また書いて、試してみた。

バブルソート

■今のコード

p data = (0..9).to_a.sample(10)
def bubble_sort(data)
  (data.length-1).times do |j|
    (data.length-(j+1)).times do |i|
      data[i], data[i+1] = data[i+1], data[i] if data[i]>data[i+1]
    end
  end
  data
end
p bubble_sort(data)

　
■以前のコード

a = (0..9).to_a
a = a.sample(a.length)
i = 0
while i < a.length
  j = 1
  while j < a.length - i
    if a[i] > a[i+j] then
      a[i], a[i+j] = a[i+j], a[i]
    end
    j += 1
  end
  i += 1
end
p a

クイックソート

■今のコード
　
※軸固定Ver（早くない）
　何度も（左端/右端から繰り返して）同じインデックスを評価しているため

p data = (0..9).to_a.sample(10)
def quick_sort(data, left, right)
  return if right-left <= 1
  pivot_index = (left+right)/2
  change_left, change_right = nil, nil
  loop do
    change_left = left.step(pivot_index) do |i|
      break i if data[i] >= data[pivot_index]
    end
    change_right = (right).downto(pivot_index) do |j|
      break j if data[j] <= data[pivot_index]
    end
    break if change_left >= change_right
    data[change_left], data[change_right] = data[change_right], data[change_left]
  end
  quick_sort(data, left, change_left-1)
  quick_sort(data, change_left, right)
  data
end
p quick_sort(data,0, data.length-1)

　
※値固定Ver（早い）

p data = (0..9).to_a.sample(10)
def quick_sort(data, left, right)
  return if left >= right
  pivot_value = data[((left + right).to_f/2.to_f).ceil]
  change_left, change_right = left, right
  loop do
    change_left += 1 while data[change_left] < pivot_value
    change_right -= 1 while data[change_right] > pivot_value
    break if change_left >= change_right
    data[change_left], data[change_right] = data[change_right], data[change_left]
  end
  quick_sort(data, left, change_right-1)
  quick_sort(data, change_right, right)
  data
end
p quick_sort(data,0, data.length-1)

　
■以前のコード

a = (0..10).to_a
a = a.sample(a.length)
p a
def q_sort(a, pipot=nil)
  return a if a.size == 1
  if pipot == nil then
    pipot = a[a.size/2.ceil]
  end
  i = 0
  while i < a.size
    if a[i] >= pipot then
      j = a.size-1
      while j >= 0
        if a[j] <= pipot then
          if i < j then
            a[i], a[j] = a[j], a[i]
            if i +1 == j then
              a[0...i] = q_sort(a[0...i])
              a[i...a.size] = q_sort(a[i...a.size])
            else
              q_sort(a[i+1 ... j-1], pipot)
            end
          else
            a[0...i] = q_sort(a[0...i])
            a[i...a.size] = q_sort(a[i...a.size])
          end
        end
        j -= 1
      end
    end
    i += 1
  end
  a
end
q_sort(a)
p a

･･･良くなってる！
ポイントは、break節の値を返すところかな。