再帰処理

再帰的な方法を用いてプログラムを組み立ててみよう。

再帰処理による並べ換え

Rubyでは、配列にsortメソッドが備わっているので、配列に入っているデータを並べ換えてもらうことができる。最近の多くの言語では、言語処理系の方に標準で並べ換え用のメソッドが用意されているのでたくさんのデータを並べ換える具体的な手順を知らなくてもよくなっている。

しかしここでは再帰処理を理解する上での題材として、並べ換え手法のひとつであるクイックソートを自分の手で作ってみよう。

クイックソートとは

クイックソートはたくさんあるデータ要素を次のような手順で並べ換える方法である。

【クイックソートの方法】 大きな箱 Xに任意個のデータが入っているものとする。クイックソートは以下の手順で行なう。 X の中のデータが1個以下なら並べ換え完了、そうでなければ次に進む X の中から、任意のデータを1個抜き取り、その値を k とする。 kを抜き取ったあとの中のデータを順次見ていき、それが k より小さかったら左側に置く そうでなければ右側に置く ことをデータがなくなるまで繰り返す 左側に寄せたものをクイックソートする 右側に寄せたものをクイックソートする 左右のかたまりの中間に k を置いて並べ換え完了

クイックソートしてみよう

クイックソートをカードを並べ換える方法に適用して体験して理解しよう。トランプを8枚用意しよう。といっても、すぐには用意できないので使用済みの紙切れを8枚に切って、それぞれに好きな数字を書こう。

数字を書いた8枚のカード(もっと多くてもよい)が準備できたら、よくシャッフルする。そうしたら以下の手順で並べ換えよう。

「クイックソートによるカードの並べ換え」

並べ換えるべき枚数が1枚以下なら終了、それ以上なら次に進む
まず1枚のカードを机の真中に置く
手に残ったカードから1枚ずつ引いていき

真中に置いたカードの数字より小さかったら左側に置く
そうでなければ右側に置く
ことをカードがなくなるまで繰り返す(このとき左右に置くカードはでたらめに並べるか重ねておいてよい)
左側に置いた山を左側の机スペースでクイックソートする
右側に置いた山を右側の机スペースでクイックソートする
おしまい

最初に選ぶカードに何を選んでもクイックソートが成功することを確認しよう

クイックソートを行なうメソッド

クイックソートを行なうメソッド qsort を定義しよう。

次のような設計とする。

qsort メソッドは引数として配列を受け取る
左側の箱、右側の箱としてそれぞれ、配列left、配列rightを利用する
left, right に対して再帰的に qsort する
最後に left, 真中の値, right を並べて完了

これを実際にメソッドにしてみよう。いきなりメソッドにするのは難しいので、ことばで骨子を考える。

def qsort(data)		 # dataは数値の入った配列
  if データが1個以下なら
    dataそのものを返して並べ換え完了
  else
    left(左側配列)を新規作成
    right(右側配列)を新規作成
    変数dataからデータを1個取り出す
    これを k とする

    残ったdata全てに対して以下を繰り返す
      if k より小さかったら
         leftに追加
      else
         rightに追加
      end
    繰り返し終わり

    「leftをqsortしたもの」と k と「rightをqsortしたもの」
    をその順に結合したものを結果として並べ換え完了
  end
end

※思い出しておこう※

第5回に学習した配列処理のためのメソッドを忘れていると次に説明する完成プログラムがさっぱり分からない。以下の配列に関するメソッドを思い出しておくこと。

配列の初期化は x=[] または、x=Array.new(個数, 値) で行なう
配列から要素を一個だけ取り出すメソッドには何があった?
先頭から一個取り出すのが shift で、末尾から一個取り出すのが pop で、
配列に要素を追加するメソッドには << と push がある
配列をくっつけるときは、配列同士を + で結べばよい
join メソッドって何だっけ?
それは、配列の全要素を文字列に直したものを並べて、それぞれの間に区切り文字列を挟んでつなげた文字列を返すメソッド

上記の「ことば」で定義した qsort メソッドを Rubyプログラムに直そう。

def qsort(data)		# 配列を受け取る

  if data.length <= 1	# データが1個以下なら
    data		# そのものを返して並べ換え完了
  else
    left = Array.new	# left(左側配列)を新規作成
    right = Array.new 	# right(右側配列)を新規作成
    k = data.shift	# 変数dataの先頭を取り出してkにする

    for x in data	# 残ったdata全てに対して繰り返す
      if x < k 	   	# kより小さかったら
         left << x	# 左側に追加
      else
         right << x	# 右側に追加
      end
    end			# 繰り返し終わり

    # qsort(left)の末尾にkを足し、さらにqsort(right)を結合
    qsort(left).push(k) + qsort(right)
  end
end

この qsort メソッドを使って、並べ換えできるか確認しよう。そのために、配列を読み込んだり、画面に表示したりするメソッドを作っておこう。

【配列を読み込むメソッド】

標準入力から順次数値を読み取り配列にするメソッド

def readNumArray()
  ary = []
  while line=gets		# 入力が続く間
    datum = line.chomp!.to_i	# 整数に直して
    ary.push(datum)		# aryに追加していく
  end
  ary				# 最後にaryを呼び主に返す
end

【配列を画面表示するメソッド】
配列を受け取り、各要素をカンマで区切って表示する。これには join が利用できる。
```
def printArray(a)
  printf("[%s]\n", a.join(", "))
end
```

これらのメソッドを組み合わせて、プログラムは完成する。

qsort.rb

#!/usr/koeki/bin/ruby
# coding: utf-8

def qsort(data)		# 配列を受け取る

  if data.length <= 1	# データが1個以下なら
    data		# そのものを返して並べ換え完了
  else
    left = Array.new	# left(左側配列)を新規作成
    right = Array.new 	# right(右側配列)を新規作成
    k = data.shift	# 変数dataの先頭を取り出してkにする

    for x in data	# 残ったdata全てに対して繰り返す
      if x < k 	   	# kより小さかったら
         left << x	# 左側に追加
      else
         right << x	# 右側に追加
      end
    end			# 繰り返し終わり

    # qsort(left)の末尾にkを足し、さらにqsort(right)を結合
    qsort(left).push(k) + qsort(right)
  end
end

def readNumArray()
  ary = []
  while line=gets		# 入力が続く間
    datum = line.chomp!.to_i	# 整数に直して
    ary.push(datum)		# aryに追加していく
  end
  ary				# 最後にaryを呼び主に返す
end

def printArray(a)
  printf("[%s]\n", a.join(", "))
end

ary = readNumArray()

puts "整列前:"
printArray(ary)
puts "整列後:"
printArray(qsort(ary))

上記のプログラム、qsort.rb を保存して実行し、1行に1つずつデータを入れて小さい順に並べ換えできることを確認せよ。

実行例:

% ./qsort.rb
45
58
5
9
45
20
[C-d]

※問題※

qsortメソッドを書き変えて、数値の大きい順に並べ換えるようにせよ。実際に実行してそれを確かめよ。

本日の目次へ