練習:クイックソート (実行状況付)
クイックソートも実行状況が出るようにしてみました。
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]