Geek asks and answers

Problem with the sorting algorithm in the RailsWizard

RailsWizard , a tool for creating rail templates, allows you to set the order of recipes by specifying which recipes should be executed before (option run_before) and after ( run_after) this recipe, as described in https://github.com/intridea/rails_wizard/wiki/Recipe-Configuration

This is implemented in the Recipeclass :

module RailsWizard
  class Recipe
    extend Comparable

    def self.<=>(another)
      return -1 if another.run_after.include?(self.key) || self.run_before.include?(another.key)
      return 1 if another.run_before.include?(self.key) || self.run_after.include?(another.key)
      self.key <=> another.key # simple sort by name
    end
  end
end

However, this algorithm often provides the wrong order, see the corresponding problem and a demonstration script for this problem: https://gist.github.com/987025

How do you fix this algorithm?

+3
source share
1 answer

, Strict Weak Ordering.

, ( x < y y < z, x < z). :

  • n < l
  • l < m
  • m < n

, m < n, , n < < . .

, . -, , , , O (n ^ 2), .

, before?.

require 'yaml'
hash = YAML.load '
a:
  after: 
  before: 
l:
  after: 
  before: 
n:
  after: 
  before: l
b:
  after: 
  before: 
m:
  after: 
  before: 
c:
  after: 
  before: 
z:
  after: 
  before: 
'
hash.each do |k,v|
  v.each do |vk,vv|
    v[vk] = (vv||'').split
  end
end

class Hash
  def without *ks
    delete_if { |k,v| ks.include? k }
  end
  def delete! *ks
    #print "\n\nwithout: #{ks.join(', ')}"
    replace without *ks
  end
end

def print_keys hash
  puts hash.map(&:first).join('  ')
end

def sort hash
  array = hash.to_a
  selection_sort array
  print_keys array
  Hash[array]
end

def selection_sort array
  (0...array.length).each do |i|
    min = i
    ((i+1)...array.length).each do |j|
      min = j if before?(array[j], array[min])
    end
    temp = array[min]
    array[min] = array[i]
    array[i] = temp
  end
end

def before? a, b
  b.last['after'].include?(a.first) || a.last['before'].include?(b.first)
end

def test hash
  puts nil,nil
  print_keys hash
  puts '-'*hash.count*3
  hash.count.times { hash = sort hash }
end

test hash

:

$ ruby sort_test.rb 


a  l  n  b  m  c  z
---------------------
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
+1

More articles:


All Articles