JS ソート・アルゴリズム トップ10

• 。

コード

/*
 *  :
 * ARRAY_LENGTH: 配列の長さ
 * ARRAY_MIN: 配列要素の最小値
 * ARRAY_MAX: 配列要素の最大値
 * SORT_METHODS: 使用されるソート方法
 * |-- bubbleSort: バブルソート
 * |-- quickSort: クイックソート
 * |-- insertionSort: 挿入ソート
 * |-- shellSort: ヒルソート
 * |-- selectSort: 選択ソート
 * |-- heapSort:  
 * |-- mergeSort: 合計ソート
 * |-- countingSort: カウントソート
 * |-- bucketSort:  
 * |-- radixSort: ベースソート
 * SHOW_ORIGIN: 元配列を出力するかどうか
 * SHOW_RESULTS: ソート結果を出力するかどうか
 * SHOW_TIMES: 出力ソートに時間がかかるかどうか
 */
const ARRAY_LENGTH = 10000;
const ARRAY_MIN = 0;
const ARRAY_MAX = 10000;
const SORT_METHODS = [
 bubbleSort,
 selectSort,
 insertionSort,
 shellSort,
 mergeSort,
 quickSort,
 heapSort,
 countingSort,
 bucketSort,
 radixSort,
];
const SHOW_ORIGIN = true;
const SHOW_RESULTS = true;
const SHOW_TIMES = true;
/*
 * メイン関数：各ソートを実行し、その経過時間とソート結果を出力する。
 */
(function main() {
 // 設定をインポートし、ソート用のランダム配列を作成する。
 const arr = buildArray(
 ARRAY_LENGTH,
 generateRandInteger(ARRAY_MIN, ARRAY_MAX)
 );
 // 出力を保持するためにretsを定義する
 let rets = {
 origin: arr,
 result: null,
 times: [],
 };
 // 出力元配列
 if (SHOW_ORIGIN) {
 console.log("origin:", rets.origin);
 }
 // 各ソートの実行
 for (let sortMethod of SORT_METHODS) {
 // ソートを実行し、経過時間を計算する。
 const timeBegin = process.uptime(),
 sortResult = sortMethod([...arr]),
 timeEnd = process.uptime();
 // 店舗ソートには時間がかかる
 rets.times.push({
 method: sortMethod.name,
 time: (timeEnd - timeBegin) * 1000,
 });
 // ソートの結果を保存する
 if (rets.result === null) {
 rets.result = sortResult;
 }
 }
 if (SHOW_RESULTS) {
 console.log("result:", rets.result);
 }
 if (SHOW_TIMES) {
 rets.times.sort((a, b) => {
 return a.time - b.time;
 });
 console.log("<<SortMethod>>", "	", "<<TimeCost>>");
 for (let time of rets.times) {
 console.log(time.method, "	", time.time.toFixed(3), "ms");
 }
 }
})();
/*
 * 指定された長さの配列を構築して返す
 * @params length {Number} 配列の長さ
 * @params element {Number|Function} 配列要素または配列要素を生成する関数
 */
function buildArray(length, element) {
 let arr = [];
 while (arr.length < length) {
 let ele = typeof element === "function" ? element() : element;
 arr.push(ele);
 }
 return arr;
}
/*
 * 指定された範囲のランダムな整数を生成して返す。
 * @params min {Number} 最小
 * @params max {Number}  
 */
function generateRandInteger(min, max) {
 return function () {
 return Math.floor((max - min + 1) * Math.random() + min);
 };
}
/*
 * 空白の配列を生成して返す
 */
function generateBlankArray() {
 return function () {
 return [];
 };
}
// バブルソート
// 時間の複雑さ：O(n^2)
// 空間の複雑さ：O
// 安定性：安定
function bubbleSort(arr) {
 // 配列の長さを取得する
 const len = arr.length;
 // 各ラウンドのスキャンの後、最大要素が決定される。，
 // を右端に配置するため、合計len-1回のスキャンが必要となる。
 for (let i = 0; i < len - 1; i++) {
 // 左から右へスキャンして決定する[0,len-i)範囲内の最大の要素，
 // で、添え字len-i-1（範囲の右端）に置かれる。
 for (let j = 0; j < len - i - 1; j++) {
 // 現在の要素が次の要素より大きい場合、両者は交換される。，
 // この方法では、大きな要素は右側に配置される。
 if (arr[j] > arr[j + 1]) {
 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
 }
 }
 }
 return arr;
}
// 選択ソート
// 時間の複雑さ：O(n^2)
// 空間の複雑さ：O
// 安定性：不安定
function selectSort(arr) {
 // 配列の長さを取得する
 const len = arr.length;
 // 最小要素の添え字を宣言する
 let minIdx;
 // 各ラウンドのスキャンの後、最小要素が決定される。，
 // で、それを左端に置くので、合計len-1回のスキャンが必要である。
 for (let i = 0; i < len - 1; i++) {
 // まず、minIdxをiに設定する。
 minIdx = i;
 // 左から右へスキャンして決定する[i,len)範囲内の最小要素
 for (let j = i + 1; j < len; j++) {
 // 現在の要素がarr[minIdx]，次にminIdxをリセットする。
 if (arr[j] < arr[minIdx]) {
 minIdx = j;
 }
 }
 // スキャンの最後に、arrをスワップする。[i]とarr[minIdx]
 [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
 }
 return arr;
}
// 挿入ソート
// 時間の複雑さ：O(n^2)
// 空間の複雑さ：O
// 安定性：安定
function insertionSort(arr) {
 // 配列の長さを取得する
 const len = arr.length;
 // 第kラウンドのスキャンの後、次のことを決定することができる。[0,k]範囲内の要素の順序，
 // したがって、合計len-1回のスキャンが必要となる
 for (let i = 1; i < len; i++) {
 // 右から左へスキャンして[i]を持つ要素である。，
 // もしarr[i]比較される要素より小さい場合は交換され、そうでない場合はスキャンが終了する。
 for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
 [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
 }
 }
 return arr;
}
// ヒルソート
// 時間の複雑さ：O
// 空間の複雑さ：O
// 安定性：不安定
function shellSort(arr) {
 // 配列の長さを取得する
 const len = arr.length;
 // グループ距離ギャップをlenの半分と定義する。，
 // ギャップに基づいてグループ化し、挿入ソートを使ってグループをソートする，
 // グループ間隔は0になるまで半減し続ける。
 for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
 for (let i = gap; i < len; i++) {
 for (let j = i; j > 0 && arr[j - gap] > arr[j]; j -= gap) {
 [arr[j - gap], arr[j]] = [arr[j], arr[j - gap]];
 }
 }
 }
 return arr;
}
// 合計ソート
// 時間の複雑さ：O
// 空間の複雑さ：O
// 安定性：安定
function mergeSort(arr) {
 // 配列の長さを取得する
 const len = arr.length;
 // 配列の長さが1以下であれば、ソートは必要なく、arrを返すだけでよい。
 if (len <= 1) return arr;
 // ピボット、ミドル、レフト、ライトの定義，
 // pivotは中間の添え字で、middle は中間の要素である。，
 // leftとrightは、それぞれmiddleより小さい要素とmiddleより大きい要素を格納するのに使われる
 const pivot = Math.floor(len / 2),
 middle = arr[pivot];
 let left = [],
 right = [];
 // 左から右へスキャンすると、左か右に要素が配置される。
 for (let i = 0; i < len; i++) {
 // 現在の要素がmiddleより小さい場合はleftに格納される；
 // それ以外の場合は、RIGHTに格納される。
 if (i !== pivot) {
 if (arr[i] < middle) left.push(arr[i]);
 else right.push(arr[i]);
 }
 }
 // 結合のための再帰
 return [...mergeSort(left), middle, ...mergeSort(right)];
}
// クイックソート
// 時間の複雑さ：O
// 空間の複雑さ：O
// 安定性：不安定
function quickSort(arr) {
 // 配列の長さを取得する
 const len = arr.length;
 // 関数subSortを宣言する，
 // この機能は[left,right]範囲内の要素をソートする
 function subSort(left, right) {
 // leftを添え字として定義する。，
 // 対応する要素はベース要素である
 let pivot = left;
 // ソートは、右が左より大きい場合に必要である。
 if (right > left) {
 // 左から右へスキャンする，
 // 基本要素より小さい要素はその左に置かれる；
 // 基本要素より大きい要素をその右に置く
 for (let i = left + 1; i <= right; i++) {
 // 現在の要素がベース要素より小さい場合、スワップ操作が実行される。
 if (arr[i] < arr[pivot]) {
 // 現在の要素を小さい方の要素と呼ぶ，
 // 小さい方の要素とベース要素の右側の要素を交換する
 [arr[i], arr[pivot + 1]] = [arr[pivot + 1], arr[i]];
 // ベースと小さい要素を入れ替える
 [arr[pivot], arr[pivot + 1]] = [arr[pivot + 1], arr[pivot]];
 // 基本添え字プラス1
 pivot++;
 // パスが終わると、小さい方の要素がベース要素の左側に置かれる。
 }
 }
 //  [left,pivot-1] [pivot+1,right]範囲内の要素をソートする
 subSort(left, pivot - 1);
 subSort(pivot + 1, right);
 }
 }
 //  [0,len-1]範囲内の要素をソートする
 subSort(0, len - 1);
 return arr;
}
//  
// 時間の複雑さ：O
// 空間の複雑さ：O
// 安定性：不安定
function heapSort(arr) {
 // 配列の長さを取得する
 let len = arr.length;
 //  
 function heapify(i) {
 // 最大値を定義する。，
 // 最大要素の添え字を表すのに使われる
 let largest = i;
 // 左と右の定義，
 // それぞれ左ノードと右ノードの添え字を表すのに使われる
 const left = 2 * i + 1,
 right = 2 * i + 2;
 // 左ノードの添え字が[0,len) ，
 // また[left]arrより大きい[largest]，
 // 次にlargetをleftにセットする。
 if (left < len && arr[left] > arr[largest]) {
 largest = left;
 }
 // 同様に[right]判断する
 if (right < len && arr[right] > arr[largest]) {
 largest = right;
 }
 // 最大値がリセットされている場合，
 // 次に、交換arr[largest]とarr[i]，
 // 子ノードを調整する
 if (largest !== i) {
 [arr[largest], arr[i]] = [arr[i], arr[largest]];
 heapify(largest);
 }
 }
 // ビッグトップ・ヒープを構築する
 for (let i = Math.floor(len / 2); i >= 0; i--) {
 heapify(i);
 }
 // ヒープの上下の要素を入れ替え、下の要素が最大になるようにし、ヒープを調整する。，
 // これをスワップと調整を繰り返しながら、大きなトップヒープが順序付き配列になるまで続ける。
 for (let i = len - 1; i > 0; i--) {
 [arr[i], arr[0]] = [arr[0], arr[i]];
 len--;
 heapify(0);
 }
 return arr;
}
// カウントソート
// 時間の複雑さ：O(n+k)
// 空間の複雑さ：O
// 安定性：安定
function countingSort(arr) {
 // 配列の長さと最大要素を取得し、バケットを初期化する。
 const len = arr.length,
 max = Math.max(...arr),
 bucket = buildArray(max + 1, 0);
 // 左から右へスキャンして数える
 for (let i = 0; i < len; i++) {
 bucket[arr[i]]++;
 }
 // バケットからカウントを取り除き、「広げる」。”
 let idx = 0;
 for (let j = 0; j <= max; j++) {
 while (bucket[j] > 0) {
 arr[idx++] = j;
 bucket[j]--;
 }
 }
 return arr;
}
//  
// 時間の複雑さ：O(n+k)
// 空間の複雑さ：O(n+k)
// 安定性：安定
function bucketSort(arr) {
 // 配列の長さ、最小値、最大値を取得する，
 // バケツのサイズに基づいてバケツの数を決定し、バケツを初期化する。
 const len = arr.length,
 min = Math.min(...arr),
 max = Math.max(...arr),
 bucketSize = 10,
 bucketCount = Math.floor((max - min) / bucketSize) + 1,
 buckets = buildArray(bucketCount, generateBlankArray());
 // 左から右へスキャンして要素を対応するバケットに収める
 for (let i = 0; i < len; i++) {
 const idx = Math.floor((arr[i] - min) / bucketSize);
 buckets[idx].push(arr[i]);
 }
 // 挿入ソートを使って、各バケツの要素をソートする
 for (let j = 0; j < bucketCount; j++) {
 insertionSort(buckets[j]);
 }
 // バケツの要素を取り除いて「広げる」。”
 return buckets.flat(2);
}
// ベースソート
// 時間の複雑さ：O
// 空間の複雑さ：O(n+k)
// 安定性：安定
function radixSort(arr) {
 // 配列の長さ、最大の要素を取得する
 const len = arr.length,
 max = Math.max(...arr);
 // 最大要素の桁数を取得する
 let maxDigit = 1;
 while (max / 10 ** maxDigit >= 1) {
 maxDigit += 1;
 }
 // ラウンド1は桁をソートし、ラウンド2は10をソートする。
 for (let digit = 1; digit <= maxDigit; digit++) {
 // 余りと除数の設定とバケツの初期化
 const mod = 10 ** digit,
 dev = mod / 10,
 buckets = buildArray(10, generateBlankArray());
 // 左から右へスキャンして要素を対応するバケットに収める
 for (let i = 0; i < len; i++) {
 let idx = Math.floor((arr[i] % mod) / dev);
 buckets[idx].push(arr[i]);
 }
 // バケットから要素を取り除き、「広げる」。”
 arr = buckets.flat(2);
 }
 return arr;
}

テスト

新しいsorts.jsファイルを作成し、前のセクションのコードをコピーします。フォルダに入り、コマンドを実行します：

node sorts.js

コマンドラインターミナルは、ソート元の配列、ソート結果、ソートごとの経過時間を出力します：

origin: [
 2818, 8155, 2632, 9331, 7831, 679, 8924, 178, 7742, 9688,
 3590, 4475, 373, 3064, 5473, 3804, 6301, 9160, 5081, 5041,
 4484, 617, 3087, 1000, 4451, 8463, 2317, 8694, 3072, 8010,
 139, 6004, 6066, 4961, 2829, 2040, 8171, 4579, 9054, 2176,
 3168, 4664, 1097, 8535, 3914, 5333, 2002, 3065, 9035, 9758,
 6563, 7281, 1024, 4731, 4337, 3245, 4959, 1442, 468, 4781,
 1964, 3177, 1873, 4566, 8713, 600, 7305, 3951, 8443, 8255,
 525, 6239, 1744, 8518, 8939, 6896, 9102, 8531, 3025, 625,
 1650, 5211, 4507, 3043, 8861, 5749, 5567, 5146, 3070, 210,
 2244, 3156, 401, 9806, 8742, 6600, 9266, 8188, 9764, 2486,
 ... 9900 more items
]
result: [
 1, 3, 4, 5, 6, 7, 7, 7, 8, 10, 11, 11,
 14, 15, 16, 16, 17, 17, 19, 23, 23, 23, 24, 26,
 27, 29, 31, 36, 38, 40, 41, 43, 45, 47, 47, 48,
 49, 50, 50, 52, 53, 54, 55, 56, 56, 57, 57, 57,
 60, 60, 61, 61, 63, 63, 63, 64, 64, 64, 65, 66,
 67, 67, 67, 70, 71, 72, 74, 75, 75, 75, 75, 77,
 81, 83, 83, 85, 85, 86, 87, 89, 89, 94, 97, 97,
 97, 98, 99, 99, 100, 100, 101, 102, 102, 104, 105, 105,
 107, 107, 108, 108,
 ... 9900 more items
]
<<SortMethod>> <<TimeCost>>
countingSort 4.167 ms
bucketSort 8.095 ms
heapSort 9.147 ms
mergeSort 13.592 ms
radixSort 14.528 ms
shellSort 19.640 ms
quickSort 20.924 ms
insertionSort 48.618 ms
selectSort 56.237 ms
bubbleSort 134.236 ms

概要

ソートアルゴリズムは、比較によってソートされるかどうかによって分類することができます：

• 比較ソート：バブルソート、選択ソート、挿入ソート、ヒルソート、マージソート、クイックソート、ヒープソート。このうち、選択ソート、バブルソート、挿入ソートは最も基本的なソート方法です。ヒルソートは挿入ソートのグループであり、挿入ソートの発展版です。マージクイックソートはどちらも分割統治（divide-and-conquer）の考え方を用いますが、その違いは、マージソートが最初にすべてのグループを分割し、サブグループのヒープをソートした後にそれらをマージするのに対し、クイックソートはグループを一度分割した後にソートを開始し、次にそれらをグループ化して再度ソートすることです。一方、ヒープソートは完全な2分木と大きなトップヒープを使ってソートします。
• 非比較型ソート：カウンティング、バケットソート、ベースソート。バケットソートは、各バケット内の数値の特定の範囲を格納し、バケットでソートされます。ベースソートは、バケットとソートを割り当てるために桁の数の値に応じて。