JavaScriptでの初心者のソートアルゴリズム:Bubble,Selection&Insertion Sort

データセットをすべて自由に配置すると、管理と検索のための時間とリソースが追加されます。 データがソートされているかどうかは、使用できる検索方法に直接影響し、バイナリ検索のように、百万の操作を取る検索と10を取る検索の違いを意味す

簡単にするために、数字の配列を最小から最大にソートすることに焦点を当てるだけですが、これらのアルゴリズムは他のソート目標に対して簡単に これらはより一般的な概念とパターンであり、特定の実装が大きく異なる可能性があるため、データをソートするための”ハウツー”は少なくなりますが、最終的には概念的にはこれらのパターンに似ている可能性があることに注意してください。

ここに50個の乱数の練習配列があります。前提条件

const unsortedArr = ;

前提条件

私はBig O記法のレンズを通してすべてを見ているので、時間の経過とともに複雑さがどのように成長するかを理解するこ

バブルソート

ここは、”こんにちは世界”の分別方法、かつ、狂気がします。

配列内の各項目について、次の項目が大きいかどうかを確認します。 ソートされた数値の再比較を避けるために、配列の後ろから開始し、別のfor loopが先行する数値を取得します。 このようにして、すべての最大値が最終的に蓄積されるか、または「バブルアップ」されます。

バブルソートアニメーション

グラフィック/アニメーションVisuAlgo.net

私たちのバージョンは、アニメーションとは逆に動作しますが、それは十分に近いです。

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Selection Sort

Selection sortはBubble sortの反対のように機能しますが、bubble sortはすべての最大値を最後にプッシュしています今、最小値を先頭にプッシュします。

配列をループするたびに、最小の値が選択され、より低い値が見つかった場合、それが新しい最低値になります。 ループが完了すると、その最小値が取得され、ループを再度開始する前に配列の前面に配置されます。 このようにして、配列全体がソートされるまで、各反復の最低値が前面に積み重ねられます。

選択ソートアニメーション

グラフィック/アニメーションVisuAlgoのおかげで。ネット

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

挿入ソート

私の個人的なお気に入りで、三つの中で最もパフォーマンスの高い、挿入ソートは、あなたが手で何かをソートする方法に似ています。

配列をソートされた部分とソートされていない部分の2つの部分として見て、新しい値を見つけるたびにループバックしてソートされた半分の場所を見 それぞれの追加で、ソートされたグループは配列全体になるまで成長します。

挿入ソートアニメーション

グラフィック/アニメーションVisuAlgoのおかげで。net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

Comparison

アルゴリズムを比較するためにBig O記法を使用する際の1つの問題は、それが悪いケースのシナリオに基づいていることです。 バブル、選択、挿入のソートはすべてO(n^2)ですが、平均的なシナリオや最良のシナリオ、またはデータ構造によってどのように変化するかについてはあまり

また、開始する前に配列全体を持つ必要がないという利点もあり、データが入ってくるときにリアルタイムで物事をソートすることができます。

データがどのように整理されているかを検討する前に、どのアルゴリズムが”最良”であるかを決定するべきではないので、これに留意してください。

結論

これら三つは、効率的に大量のデータをソートするための最良の解決策からはほど遠いですが、彼らは圧倒的な海になることができるものにあ 🌊