JavaScript での挿入ソート
この記事では、JavaScript における挿入ソートの考え方について説明し、その実装例を示します。
JavaScript の並べ替えテクニック
最適性、高速化、および間隔の縮小を実現するというビジョンを持った関心のある個人によって、さまざまな並べ替え手法が開発されました。 この実行では、挿入ソートは、最悪の場合の時間計算量が O(n^2) であるのに対し、最良の場合は O(n) であることを示しています。
ソートするデータ量が少ない場合は、Array.prototype.sort() が適しています。 好ましい状況として、それは O(n) の時間計算量を与えます。これは O(n*logn) よりも優れています。
ただし、sort() 関数は、複雑なオブジェクトなどを含む大量のデータに対してはうまく機能しません。Array.prototype.sort() 関数には、挿入ソートが実装されているため、JavaScript のデフォルトのソート アルゴリズムが使用されます。 効率の良い部類には入りません。
また、コードの並べ替えのパフォーマンスは、ユーザーが使用しているブラウザーに依存することにも注意してください。 Chrome V8 は Tim Sort (Insertion Sort + Merge Sort) を使用し、Firefox は基本的な Merge Sort を使用します。
実際のシナリオでは、生データは必ずしも順不同ではありません。 代わりに、彼らは秩序のパターンに従います。 したがって、データを最初からソートする必要はないと言えます。
V8 の場合、アレイは最初に run と呼ばれるブロックに分割されます。 最下位レベルのこれらの 実行 は、挿入ソートの原則でソートされ、後でマージ ソートの方法でマージされます。
少数の数値またはオブジェクトを操作している場合、Tim Sort は時間複雑度 O(n) の挿入ソートとして動作します。 一方、大規模なデータの場合、V8 ソートは O(n*logn) の時間計算量を持つマージ ソートとして機能します。
そのため、Tim Sort は、従来の Merge Sort よりも高度に最適化された安定したソート手法です。
この例のセクションでは、挿入ソートの基本的な考え方を説明し、なぜそれが制約を持っているのか、なぜ多くのソートよりも優れているのかを判断できるようにします。 前の部分の説明では、JavaScript エンジンである V8 エンジンで挿入ソートがどのように使用されるかについて説明しました。
デモンストレーションに飛び乗りましょう。
JavaScript で挿入ソート手法を実装する
この種の基本的な考え方は、カードの手札を並べ替えることにたとえることができます。 最初にカードを最初に設定し、後でソートする次のカードを選択します。これを最初のセット カードと呼びます。
ここで、次のカードは key と名付けられ、key が最初のカードよりも大きい場合は、そのまま保持します。 それ以外の場合は、key と最初のカードの位置を入れ替えます。 そして、配列全体がトラバースされ、ソートされるまで、これが繰り返されます。
コード行を確認してみましょう。
コードスニペット：
var arr = [4, 2, 3, 1, 7];
var size = arr.length;
for (var i = 1; i < size; i++) {
var key = arr[i];
var j = i - 1;
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
console.log(arr)
出力：
ご覧のとおり、挿入ソートは O(1) のスペースの複雑さを持ちます。これは、1 スロットではなく、キーを格納するためのスペースの他の配列を占有しないためです。 ですので、最適なスペースを意識するのであれば、この種が合うかもしれません。
