Раздел «Язык Ruby».QuickSort:

Быстрая сортировка на Ruby

Конечно, на практике нужно пользоваться методами sort и sort_by, определенными для всех стандартных контейнеров. Эти функции возвращают массив.

В учебных целях реализуем алгоритм быстрой сортировки на самом Ruby.

Содержание:

Метод 1

Попробуем использовать метод partition, определенный для экземпляров Enumerable:

class Array 
   def qsort
      return self.dup if size <=1
      # делить на части будем по первому элементу
      l,r = partition   {|x| x <= self.first}
      c,l = l.partition {|x| x == self.first}
      l.qsort + с + r.qsort # конкатенация трех массивов
   end
end

Метод 2

Но удобно делить исходный массив сразу на три массива. Для этого определим метод partition3:

class Array 
   # given block should return 0,1 or 2
   # -1 stands for 2
   # outputs three arrays
   def partition3
      a = Array.new(3) {|i| []}
      each do |x|
         a[yield(x)].push x
      end
      a
   end
   def qsort
      return self.dup if size <=1
      c,l,r = partition3 {|x| first <=> x}
      l.qsort + c +  r.qsort
   end
end   

Можно сделать более универсальную функцию partitionN

class Array
   def partitionN
      inject(Hash.new) { |f,x|
         key = yield(x)
         f[key]=[] unless f.has_key?(key)
         f[key].push x
         f
      }.to_a.sort.map{|pair| pair[1]}
   end
end
p [0,1,2,3,5,4,3,6,7,5,4,3,4,65,7,87,4523].partitionN {|x| x % 4}
#
# => [[0, 4, 4, 4], [1, 5, 5, 65], [2, 6], [3, 3, 7, 3, 7, 87, 4523]]
#

Реализация qsort!

Необходима также версия функции сортировки, которая сортирует массив "на месте". Вот она:

class Array
   def qsort!
      self.replace(self.qsort)
   end
end
a = [1,7,6,5,4,3,2,1]
a.qsort!
p a
#
# => [1, 1, 2, 3, 4, 5, 6, 7]
#

Метод, создающий методы-модификаторы

Целый ряд методов в стандартных классах Ruby имеет аналоги, модифицирующие сам объект. Имена этих функций заканчиваются на !, например, sort!, uniq!, map!.

Их все можно было определить разом. Например так:

def make_modifier(*methods)
   methods.each do |method|
      eval " 
         class #{self.to_s}
            def #{method}!(*args,&block)
               self.replace(self.#{method}(*args,&block))
            end
         end
      "
   end
end
class Array
   make_modifier :sort, :uniq, :map
end

Из соображений оптимизации такие вещи не делаются для ключевых функций (из соображений оптимизации многие методы стандартных классов реализованы на Си). Но в принципе, это очень правильная идея — можно и нужно использовать средства метапрограммирования для упрощения кода и уменьшения труда программиста.

Более концептуальная реализация make_modifier

def make_modifier(*methods)
   methods.each do |method|
      define_method(method.to_s + '!') do |*args, &block|
        self.replace(self.send(method, *args, &block))
      end
   end
end

Ну, и наконец, концептуально правильнее программировать функцию qsort!, сортирующую массив на месте, а затем определять qsort:

class Array
   def qsort
      self.dup.qsort!
   end
end