JavaScript バブルソートアルゴリズム

バブル ソートは、比較的シンプルで理解しやすいため、人々が最初に考えるソート アルゴリズムであることがよくあります。基本的な考え方は、2 つの数値を一度に比較し、それらが正しい順序であることを確認してから、他の項目に進むことです。各レベルの最後に、貴重なアイテムが正しい位置に「並べ替え」られ、最終的には他のアイテムだけが並べ替えられます。原文のソース: http://caibaojian.com/javascript-bubble-sort.html

アルゴリズム実装アイデア

最初の項目と 2 番目の項目を比較します

最初の項目が 2 番目の項目の後ろにある必要がある場合は、それらを入れ替えます

2 番目の項目と 3 番目の項目を比較します

2 番目の項目が 3 番目の項目の後にある場合は、それらを入れ替えます

データの最後まで続けます

このプロセスは、それぞれのデータが完全に並べ替えられるまで数回繰り返されます。サイクル、最後の項目は毎回正しくソートされるため、ソートする項目はますます少なくなります。よりよく理解するために、配列 [3, 2, 4, 5, 1] を比較してみましょう。

比較プロセスの例

1 つ目はポジティブソートで、最初の項目と 2 番目の項目を比較します。2 ～ 3 は小さいため、 3 が最後に配置され、結果は [2,3,4,5,1] になります。

2 番目と 3 番目の項目の順序は正しいので、3 番目と 4 番目の項目も入れ替える必要はありません。正しいです。交換する必要はありません。4 番目と 5 番目のアイテムが交換され、結果は [2,3,4,1,5] になります。

最初と 2 番目のアイテムを再度ループし、3 番目と 4 番目のアイテムを交換します。 [2,3,1,4,5]

3サイクル目、2回目と3回目の交換は[2,1,3,4,5]

4サイクル目、1回目と2回目の交換実装の第一歩[1,2,3,4,5]

のバブル ソートは、配列内の 2 つの項目を交換するメソッドを作成することです。この方法は、多くの非効率的なソートで一般的です。簡単な JavaScript 実装コードは次のとおりです:

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

via 前述したように、この並べ替えアルゴリズムは複数の並べ替えが必要なため、比較的非効率的です。配列に n 個の項目があると仮定すると、計算には 2 の n 乗が必要になります。http://caibaojian.com/javascript-bubble-sort.html

前方バブル アルゴリズムの原文を見てみましょう。

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

via の外側のループはサイクル数を制御し、内側のループは項目間のソート比較です。

逆バブルソート

function bubbleSort(items){
    var len = items.length,
        i, j;

    for (i=len-1; i >= 0; i--){
        for (j=len-i; j >= 0; j--){
            if (items[j] < items[j-1]){
                swap(items, j, j-1);
            }
        }
    }

    return items;
}

via上記の 2 つのコードの結果は同じで、どちらも小さいものから大きいものにソートされますが、ループの順序がわずかに異なり、どちらも順方向バブルです。

逆バブルソート

は、最初の項目が 2 番目の項目より小さい場合、位置を入れ替えるなど、サイズの変更を実際に決定します。

function bubbleSort2(items){
var len = items.length,
i,j,stop;
for(i=0;i<len; i++){
for(j=0,stop=len-i;j<stop;j++){
if(items[j]<items[j+1]){
swap(items,j,j+1);
}
}
}
return items;
}

概要

via 繰り返しになりますが、バブル ソートは実際の作業には適用できない場合があります。これは、アルゴリズムを理解し、より多くの知識を習得するための基礎を築くのに役立つ単なるツールです。私たちが最もよく使用するのは、おそらく組み込みの Array.prototype.sort() プロトタイプ メソッドです。これは、より効率的であるためです。

JavaScript バブルソートアルゴリズムに関連するその他の記事については、PHP 中国語 Web サイトに注目してください。