練習：クイックソート (実行状況付)

クイックソートも実行状況が出るようにしてみました。

def trace(a, f, t, i, j, x)
  print " "
  a.each_index do |p|
    s  = if p == f then "[" else " " end
    s += if p == i || p == j then "T" else " " end
    s += if p == t then "]" else " " end
    printf "%-3s  ", s
  end
  puts "lim=#{x}"
  p a
end

module Sort
  module QuickSort
    def sort () self.clone.sort! end
    def sort! () execute(self, 0, self.size - 1) end
    def execute (a, f, t)
      x = a[(f + t) / 2]
      i = f
      j = t
      while true
        i += 1 while a[i] < x
        j -= 1 while a[j] > x
        break unless i < j
        a[i], a[j] = a[j], a[i]
$debug and trace(a, f, t, i, j, x)
        i += 1
        j -= 1
      end
      execute(a, f, i - 1) if (f < i - 1)
      execute(a, j + 1, t) if (j + 1 < t)
      return a
    end
    private :execute
  end
end

$debug = true

o = Array.new(12) do |i| rand(900) + 100 end
o.extend Sort::QuickSort
p o
o.sort

以下、実行状況。

[385, 449, 746, 880, 857, 746, 182, 636, 646, 590, 233, 786]
 [          T                                       T     ]  lim=746
[385, 449, 233, 880, 857, 746, 182, 636, 646, 590, 746, 786]
 [               T                             T          ]  lim=746
[385, 449, 233, 590, 857, 746, 182, 636, 646, 880, 746, 786]
 [                    T                   T               ]  lim=746
[385, 449, 233, 590, 646, 746, 182, 636, 857, 880, 746, 786]
 [                         T         T                    ]  lim=746
[385, 449, 233, 590, 646, 636, 182, 746, 857, 880, 746, 786]
 [               T              T]                           lim=590
[385, 449, 233, 182, 646, 636, 590, 746, 857, 880, 746, 786]
 [     T         T]                                          lim=449
[385, 182, 233, 449, 646, 636, 590, 746, 857, 880, 746, 786]
 [T    T     ]                                               lim=182
[182, 385, 233, 449, 646, 636, 590, 746, 857, 880, 746, 786]
      [T    T]                                               lim=385
[182, 233, 385, 449, 646, 636, 590, 746, 857, 880, 746, 786]
                     [T         T]                           lim=636
[182, 233, 385, 449, 590, 636, 646, 746, 857, 880, 746, 786]
                                    [          T         T]  lim=880
[182, 233, 385, 449, 590, 636, 646, 746, 857, 786, 746, 880]
                                    [     T         T]       lim=857
[182, 233, 385, 449, 590, 636, 646, 746, 746, 786, 857, 880]
                                    [T    T     ]            lim=746
[182, 233, 385, 449, 590, 636, 646, 746, 746, 786, 857, 880]