いろいろなソート(サンプル付き)

Pocket

ソートのアルゴリズムについて調べました。
代表的なソート方法5種類について概略をまとめます。
n個の要素を持つ配列を昇順(小さい数から大きい数)にソートする場合です。

バブルソート

1番目の要素と2番目の要素を比較。大小が逆ならば要素を入れ替える。続いて1番目と3番目を比較。これを1番目とn番目まで繰り返すと最初の要素が最小になる。
次に2番目と3番目を比較、2番目と4番目を比較、2番目とn番目を比較。これを繰り返すと2番目の要素が2番目に小さい数となる。
これをn-1番目とn番目の比較まで繰り返す。

挿入ソート

2番目の要素と1番目の要素を比較。大小が逆ならば要素を入れ替える。
次に3番目と2番目を比較。大小が逆ならば要素を入れ替える。逆でなければ3番目と1番目を比較。大小が逆ならば3番目を1番目の要素に入れ、1番目を2番目、2番目を3番目に順次入れる。
これをn番目とn-1番目の比較まで繰り返す。

選択ソート

n個の要素を片端から全て調べ最小の要素を取り除く。この要素を別の配列の1番目の要素に入れる。元の配列の要素はn-1個になる。
残ったn-1個の要素を全て調べ最小の要素を取り除く。この要素を別の配列の2番目の要素に入れる。元の配列の要素はn-2個になる。
これをn回繰り返す。

マージソート

配列の要素が1個の場合はその配列を返す。
配列の要素が2個以上の場合は配列を前半と後半に2等分する(奇数の場合は中央の要素をどちらかに含める)。
前半の配列をマージソートする。
後半の配列をマージソートする。
前半と後半の配列をマージする。
配列のマージを参照。

クイックソート

配列の要素が1個の場合はその配列を返す。
配列の要素が2個以上の場合は最後の要素を取り除き、この要素を「ピボット」として記憶しておく。
別の配列を二つ用意する。
全ての要素をピボットと比較し、小さければ前半の配列に順次入れる。そうでなければ後半の配列に順次入れる。
前半の配列をクイックソートする。
後半の配列をクイックソートする。
前半の配列、ピボット、後半の配列の順でつなげる。

マージソートとクイックソートは「再帰」という手法を使うので分かりにくいかもしれません。

どのアルゴリズムも結果は同じになりますので、ポイントはスピードです。
1000個のランダムな数をソートした場合にかかる時間についてまとめました。
コードはJavaScriptで書きました。後で示します。

種類 時間
バブルソート 100
マージソート 77
挿入ソート 65
選択ソート 57
クイックソート 20

バブルソートを100として比較しています。数値が少ないほど速いです。
最も遅いと言われているのがバブルソートで、速いと言われているのがクイックソート。その通りの結果になりました。
予想外なのはマージソートの遅さです。私のコーディングがまずいのかもしれません。

function bubblesort(a) {
  var num, i, j, temp;
  num = a.length;
  for (i = 0; i < num - 1; i++) {
    for (j = i + 1; j < num; j++) {
      if (a[i] > a[j]) {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
    }
  }
  return (a);
}
function insertsort(a) {
  var num, i, j, temp;
  num = a.length;
  for (i = 1; i <= num; i++) {
    temp = a[i];
    if (temp < a[i - 1]) {
      j = i;
      while (temp < a[j - 1] && j > 0) {
        a[j] = a[j - 1];
        j--;
      }
      a[j] = temp;
    }
  }
  return (a);
}
function selectionsort(a) {
  var num, i, j, k;
  var min, temp;
  num = a.length;
  for (i = 0; i < num; i++) {
    min = a[i];
    k = i;
    for (j = i + 1; j < num; j++) {
      if (a[j] < min) {
        min = a[j];
        k = j;
      }
    }
    temp = a[i];
    a[i] = a[k];
    a[k] = temp;
  }
  return (a);
}
function quicksort(a) {
  var num, i;
  var pivot, temp;
  var x = new Array();
  var y = new Array();
  num = a.length;
  if (num <= 1) {
    return (a);
  } else {
    pivot = a[num - 1];
    for (i = 0; i < num - 1; i++) {
      if (a[i] < pivot) {
        x.push(a[i]);
      } else {
        y.push(a[i]);
      }
    }
    x = quicksort(x);
    x.push(pivot);
    return (x.concat(quicksort(y)));
  }
}
function mergesort(a) {
  var num, k;
  var c = new Array();
  var x = new Array();
  var y = new Array();
  num = a.length;
  if (num <= 1) {
    return (a);
  } else {
    k = Math.floor(num / 2);
    x = a.slice(0, k);
    y = a.slice(k, num);
    x = mergesort(x);
    y = mergesort(y);
    while (x.length > 0 && y.length > 0) {
      if (x[0] < y[0]) {
        c.push(x.shift());
      } else {
        c.push(y.shift());
      }
    }
    return (c.concat(x).concat(y));
  }
}

[ 2011年12月9日 | カテゴリー: JavaScript | タグ: , ]

« | »

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報