スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

非再帰版マージソートのプログラム例

JavaScriptとC言語によるプログラム例。

JavaScriptによるプログラム例

<html>
<head>
<title>Non-Recursive Merge Sort</title>
</head>
<body>
<script type="text/javascript">
<!--
// マージソート(非再帰版)
// 第1引数:配列
// 第2引数:比較関数
function nonRecursiveMergeSort(array, cmpfunc) {

  // マージ作業用の配列(左側の部分列用)
  var leftSubAry = new Array(array.length);

  // 配列を分割したときの部分列の幅
  var subAryLength = 1;

  // 与えられた配列を 2*subAryLength の幅に分割し、
  // 二つの部分列に分けてマージする
  while(subAryLength <= array.length) {
    var last = Math.floor(array.length / (subAryLength * 2)) + 1;
    var rem = array.length % (subAryLength * 2);
    var pos = 0;
    for(var i = 1; i <= last; i++) {
      var lLength, rLength;
      // 末尾のとき
      if(i == last) {
        if(rem > subAryLength) {
          lLength = subAryLength;
          rLength = rem - subAryLength;
        }
        else {
          lLength = rem;
          rLength = 0;  // 末尾はマージ済み
        }
      }
      // 末尾以外のとき
      else {
        lLength = subAryLength;
        rLength = subAryLength;
      }

      // 左側の部分列を作業用配列にコピー
      // k = pos, ..., pos + lLength - 1
      for(var j = 0, k = pos; j < lLength; j++, k++)
        leftSubAry[j] = array[k];

      // 右側の部分列の先頭と終端
      var rHead = pos + lLength;
      var rTail = pos + lLength + rLength;

      // 各々の要素を先頭から取り出して比較する
      // 左右どちらかの部分列が空になるまで繰り返す
      var j = 0, rPos = rHead; 
      while(j < lLength && rPos < rTail) {
        // 1. 小さいほうの値を優先 (昇順に整列)
        // 2. 両方の値が等しければ左側を優先 (位置関係を保つ)
        if(cmpfunc(leftSubAry[j], array[rPos]) <= 0)
          array[pos++] = leftSubAry[j++];
        else
          array[pos++] = array[rPos++];  // 常に pos <= rPos
      }

      // 余った要素を追加する
      // この時点で左右どちらかの部分列は空なので、
      // 以下の2つのループのうち片方は実行されない
       while (j < lLength)
        array[pos++] = leftSubAry[j++];
       while (rPos < rTail)
        array[pos++] = array[rPos++];
    }

    // 部分列の幅を倍にする
    subAryLength *= 2;
  }
}

// 比較関数
// a と b とが等しい:0
// a が b より小さい:負の値
// a が b より大きい:正の値
function cmp(a, b) {
  if (a == b) {
    return 0;
  }
  else {
    return (a < b) ? -1 : 1;
  }
}

// 配列の内容を表示
function display(array) {
  document.open();
  for (var i = 0; i < array.length; i++) {
    document.write(array[i] + '<br>');
  }
  document.write('<br>');
  document.close();
}

// =====================================

// 配列
var n = 10;
var bound = 20; 
var array = new Array(n);
for(var i = 0; i < n; i++){
  array[i] = Math.floor(Math.random() * bound);
}

// ソート前
display(array);

// ソート実行
// array 自身を書き換える
nonRecursiveMergeSort(array, cmp);

// ソート後
display(array);
//-->
</script>
</body>
</html>

C言語によるプログラム例

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 配列のデータ型を強調するために導入 */
typedef int DATA; 

/* マージソート(非再帰版)
   第1引数:配列
   第2引数:配列の大きさ
   第3引数:比較関数 */
void nonRecursiveMergeSort(
  DATA array[], 
  int array_length, 
  int (*cmpfunc)(DATA, DATA)) 
{
  DATA *leftSubAry;
  register DATA *pa, *pl, *pr;
  int subAryLength, last, rem, lLength, rLength;
  int i, j, pos, rPos, rHead, rTail; 

  /* マージ作業用の配列(左側の部分列用) */
  leftSubAry = (DATA*)malloc(sizeof(DATA) * array_length);
  if (leftSubAry == NULL) {
    printf("Can't reallocate memory. 'leftSubAry' is NULL.\n");
    exit(1);  
  }
  /* 配列を分割したときの部分列の幅 */
  subAryLength = 1;

  /* 与えられた配列を 2*subAryLength の幅に分割し、
     二つの部分列に分けてマージする */
  while(subAryLength <= array_length) {
    last = array_length / (subAryLength << 1) + 1;
    rem = array_length % (subAryLength << 1);
    pos = 0;
    for(i = 1; i <= last; i++) {
      /* 末尾のとき */
      if(i == last) {
        if(rem > subAryLength) {
          lLength = subAryLength;
          rLength = rem - subAryLength;
        }
        else {
          lLength = rem;
          rLength = 0;  /* 末尾はマージ済み */
        }
      }
      /* 末尾以外のとき */
      else {
        lLength = subAryLength;
        rLength = subAryLength;
      }

      /* 左側の部分列を作業用配列にコピー
         array[pos], ..., array[pos + lLength - 1] */
      pa = &array[pos];
      pl = &leftSubAry[0]; 
      for(j = 0; j < lLength; j++) *pl++ = *pa++;
      /* 右側の部分列の先頭と終端 */
      rHead = pos + lLength;
      rTail = pos + lLength + rLength;

      /* 各々の要素を先頭から取り出して比較する。
         左右どちらかの部分列が空になるまで繰り返す */
      pa = &array[pos];
      pl = &leftSubAry[0]; 
      pr = &array[rHead];
      j = 0; rPos = rHead;
      while(j < lLength && rPos < rTail) {
        /* 1. 小さいほうの値を優先 (昇順に整列)
           2. 両方の値が等しければ左側を優先 (位置関係を保つ) */
        if((*cmpfunc)(*pl, *pr) <= 0) {
          *pa++ = *pl++; 
          pos++; j++;
        }
        else {
          *pa++ = *pr++;
          pos++; rPos++;  /*  常に pos <= rPos */
        }
      }

      /* 余った要素を追加する。
         この時点で左右どちらかの部分列は空なので、
         以下の2つのループのうち片方は実行されない */
       while(j < lLength) {
        *pa++ = *pl++; 
        pos++; j++;
      }
       while(rPos < rTail) {
        *pa++ = *pr++; 
        pos++; rPos++;
      }
      /* この時点で pos = rTail */
    }

    /* 部分列の幅を倍にする */
    subAryLength <<= 1;
  }

  /* 動的メモリの解放 */
  free(leftSubAry); leftSubAry = NULL;
}

/* 比較関数
   a と b とが等しい:0
   a が b より小さい:負の値
   a が b より大きい:正の値 */
int cmp(DATA a, DATA b) {
  return a - b;
}

/* 配列の内容を表示 */
void display(DATA array[], int array_length)
{
  int i; 

  for (i = 0; i < array_length; i++) {
    printf("%d\n", array[i]);
  }
  printf("\n");
}

/* ===================================== */

int main(void)
{
  DATA array[10];
  int bound = 20;
  int array_length = sizeof(array) / sizeof(array[0]);
  int i;

  /* 配列の生成 */
  srand((unsigned)time(NULL));
  for (i = 0; i < array_length; i++) {
    array[i] = rand() % bound;
  }  

  /* ソート前 */
  display(array, array_length);

  /* ソート実行 */
  /* array 自身を書き換える */
  nonRecursiveMergeSort(array, array_length, *cmp);

  /* ソート後 */
  display(array, array_length);

  return 0;
}

参考文献

  • 奥村晴彦:C言語による最新アルゴリズム事典, 技術評論社, 1991. pp.267-268
  • 近藤嘉雪:定本Cプログラマのためのアルゴリズムとデータ構造, ソフトバンク, 1998. pp.217-232

関連記事

非再帰版クイックソートのプログラム例

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。