Sumber Imej: sederhana

Isih ialah salah satu bahagian yang paling penting dalam Struktur Data dan Algoritma. Terdapat banyak jenis algoritma pengisihan dan berikut ialah salah satu algoritma yang paling mudah: Isih gelembung.

Algoritma pengisihan adalah asas dalam sains komputer, dan Isih Buih ialah salah satu algoritma pengisihan yang paling mudah dan intuitif. Siaran ini akan meneroka cara Isih Buih berfungsi, menganalisis kerumitan masanya dan menelusuri pelaksanaan JavaScript.

Dalam siri ini, saya akan berkongsi Struktur Data Algoritma Pengisihan yang lengkap dan Algoritma menggunakan Javascript dan bermula dengan Isih Buih. Jika anda suka dan mahu saya berkongsi algoritma Isih lengkap dengan contoh, sila suka dan ikuti saya. Ia mendorong saya untuk mencipta dan menyediakan kandungan untuk anda semua.

Apakah Bubble Sort?

Isih Buih ialah algoritma pengisihan mudah yang berulang kali melangkah melalui senarai, membandingkan elemen bersebelahan (elemen seterusnya) dan menukarnya jika ia berada dalam susunan yang salah. Proses ini diulang sehingga senarai diisih. Algoritma mendapat namanya kerana elemen yang lebih kecil "gelembung" ke bahagian atas senarai.

Pelaksanaan JavaScript:

Mari kita selami kod untuk melihat cara Isih Buih dilaksanakan dalam 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]; 

Output

Isih dengan Pesanan Menurun:

// 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 ]

Output:

Sudah menambah ulasan dan menerangkan setiap baris kod di atas. tetapi saya juga akan menerangkan secara terperinci supaya ia membantu anda memahami proses dan kod yang lengkap.

Cara ia berfungsi:

• Permulaan: Kami mulakan dengan menentukan panjang tatasusunan, yang membantu mengawal bilangan lelaran.
• Gelung Luar: Gelung ini berjalan n-1 kali, dengan n ialah panjang tatasusunan. Setiap lelaran memastikan elemen terbesar seterusnya diletakkan pada kedudukannya yang betul.
• Gelung Dalam: Untuk setiap laluan gelung luar, gelung dalam membandingkan elemen bersebelahan dan menukarnya jika ia tidak teratur. Julat gelung dalam berkurangan dengan setiap hantaran kerana elemen terbesar sudah diisih pada penghujung tatasusunan.
• Pertukaran: Jika elemen lebih besar daripada elemen seterusnya, ia ditukar menggunakan pembolehubah sementara.
• Pulangan: Akhirnya, tatasusunan yang diisih dikembalikan.

Versi Dioptimumkan:

// 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]; 

Penjelasan:

• untuk (biar i = 0; i < len — 1; i ) Ini ialah gelung luar, yang berjalan n-1 kali, dengan n ialah panjang tatasusunan. Gelung luar mengawal berapa kali gelung dalam akan dilaksanakan. Setiap lelaran gelung luar memastikan elemen terbesar seterusnya diletakkan pada kedudukannya yang betul.
• let isSwapped = palsu Pembolehubah boolean isSwapped dimulakan kepada false. Pembolehubah ini digunakan untuk menjejaki sama ada mana-mana elemen ditukar semasa laluan semasa gelung dalam. Jika tiada pertukaran berlaku, tatasusunan sudah diisih dan algoritma boleh ditamatkan lebih awal.
• untuk (biar j = 0; j < len — i — 1; j ) { Ini ialah gelung dalam, yang berulang ke atas elemen tatasusunan sehingga len - i - 1. Bahagian - i memastikan bahawa gelung tidak mengambil kira elemen yang telah diisih dalam pas sebelumnya.
• jika (tatasusunan[j] > tatasusunan[j 1]) { Keadaan ini menyemak sama ada elemen semasa lebih besar daripada elemen seterusnya. Jika benar, pertukaran diperlukan untuk menyusun elemen dengan betul.

// 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 ]

• Baris ini melakukan pertukaran elemen tatasusunan[j] dan tatasusunan[j 1] menggunakan temp pembolehubah sementara. Selepas pertukaran, isSwapped ditetapkan kepada benar, menunjukkan bahawa pertukaran telah berlaku.

// 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]; 

• Selepas gelung dalam selesai, syarat ini menyemak sama ada isSwapped masih palsu. Jika tiada swap dibuat, tatasusunan sudah diisih dan gelung luar boleh keluar awal menggunakan break.
• Akhir sekali, tatasusunan yang diisih dikembalikan.

Kerumitan Masa

Kerumitan masa Isih Buih ialah (O(n2)) dalam kes yang paling teruk dan purata, dengan (n) ialah bilangan elemen dalam tatasusunan. Ini kerana setiap elemen dibandingkan dengan setiap elemen lain. Dalam kes terbaik, apabila tatasusunan sudah diisih, kerumitan masa boleh menjadi (O(n)) jika pengoptimuman ditambahkan untuk menghentikan algoritma apabila tiada pertukaran diperlukan.

Dalam senario kes terbaik, apabila tatasusunan sudah diisih, algoritma boleh ditamatkan awal disebabkan pengoptimuman isSwapped, menghasilkan kerumitan masa (O(n)).

Secara keseluruhan, pengisihan gelembung tidak cekap untuk set data yang besar kerana kerumitan masa kuadratiknya, tetapi ia boleh berguna untuk tatasusunan kecil atau sebagai alat pendidikan untuk memahami algoritma pengisihan.

Kesimpulan

Isih Buih ialah algoritma yang sangat baik untuk tujuan pendidikan kerana kesederhanaannya. Walau bagaimanapun, ia tidak sesuai untuk set data yang besar kerana kerumitan masa kuadratiknya. Walaupun ketidakcekapannya, pemahaman Bubble Sort menyediakan asas untuk mempelajari algoritma pengisihan yang lebih maju.

Atas ialah kandungan terperinci Memahami Algoritma Isih Buih: Panduan Langkah demi Langkah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!