我的选择排序算法有什么问题？

Question

我的选择排序算法有什么问题？

3

对于经验丰富的人来说，答案可能很明显，但我已经看了几个小时的书，我的眼睛很累，似乎找不到错误。

下面是我编写的选择排序的两个实现，但都没有正确地对输入进行排序。您可以在在线解释器上试运行此代码。

def selection_sort_enum(array)
  n = array.length - 1

  0.upto(n - 1) do |i|
    smallest = i

    (i + 1).upto(n) do |j|
      smallest = j if array[j] < array[i]
    end

    array[i], array[smallest] = array[smallest], array[i] if i != smallest
  end
end

def selection_sort_loop(array)
  n = array.length - 1
  i = 0
  while i <= n - 1
    smallest = i
    j = i + 1
    while j <= n
      smallest = j if array[j] < array[i]
      j += 1
    end
    array[i], array[smallest] = array[smallest], array[i] if i != smallest
    i += 1
  end
end

这是第一个实现的测试，selection_sort_enum：

puts "Using enum:"
a1 = [*1..10].shuffle
puts "Before sort: #{a1.inspect}"
selection_sort_enum(a1)
puts "After sort: #{a1.inspect}"

这是第二个实现的测试，即 selection_sort_loop ：

puts "Using while:"
a2 = [*1..10].shuffle
puts "Before sort: #{a2.inspect}"
selection_sort_enum(a2)
puts "After sort: #{a2.inspect}"

以下是第一种实现方法 selection_sort_enum 的输出结果:

Using enum:
Before sort: [7, 5, 2, 10, 6, 1, 3, 4, 8, 9]
After sort:  [4, 3, 1, 9, 5, 2, 6, 7, 8, 10]

以下是第二种实现方法selection_sort_loop的输出结果：

Using while:
Before sort: [1, 10, 5, 3, 7, 4, 8, 9, 6, 2]
After sort:  [1, 2, 4, 3, 6, 5, 7, 8, 9, 10]

- Mohamad

你的问题写得有些令人困惑：你有两个输出。看起来你的“第一个输出”是指调用方法的代码。请调整你的问题，使其更加清晰明了。 - the Tin Man

@theTinMan 收到了。我已经更新了它以使其更清晰。感谢您指出这一点。 - Mohamad

2

你的第一个方法最好改名为selection_sort_enum!，因为你正在改变原始数组。如果要创建一个新的排序数组，只需将第一行更改为def selection_sort_enum(arr); array = arr.dup。 - Cary Swoveland

3个回答

1

def selection_sort_enum(array)
  n = array.length - 1 

  0.upto(n) do |i| # n instead of (n - 1)
    smallest_index = i

    (i + 1).upto(n) do |j|
      smallest_index = j if array[j] < array[i]
    end

    puts "#{array}", smallest_index
    array[i], array[smallest_index] = array[smallest_index], array[i] if i != smallest_index
  end
end

- Ilya

这对我有用，但一些解释会很有帮助。 - Cary Swoveland

1

你可能会对这个感兴趣：

def selection_sort_enum(array)
  n = array.length - 1

  0.upto(n - 1) do |i|
    smallest = i

    (i + 1).upto(n) do |j|
      smallest = j if array[j] < array[i]
    end

    array[i], array[smallest] = array[smallest], array[i] if i != smallest
  end
  array # <-- added to return the modified array
end

def selection_sort_loop(array)
  n = array.length - 1
  i = 0
  while i <= n - 1
    smallest = i
    j = i + 1
    while j <= n
      smallest = j if array[j] < array[i]
      j += 1
    end
    array[i], array[smallest] = array[smallest], array[i] if i != smallest
    i += 1
  end
  array # <-- added to return the modified array
end

require 'fruity'

ARY = (1 .. 100).to_a.shuffle
compare do
  _enum { selection_sort_enum(ARY.dup) }
  _loop { selection_sort_loop(ARY.dup) }
end

这导致了什么结果：

# >> Running each test once. Test will take about 1 second.
# >> _enum is faster than _loop by 3x ± 1.0

- the Tin Man

我真的很惊讶枚举比循环更快。我认为循环作为一种原始操作会更快。谢谢。 - Mohamad

1

请不要在答案中编辑代码。虽然这个答案只是提供信息，但它也是测试的记录。改变代码会改变问题或答案的预期含义，因此不应该这样做。代码返回错误结果并不重要，重要的是其中一个比另一个快得多。您可以要求进行更改。 - the Tin Man

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- uSeemSurprised · Accepted Answer

在这两个示例代码中，你比较的索引应该是smallest而不是i。

以下代码应该可以正常工作：

def selection_sort_enum(array)
  n = array.length - 1

  0.upto(n - 1) do |i|
    smallest = i

    (i + 1).upto(n) do |j|
      smallest = j if array[j] < array[smallest]
    end
    array[i], array[smallest] = array[smallest], array[i] if i != smallest
  end
end

def selection_sort_loop(array)
  n = array.length - 1
  i = 0
  while i <= n - 1
    smallest = i
    j = i + 1
    while j <= n
      smallest = j if array[j] < array[smallest]
      j += 1
    end
    array[i], array[smallest] = array[smallest], array[i] if i != smallest
    i += 1
  end
end

输出：

Using enum:
Before sort: [5, 6, 7, 9, 2, 4, 8, 1, 10, 3]
After sort: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Using while:
Before sort: [6, 5, 9, 2, 1, 3, 10, 4, 7, 8]
After sort: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

链接到解决方案：http://ideone.com/pKLriY