这是选择排序算法的忠实再现？ [英] Is this a faithful rendition of the selection sort algorithm?

问题描述

我一直在读一所本书排序算法。为了让我的头周围，我试着写来实现算法的简单程序。

I've been reading an elementary book about sort algorithms. To get my head around it, I tried to write a simple program to implement the algorithm.

编辑：我省略了，这是在previous版本的重要防线 - 见下面的评论

I had omitted an important line that was in a previous version - see comment below.

这是我的选择排序：

class SelectionSorter

  attr_reader :sorted

  def initialize(list)
    @unsorted = list
    @sorted = []
  end

  def select(list)
    smallest = list.first
    index = 0
    list.each_with_index do |e,i|
      if e < smallest
        smallest = e
        index = i
      end
    end
    @sorted << list.delete_at(index)
  end

  def sort
    @unsorted.length.times { self.select(@unsorted) }
  end

end

这是一个测试：

Here's a test:

require 'minitest/autorun'
require_relative 'sort'

class SelectionSortTest < MiniTest::Test

  describe SelectionSorter do

    it 'sorts a randomly generated list' do
      list = (1..20).map { rand(100-1) + 1 }
      sorted_list = list.sort
      sorter = SelectionSorter.new(list)
      sorter.sort
      sorter.sorted.must_equal sorted_list 
    end

  end

end

我很想意见，特别是围绕这是否实际上是一个忠实的执行算法。

I'd love comments, particularly around whether this is actually a faithful implementation of the algorithm.

编辑2：

确定 - 这是我就地code。这是事情我想避免的，因为它感觉nastily程序，与嵌套循环排序。但是，我认为这是一个忠实执行。

OK - here's my in-place code. This is the sort of thing I wanted to avoid, as it feels nastily procedural, with nested loops. However, I think it's a faithful implementation.

class SelectionSorter

  def sort(list)
    sorted_boundary = (0..(list.length)-1)
    sorted_boundary.each do |sorted_index|
      smallest_index = sorted_index
      smallest_value = list[smallest_index]
      comparison = sorted_index + 1
      (comparison..(list.length-1)).each do |next_index|
        if list[next_index] < smallest_value
          smallest_index = next_index
          smallest_value = list[smallest_index]
        end
      end
      unless sorted_index == smallest_index
        list[smallest_index] = list[sorted_index]
        list[sorted_index] = smallest_value
      end
    end
    list
  end

end

我很愿意这样做更递归的方式，以较少的存储的状态，并没有嵌套循环。有什么建议？

I'd love to do this in a more recursive fashion, with less stored state, and without nested loops. Any suggestions?

推荐答案

尝试添加最小= E 后立即指数=我，所以要保持迄今为止发现的最小的值的标记牌。

Try adding smallest = e immediately after index = i, so you are keeping a running tally of the smallest value found so far.

我还要注意，选择排序是就地通常实现，即，扫描位置1-N的对于最小的列表，然后将其交换与第一元件，然后用元件重复该过程2-N， 3-N等没有必要对第二阵列或从阵列的中间删除元素为代价。

I'd also note that selection sort is usually implemented in-place, i.e., scan locations 1-N of your list for the min and then swap it with the first element, then repeat the process with elements 2-N, 3-N, etc. There's no need for a second array or the expense of removing elements from the middle of an array.

这篇关于这是选择排序算法的忠实再现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！