JavaScriptによる基数ソートを理解する
比較ベースのソートの性質上、マージソートやクイックソートのように、O(nlogn)
をはるかに超えて改善することは数学的に不可能です。 代わりに、もう少し賢くなり、O(n * m)
に近づくために、すべてを一緒に比較することを避けることができます。
前提条件
Big O Notation の基本的な理解は、他のアルゴリズムと比較した基数ソートについて考えるために不可欠です。
コンセプト
基数ソートはバケットソートとも呼ばれ、最も古いソートアルゴリズムの1つであり、既存のコンピューターですらあります。 1880年代にパンチカードを分類するために使用されました。
これは、AZやこの場合は0〜9のように、比較する必要のあるデータのタイプごとにサブ配列またはバケットを用意するという考えに基づいています。 各アイテムの最初の文字/数字を取得し、アイテム全体を対応するバケットに追加してから、新しい順序を保持したまま配列に戻します。
次に、次の文字/数字に移動して、プロセスを繰り返すことができます。 アイテムが文字/数字を使い果たした場合、他のすべてが明らかに大きい/長いため、最初のバケットに追加します。 最大のアイテムの桁/文字数と同じ回数これを実行すると、厄介な比較を行うことなく、配列が完全にソートされます。
VisuAlgo.netのおかげでグラフィック/アニメーション
練習データ
数字ははるかに単純なので、1から50までの数字の配列で練習できます。
const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];
ユーティリティ
数字を扱っているので、最小の数字の場所から始めて、上に向かっていきたいので、右から始まるインデックスで各数字を取得する方法が必要になります。
私が見つけた最も直感的な方法は、必要な数を取得して文字列に変換し、その中から負のインデックスを持つ配列として選択することです。 数値がそのインデックスにない場合は、ゼロを返すだけで、ソートされた配列の前に配置されます。
const getNum = (num, index) => { const strNum = String(num); let end = strNum.length - 1; const foundNum = strNum[end - index]; if (foundNum === undefined) return 0; else return foundNum; }; console.log(getNum(4353, 2));
一度に1桁前に戻るため、アルゴリズムは最長の数値の何倍も実行する必要があります。したがって、8桁のアイテムがある場合は、8回実行する必要があります。 基数ソートの平均的な複雑さはO(n * m)
です。これは、アイテムの数に実行する必要のある回数を掛けたものだからです。
実行する回数を取得するには、配列を検索して最大数を検索し、その長さを返します。
const largestNum = arr => { let largest = "0"; arr.forEach(num => { const strNum = String(num); if (strNum.length > largest.length) largest = strNum; }); return largest.length; };
基数ソート
実装は非常に簡単です。すべての桁の場所で、Array.from
を使用して10個の空のバケットを作成できます。 すべてのアイテムについて、それらは対応するバケットに配置されます。それが完了すると、バケットの配列を1つの配列にフラット化して、次の文字の場所からやり直します。 最長の桁の終わりに達すると、完全にソートされた配列を返すことができます。
const radixSort = arr => { let maxLength = largestNum(arr); for (let i = 0; i < maxLength; i++) { let buckets = Array.from({ length: 10 }, () => []); for (let j = 0; j < arr.length; j++) { let num = getNum(arr[j], i); if (num !== undefined) buckets[num].push(arr[j]); }; arr = buckets.flat(); }; return arr; }; console.log(radixSort(unsortedArr));
結論
これをいじりながら、5,000アイテムの配列で試してみましたが、驚いたことに、わずか23ミリ秒で完了しました。 あなたのことはわかりませんが、これまでに取り上げた他のアルゴリズムに比べて、信じられないほどの改善だと思います。