畫像出典：medium

並べ替えは、データ構(gòu)造とアルゴリズムの最も重要な部分の 1 つです。並べ替えアルゴリズムには多くの種類がありますが、ここでは最も簡(jiǎn)単なアルゴリズムの 1 つであるバブル ソートを紹介します。

並べ替えアルゴリズムはコンピューター サイエンスの基礎(chǔ)であり、バブル ソートは最もシンプルで直感的な並べ替えアルゴリズムの 1 つです。この投稿では、バブル ソートがどのように機(jī)能するかを調(diào)査し、その時(shí)間計(jì)算量を分析し、JavaScript の実裝について説明します。

このシリーズでは、完全な並べ替えアルゴリズムのデータ構(gòu)造と Javascript を使用したアルゴリズムを共有し、バブル ソートから始めます。完全な並べ替えアルゴリズムを例とともに共有したい場(chǎng)合は、「いいね」とフォローをお願(yuàn)いします。皆さんのためにコンテンツを作成し、準(zhǔn)備するモチベーションになります。

バブルソートとは何ですか?

バブル ソートは、リストを繰り返しステップ実行し、隣接する要素 (次の要素) を比較し、順序が間違っている場(chǎng)合は入れ替える簡(jiǎn)単な並べ替えアルゴリズムです。このプロセスは、リストがソートされるまで繰り返されます。このアルゴリズムの名前は、より小さい要素がリストの先頭に「バブル」することから付けられました。

JavaScriptの実裝:

コードを詳しく見て、JavaScript でバブル ソートがどのように実裝されているかを見てみましょう:

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

出力

降順で並べ替える:

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

出力：

上記のコードの各行についてはすでにコメントを追加し、説明しています。ただし、完全なプロセスとコードを理解するのに役立つように、詳しく説明します。

仕組み:

• 初期化: 配列の長(zhǎng)さを決定することから始めます。これは、反復(fù)回?cái)?shù)の制御に役立ちます。
• 外側(cè)のループ: このループは n-1 回実行されます。ここで、n は配列の長(zhǎng)さです。各反復(fù)により、次に大きい要素が正しい位置に配置されることが保証されます。
• 內(nèi)部ループ: 外部ループのパスごとに、內(nèi)部ループは隣接する要素を比較し、順序が狂っていればそれらを交換します。最大の要素は配列の最後ですでにソートされているため、內(nèi)側(cè)のループの範(fàn)囲はパスごとに減少します。
• 交換: 要素が次の要素より大きい場(chǎng)合、それらは一時(shí)変數(shù)を使用して交換されます。
• Return: 最後に、ソートされた配列が返されます。

最適化されたバージョン:

// By default ascending order
function bubble_sort(array) {
    const len = array.length; // get the length of an array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop runs n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value 
        for (let j = 0; j > len - i -1; j++) {
            // checking if the first element greater than to the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array; // return the sorted array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

説明:

• for (let i = 0; i
• isSwapped = false にしましょう ブール変數(shù) isSwapped は false に初期化されます。この変數(shù)は、內(nèi)部ループの現(xiàn)在のパス中に要素が交換されたかどうかを追跡するために使用されます。スワップが発生しない場(chǎng)合、配列はすでにソートされており、アルゴリズムは早期に終了する可能性があります。
• for (j = 0; j
• if (配列[j] > 配列[j 1]) { この條件は、現(xiàn)在の要素が次の要素より大きいかどうかをチェックします。 true の場(chǎng)合、要素を正しく順序付けるには交換が必要です。

// Descending order
function bubble_sort_descending_order(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i -1; j++) {
            // checking if first element greter than next element,
            if (array[j] < array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort_descending_order(array));

// output data after sorted!
// [ 12, 11, 9, 7, 3 ]

• これらの行は、一時(shí)変數(shù) temp を使用して要素 array[j] と array[j 1] の交換を?qū)g行します。スワップ後、isSwapped は true に設(shè)定され、スワップが発生したことを示します。

// optimized version:
function bubble_sort(array) {
    const len = array.length; // get the length of the array
    //The outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run.
    //If the length is n then the outer loop run n-1 times.
    for (let i = 0; i < len - 1; i++) { 
        // Inner loop will run based on the outer loop and compare the value, 
        //If the first value is higher than the next value then swap it, loop must go on for each lowest value
        let isSwapped = false;
        for (let j = 0; j < len - i -1; j++) {
            //check if the first element is greater than the next element
            if (array[j] > array[j + 1]) {
                // then, swap the value array[j] to array[j+1]
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSwapped =  true;
            }
        }

        //If no element swap by inner loop then break;
        if (isSwapped === false) {
            break;
        }
    }

    return array;
}

const array =  [7, 12, 9, 11, 3]; // input data
console.log(bubble_sort(array));

// output data after sorted!
// [3, 7, 9, 11, 12]; 

• 內(nèi)側(cè)のループが完了した後、この條件は isSwapped がまだ false であるかどうかをチェックします。スワップが行われていない場(chǎng)合、配列はすでにソートされており、break を使用して外側(cè)のループを早期に終了できます。
• 最後に、ソートされた配列が返されます。

時(shí)間計(jì)算量

バブル ソートの時(shí)間計(jì)算量は、最悪の場(chǎng)合と平均的な場(chǎng)合では (O(n2)) です。ここで、(n) は配列內(nèi)の要素の數(shù)です。これは、各要素が他のすべての要素と比較されるためです。最良の場(chǎng)合、配列がすでにソートされている場(chǎng)合、スワップが必要ないときにアルゴリズムを停止する最適化が追加された場(chǎng)合、時(shí)間計(jì)算量は (O(n)) になります。

最良のシナリオでは、配列がすでにソートされている場(chǎng)合、isSwapped 最適化によりアルゴリズムが早期に終了する可能性があり、その結(jié)果、時(shí)間計(jì)算量は (O(n)) になります。

全體として、バブル ソートは二次時(shí)間計(jì)算量のため、大規(guī)模なデータセットに対しては効率的ではありませんが、小さな配列に対して、またはソート アルゴリズムを理解するための教育ツールとしては役立ちます。

結(jié)論

バブル ソートは、そのシンプルさから教育目的に最適なアルゴリズムです。ただし、二次時(shí)間計(jì)算量があるため、大規(guī)模なデータセットには適していません。非効率ではありますが、バブル ソートを理解することは、より高度なソート アルゴリズムを?qū)W習(xí)するための基礎(chǔ)となります。

以上がバブルソートアルゴリズムを理解する: ステップバイステップガイドの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語 Web サイトの他の関連記事を參照してください。