※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

とある秤人がたくさんある石を天秤ばかりで軽い順に並べようとしている。
天秤ばかりだから大小関係しかわからない。
彼は記憶力が悪いので他ではかった時の結果は思い出せない。
どうはかっていけばよいだろうか?

その方法は次のとおりである。
石の山の中から石を一つ適当に選ぶ。
その石より重いか同じ重さのものを右に、その石より軽いものを左に分け、最後に基準とした石を二つの山の中央に置きこの石を中央0とする。

すると左は中央の石より軽いものしかなく、右は同じかより重いものしかない。
この時左の石の山に右より重い石は一つもない。

次に左だけに注目して同じ操作をしできた山を左-1、中央-1、右-1とする。
右でも同様の操作をし左1、中央1,右1の石の山を作る。
すると左-1<中央-1=<右-1<中央0=<左1<中央1<=右1という大小関係が生まれる。
左-1、右-1、左1、右1でさらに同様の操作を続けてわけていくと最後は全ての山で石が1つか全くない状態が生まれる。

この状態になったら全ての石は左から右へ向かって軽い順に並んでいる。
後は結合していくだけである。

この方法は11世紀のイスラム数学者
カクー・ノジ・ンブツ氏の書物に記載されているとおりである。

























架空の人物=カクー・ノジ・ンブツと小学生でもわかるネタである。
つまりこの記事はクイックソートのジョークバージョン。
作者 堀江伸一