按红宝石实现外壳排序

Question

我试着用红宝石来实现shell排序。

def shell_sort(list)
  d = list.length
  return -1 if d == 0
  (0...list.length).each do |i|
    d = d / 2
    puts "d:#{d}"
    (0...(list.length-d)).each do |j|
      if list[j] >= list[j+d]
         list[j], list[j+d] = list[j+d], list[j]
      end
    end
    puts list.inspect
    break if d == 1
  end
  list
end

puts shell_sort([10,9,8,7,6,5,4,3,2,1]).inspect

但结果是不正确的。

=>[2, 1, 3, 4, 5, 7, 6, 8, 9, 10]

我不知道哪里出了问题，希望有人能帮我。提前感谢！

Answer 1

我在这里引用了Shell排序：Shell排序- Wikepedia，由此我理解了您的算法是错误的。间隙序列的迭代是可以的，我的意思是你只迭代到d/2 == 1。

但是对于一个间隙，比方说2，您只需从0迭代到list.length-2，并交换每个j和j+2元素(如果list[j]大于list[j+2] )。这甚至不是正确的插入排序，Shell排序要求对空白进行插入排序。此外，Shell排序要求在进行x间隙排序之后，从任何地方开始的每个xth元素都将被排序(参见在链接上运行的示例，您可以验证自己)。

一种情况下，它可以错在一个2间隙排序的通行证：

list = 5,4,3,2,1
j = 0 passed :
list = 3,4,5,2,1
j = 1 passed : 
list = 3,2,5,4,1
j = 2 passed
list = 3,2,1,4,5

在它完成之后，您可以看到，从0开始的第二个元素没有按排序顺序排列。我建议您先学习插入排序，然后了解在Shell排序中使用它的位置和方式，如果您想自己进行排序，请再试一次。

不管怎么说，我已经写了一个(如果你想的话留到以后)，以你的方法为基础，有很多评论。希望你能从这件事中获得灵感。并试图使输出阐明算法的工作原理。

def shell_sort(list)
  d = list.length
  return -1 if d == 0

  # You select and iterate over your gap sequence here.
  until d/2 == 0 do
    d = d / 2

    # Now you pick up an index i, and make sure every dth element,
    # starting from i is sorted.
    # i = 0
    # while i < list.length do
    0.step(list.length) do |i|

      # Okay we picked up index i. Now it's just plain insertion sort.
      # Only difference is that we take elements with constant gap, 
      # rather than taking them up serially.
      # igap = i + d
      # while igap < list.length do
      (i+d).step(list.length-1, d) do |igap| 

         # Just like insertion sort, we take up the last most value.
         # So that we can shift values greater than list[igap] to its side,
         # and assign it to a proper position we find for it later.
         temp = list[igap]
         j = igap
         while j >= i do
           break if list[j] >= list[j - d]
           list[j] = list[j-d]
           j -= d
        end
        # Okay this is where it belongs.
        list[j] = temp

        #igap += d
      end

      # i += 1
    end
    puts "#{d} sort done, the list now : "
    puts list.inspect
   end
   list
end

list = [10,9,8,7,6,5,4,3,2,1]
puts "List before sort : "
puts list.inspect
shell_sort(list)
puts "Sorted list : "
puts list.inspect

Answer 2

我觉得你的算法需要调整一下。

它失败的原因很简单，因为在最后一次运行时(当d == 1)，最小的元素(1)不够接近，第一个元素一次就交换了它。

使其工作的最简单的方法是在元素切换位置时“重新启动”您的内部循环。所以，一些粗略的解决方案就像

(0...(list.length-d)).each do |j|
  if list[j] >= list[j+d]
    list[j], list[j+d] = list[j+d], list[j]
    d *= 2
    break
  end
end

这个解决方案当然不是最优的，但是应该以尽可能少的代码实现所需的结果。

Answer 3

您应该对数组进行最后一次运行。为了简化代码，我将exchange部分提取为独立的函数，以便您现在可以看到您应该在哪里这样做：

def exchange e, list
  (0...(list.length-e)).each do |j|
    if list[j] >= list[j+e]
      list[j], list[j+e] = list[j+e], list[j]
    end
  end
end

def shell_sort(list)
  d = list.length
  return -1 if d == 0
  (0...list.length).each do |i|
    d = d / 2
    puts "d:#{d}"
    exchange(d, list)
    puts list.inspect
    if d == 1
      exchange(d, list)
      break
    end
  end
  list
end

arr = [10,9,8,7,6,5,4,3,2,1]
p shell_sort(arr)

结果：

#> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]