タグアーカイブ: マージソート

再帰呼び出しと再帰方程式

前回の授業では、簡単な再帰呼び出しのプログラムについて再帰方程式などの説明を行った。今日の授業では、ハノイの塔の処理時間や、マージソートのプログラムの処理時間について検討を行う。ハノイの塔ハノイの塔は、３本の塔にN枚 […]

前回の授業のハノイの塔は、単純な再帰方程式で処理時間のオーダーが巨大となる一例として示した。そこで、プログラムの中でよく利用されるデータの並び替え(ソート)で処理時間の分析を行ってみる。ポインタについての説明は、前回の […]

配列のマージソートを、難しいテクニックを使わないスタンダードな書き方でのサンプル。 function merge_sort( a , start , end ) { if ( start + 1 == end ) { / […]

マージソートの分析マージソートは、与えられたデータを2分割し、その2つの山をそれぞれマージソートを行う。この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、ソートを行う。こ […]