ホーム » 「マージソート」タグがついた投稿

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

2019年8月
« 7月    
 123
45678910
11121314151617
18192021222324
25262728293031

最近の投稿(電子情報)

アーカイブ

カテゴリー

ソートアルゴリズム

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

様々なソートアルゴリズム

データの有名な並び替えアルゴリズムとその処理時間のオーダーを示す。

  • バブルソート O(N2)
  • 選択法 O(N2/2)
  • クイックソート O( N log N )
  • マージソート O( N log N )

マージソートの分析

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

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。






よって、

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

  1. データ件数 = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

JavaScriptでマージソート

配列のマージソートを、難しいテクニックを使わないスタンダードな書き方でのサンプル。

function merge_sort( a , start , end ) {
   if ( start + 1 == end ) {
      // a[start]の1件だけなので並び替える必用なし
   } else {
      // 真ん中
      var mid = Math.floor( (start + end) / 2 ) ;
      // 左半分を並べ替え
      merge_sort( a , start , mid ) ;
      // 右半分を並べ替え
      merge_sort( a , mid , end ) ;

      // 2つの山をマージする。
      var temp = new Array() ;          // マージ結果の一時的保存用
      var lt = start ;                  // 左の山の先頭
      var rt = mid ;                    // 右の山の先頭
      // ここがまだダサい。
      for( i = 0 ; i < end - start ; i++ ) {
         var w ;
         if ( lt >= mid ) {        // 左の山が空、右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         } else if ( rt >= end ) { // 右の山が空、左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else if ( a[lt] > a[rt] ) {  // 左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else {                       // 右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         }
         temp[ i ] = w ;
      }
      // マージした結果を、a[]のstart..endに戻す
      for( var i = 0 ; i < end - start ; i++ ) {
         a[ start + i ] = temp[ i ] ;
         console.log( "a["+(start+i)+"]="+a[start+i]) ;
      }
   }
}

array = new Array( 11 , 45 , 22 , 33 , 77 , 88 , 44 , 55 ) ;
merge_sort( array , 0 , array.length ) ;
for( var i = 0 ; i < array.length ; i++ )
   console.log( "a["+i+"]=" + array[i] ) ;

マージソートのオーダー

マージソートの分析

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

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。






よって、

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

  1. データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。