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

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

JavaScriptによるプログラム例

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

  // (再帰処理の代わりに)分割の両端をスタックで管理する
  var size = 
    Math.floor(Math.LOG2E * Math.log(array.length)) + 1;
  var lStack = new Array(size);
  var rStack = new Array(size);
  var p;  // スタックポインタ

  // スタックの初期化
  lStack[0] = 0;
  rStack[0] = array.length - 1;
  p = 1;

  // スタックが空になるまでループする
  while(p > 0) {
    // スタックから取り出す
    p--;
    left = lStack[p];
    right = rStack[p];

    // 分割の幅が1以下になるまでループ
    while (left < right) {
      // 中央の要素をpivotに設定
      var r = Math.floor( (left + right) / 2 ); 
      var pivot = array[r];
      // i, jをそれぞれ左端、右端に設定
      var i = left;
      var j = right;
      // pivotより小さい要素を左に、大きい要素を右に集める
      while (1) {
        // iを右へ進める
        while(cmpfunc(array[i], pivot) < 0) i++;
        // jを左へ進める
        while(cmpfunc(pivot, array[j]) < 0) j--;
        // i, jが交差したらループを抜ける
        if(j <= i) break;
        // 要素の交換
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        // i, jを進める
        i++; j--;
      }

      // 配列を2分割。スタック節約のため、
      // 分割幅の長い方をスタックに積み、
      // 分割幅の短い方から先に処理する。
      // j <= pivotを値にもつ要素に対応する添字 <= i
      if (i - left < right - j) {
        if (left < i) {
          /* 右側を積む */
          lStack[p] = i;
          rStack[p] = right;
          p++;
        }
        right = i - 1;
      }
      else {
        if (j < right) {
          /* 左側を積む */
          lStack[p] = left;
          rStack[p] = j;
          p++;
        }
        left = j + 1;
      } 
    }
  }
}

// 比較関数
// 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 自身を書き換える
nonRecursiveQuickSort(array, cmp);

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

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

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

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

/* クイックソート(非再帰版)
   第1引数:配列
   第2引数:配列の大きさ
   第3引数:比較関数 */
void nonRecursiveQuickSort(
  DATA array[], 
  int array_length, 
  int (*cmpfunc)(DATA, DATA)) 
{
  int *lStack, *rStack;
  int size, p, left, right, r, iPos, jPos;
  DATA pivot, temp;
  register DATA *i, *j;

  /* (再帰処理の代わりに)分割の両端をスタックで管理する */
  size = (int)(M_LOG2E * log((double) array_length)) + 1;
  lStack = (int*)malloc(sizeof(int) * size);
  if (lStack == NULL) {
    printf("Can't reallocate memory. 'lStack' is NULL.\n");
    exit(1);  
  }
  rStack = (int*)malloc(sizeof(int) * size);
  if (rStack == NULL) {
    printf("Can't reallocate memory. 'rStack' is NULL.\n");
    exit(1);  
  }

  /* スタックの初期化 */
  lStack[0] = 0;
  rStack[0] = array_length - 1;
  p = 1;

  /* スタックが空になるまでループする */
  while (p > 0) {
    /* スタックから取り出す */
    p--;
    left = lStack[p];
    right = rStack[p];

    /* 分割の幅が1以下になるまでループ */
    while (left < right) {
      /* 中央の要素をpivotに設定 */
      r = (left + right) / 2; 
      pivot = array[r];
      /* i, jをそれぞれ左端、右端に設定 */
      i = &array[left];
      j = &array[right];
      iPos = left; jPos = right;
      /* pivotより小さい要素を左に、大きい要素を右に集める */
      while (1) {
        /* iを右へ進める */
        while ((*cmpfunc)(*i, pivot) < 0){
          i++; iPos++;
        }
        /* jを左へ進める */
        while ((*cmpfunc)(pivot, *j) < 0){
          j--; jPos--;
        }
        /* iPos, jPosが交差したらループを抜ける */
        if(jPos <= iPos) break;
        /* 要素の交換 */
        temp = *i; *i = *j; *j = temp;
        /* i, jを進める */
        i++; iPos++;
        j--; jPos--;
      }

      /* 配列を2分割。スタック節約のため、
         分割幅の長い方をスタックに積み、
         分割幅の短い方から先に処理する。 */
      /* jPos <= pivotを値にもつ要素に対応する添字 <= iPos */
      if (iPos - left < right - jPos) {
        if (left < iPos) {
          /* 右側を積む */
          lStack[p] = iPos;
          rStack[p] = right;
          p++;
        }
        right = iPos - 1;
      }
      else {
        if (jPos < right) {
          /* 左側を積む */
          lStack[p] = left;
          rStack[p] = jPos;
          p++;
        }
        left = jPos + 1;
      } 
    }
  }
  /* 動的メモリの解放 */
  free(lStack); lStack = NULL;
  free(rStack); rStack = 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 自身を書き換える */
  nonRecursiveQuickSort(array, array_length, *cmp);

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

  return 0;
}

参考文献

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

関連記事

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

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

プロフィール

よしいず

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

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

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

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

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

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示