いろいろなソート(サンプル付き)
ソートのアルゴリズムについて調べました。
代表的なソート方法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として比較しています。数値が少ないほど速いです。
最も遅いと言われているのがバブルソートで、速いと言われているのがクイックソート。その通りの結果になりました。
予想外なのはマージソートの遅さです。私のコーディングがまずいのかもしれません。
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);
}
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);
}
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);
}
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)));
}
}
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 | タグ: sort , アルゴリズム ]
« 罫線の下端で改ページするマクロ | おかしなうまい棒スティックパーティー »
コメントを残す