[Bermain muzik] DOUG LLOYD: Baiklah, jadi semacam gelembung algoritma anda boleh gunakan untuk menyelesaikan satu set unsur-unsur. Mari kita lihat bagaimana ia berfungsi. 

Jadi idea asas di sebalik gelembung jenis adalah ini. Kita biasanya mahu untuk bergerak lebih tinggi unsur-unsur bernilai umumnya ke kanan, dan menurunkan unsur bernilai umumnya ke kiri, seperti yang kita jangkakan. Kami mahu perkara yang lebih rendah untuk berada di mulanya, dan perkara-perkara yang lebih tinggi untuk berada di akhir. 

Bagaimana kita lakukan ini? Well kod pseudo, kita boleh katakan, mari kita menetapkan kaunter pertukaran kepada nilai yang bukan sifar. Kami akan melihat mengapa kita berbuat demikian dalam satu saat. Dan kemudian kita mengulangi berikut proses sehingga kaunter pertukaran adalah 0, atau sehingga kami tidak membuat sebarang pertukaran pada semua. 

Menetapkan semula kaunter pertukaran untuk 0 jika tidak sudah 0. Kemudian melihat setiap pasangan bersebelahan unsur-unsur. Jika kedua-dua elemen ini tidak teratur, menukar mereka, dan tambahkan 1 ke kaunter swap. Jika anda berfikir tentang ini sebelum anda menggambarkan ia, melihat bahawa ini akan bergerak lebih rendah elemen penting ke kiri dan lebih tinggi bernilai unsur-unsur ke kanan, berkesan melakukan apa yang kita mahu lakukan, yang memindahkan kumpulan unsur-unsur dengan cara itu. Mari kita menggambarkan bagaimana ini mungkin kelihatan menggunakan pelbagai kami yang kita digunakan untuk menguji daripada algoritma ini. Kami mempunyai pelbagai terisih di sini lagi, ditunjukkan oleh semua unsur-unsur menjadi merah. Dan Aku menguduskan kaunter pertukaran saya kepada nilai bukan sifar. Saya sewenang-wenangnya memilih negatif 1-- ia bukan 0. Kami mahu mengulangi proses ini sehingga kaunter pertukaran adalah 0. Ini adalah mengapa saya menetapkan pertukaran saya bertentangan dengan beberapa nilai bukan sifar, kerana jika tidak, kaunter pertukaran akan menjadi 0. Kami akan tidak memulakan proses algoritma. Jadi sekali lagi, langkah-langkah ialah- menetapkan semula kaunter swap kepada 0, kemudian melihat setiap bersebelahan pasangan, dan jika mereka daripada perintah, menukar mereka, dan menambah 1 ke kaunter swap. Jadi mari kita memulakan proses ini. Jadi perkara pertama yang kita lakukan adalah kita menetapkan kaunter pertukaran ke 0, dan kemudian kita mula mencari di setiap pasangan bersebelahan. 

Oleh itu, kita mula-mula mula melihat 5 dan 2. Kita lihat bahawa mereka berada di luar memerintahkan dan dengan itu kita menukar mereka. Dan kita tambah 1 ke kaunter swap. Jadi sekarang kaunter pertukaran kami adalah 1, dan 2 dan 5 telah dihidupkan. Sekarang kita mengulangi proses lagi. 

Kita melihat pasangan bersebelahan yang akan datang, 5 dan 1-- mereka juga daripada perintah, jadi kami menukar mereka dan menambah 1 ke kaunter swap. Kemudian kami melihat 5 dan 3. Mereka adalah daripada perintah, jadi kami menukar mereka dan kami tambahkan 1 ke kaunter swap. Kemudian kami melihat 5 dan 6. Mereka berada dalam perintah, supaya kita tidak benar-benar perlu untuk menukar apa-apa masa ini. Kemudian kita melihat 6 dan 4. Mereka juga berada di luar perintah, jadi kami menukar mereka dan kami tambahkan 1 ke kaunter swap. 

Sekarang perhatikan apa yang berlaku. Kami telah berpindah 6 hingga ke akhir. Jadi dalam jenis pemilihan, jika anda telah melihat video itu, apa yang kami lakukan adalah kita berakhir menggerakkan unsur-unsur yang paling kecil di dalam bangunan array disusun dasarnya dari kiri ke kanan, kecik hingga besar. Dalam hal semacam gelembung, jika kita berikut algoritma ini khususnya, sedang kita benar-benar akan membina array disusun dari kanan ke kiri, terbesar kepada yang paling kecil. Kami berkesan dipam 6, nilai terbesar, sepanjang jalan ke akhir. 

Dan dengan itu kita kini boleh mengisytiharkan bahawa yang disusun, dan pada masa akan iterations-- melalui array again-- kita tidak perlu mengambil kira 6 lagi. Kita hanya perlu mengambil kira unsur-unsur terisih apabila kita melihat pasangan bersebelahan. Jadi kita telah selesai satu melalui semacam gelembung. Jadi sekarang kita kembali kepada soalan, ulangi sehingga kaunter pertukaran adalah 0. Well kaunter swap ialah 4, jadi kita akan untuk terus mengulangi proses ini lagi. 

Kami akan menetapkan semula kaunter swap kepada 0, dan melihat setiap pasangan bersebelahan. Oleh itu, kita mulakan dengan 2 dan 1-- mereka daripada perintah, supaya kita menukar mereka dan kita tambah 1 ke kaunter swap. 2 dan 3, mereka teratur. Kita tidak perlu berbuat apa-apa. 3 dan 5 adalah teratur. Kita tidak perlu berbuat apa-apa di sana. 

5 dan 4, mereka berada di luar perintah, dan dengan itu kita perlu untuk menukar mereka dan menambah 1 ke kaunter swap. Dan sekarang kita telah berpindah 5, unsur terbesar yang akan datang, hingga akhir bahagian yang terisih. Oleh itu, kita kini boleh memanggil bahawa sebahagian daripada bahagian yang disusun. 

Kini anda sedang melihat skrin dan mungkin boleh beritahu, begitu juga saya, yang array disusun sekarang. Tetapi kita tidak dapat membuktikan bahawa kini. Kami tidak mempunyai jaminan bahawa ia disusun. Tetapi ini adalah di mana swap kaunter akan datang ke dalam bermain. 

Oleh itu, kita telah menyelesaikan lulus. Kaunter pertukaran ialah 2. Jadi, kita akan mengulangi proses ini lagi, ulangi sehingga kaunter pertukaran adalah 0. Menetapkan semula kaunter pertukaran ke 0. Oleh itu, kita akan menetapkan semula. 

Sekarang lihat pada setiap pasangan bersebelahan. Itulah teratur, 1 dan 2. 2 dan 3 adalah teratur. 3 dan 4 adalah teratur. Jadi pada ketika ini, melihat kami telah selesai melihat setiap pasangan yang bersebelahan, tetapi kaunter pertukaran itu masih 0. 

Jika kita tidak perlu menukar sebarang unsur-unsur, maka mereka hendaklah teratur, dengan menurut proses ini. Dan sebagainya kecekapan macam, bahawa saintis kita komputer cinta, adalah kita kini boleh mengisytiharkan pelbagai keseluruhan mesti diisih, kerana kita tidak perlu menukar mana-mana unsur-unsur. Itu cukup bagus. 

Jadi apa kes yang paling teruk senario dengan seperti gelembung? Dalam kes terburuk array adalah agar benar-benar terbalik, dan dengan itu kita perlu gelembung setiap unsur-unsur besar semua jalan di seluruh array. Dan kita berkesan juga perlu gelembung semua unsur-unsur kecil kembali sepanjang jalan di seluruh array, juga. Jadi setiap satu daripada unsur-unsur n perlu bergerak di semua unsur-unsur n lain. Jadi itulah senario kes terburuk. Dalam kes ini, senario walaupun, ini adalah sedikit berbeza daripada jenis pemilihan. Array sudah disusun apabila kita masuk ke dalam. Kami tidak perlu membuat sebarang swap pada pas yang pertama. Oleh itu, kita mungkin perlu melihat di lebih sedikit unsur-unsur, bukan? Kami tidak perlu mengulangi ini memproses beberapa kali. 

Jadi apa maksudnya? Jadi apa kes yang teruk untuk jenis gelembung, dan apa yang kes senario terbaik untuk jenis gelembung? Adakah anda rasa ini? Dalam kes terburuk anda perlu untuk melelar di semua n unsur n kali. Jadi kes yang paling teruk adalah n kuasa dua. 

Jika array adalah sempurna disusun walaupun, anda hanya perlu melihat setiap satu elemen sekali. Dan jika kaunter pertukaran itu masih 0, anda boleh berkata pelbagai ini disusun. Dan sebagainya dalam kes ini, ini adalah sebenarnya lebih baik daripada pilihan sort-- ia omega n. 

Saya Doug Lloyd. Ini adalah CS50.