[MUSIC PLAYING] Doug LLOYD: Baiklah, jadi bubble sort adalah sebuah algoritma Anda dapat menggunakan untuk mengurutkan satu set elemen. Mari kita lihat cara kerjanya. 

Jadi ide dasar di balik bubble sort adalah ini. Kita umumnya ingin bergerak lebih tinggi elemen dihargai umumnya ke kanan, dan menurunkan elemen dihargai umumnya ke kiri, seperti yang kita harapkan. Kami menginginkan hal yang lebih rendah berada di awal, dan hal-hal yang lebih tinggi berada di akhir. 

Bagaimana kita melakukan ini? Nah dalam kode pseudo, kita bisa mengatakan, mari kita mengatur counter swap nilai non-nol. Kami akan melihat mengapa kita melakukan itu dalam satu detik. Dan kemudian kita mengulang berikut proses sampai counter swap adalah 0, atau sampai kami tidak membuat swap sama sekali. 

Atur ulang swap counter untuk 0 jika tidak sudah 0. Kemudian melihat setiap berdekatan sepasang elemen. Jika kedua unsur adalah tidak dalam urutan, swap mereka, dan tambahkan 1 ke counter swap. Jika Anda berpikir tentang ini sebelum Anda memvisualisasikan itu, melihat bahwa ini akan bergerak lebih rendah elemen dihargai ke kiri dan lebih tinggi dihargai elemen ke kanan, efektif melakukan apa yang ingin kita lakukan, yang bergerak kelompok-kelompok elemen dengan cara itu. Mari kita memvisualisasikan bagaimana ini mungkin terlihat menggunakan array kita bahwa kita digunakan untuk menguji out algoritma ini. Kami memiliki sebuah array disortir di sini lagi, ditunjukkan oleh semua elemen menjadi merah. Dan saya mengatur pertukaran kontra saya ke nilai nol. Aku sewenang-wenang memilih negatif 1-- itu tidak 0. Kami ingin mengulang proses ini sampai counter swap adalah 0. Ini adalah mengapa saya mengatur swap counter untuk beberapa nilai bukan nol, karena jika tidak Swap kontra akan 0. Kita bahkan tidak akan memulai proses algoritma. Jadi sekali lagi, langkah-langkah are-- reset counter Swap ke 0, kemudian melihat setiap berdekatan Pasangan, dan jika mereka rusak, swap mereka, dan menambahkan 1 ke counter swap. Jadi mari kita mulai proses ini. Jadi hal pertama yang kita lakukan adalah kita mengatur meja swap 0, dan kemudian kami mulai mencari di setiap pasangan yang berdekatan. 

Jadi pertama-tama kita mulai melihat 5 dan 2. Kami melihat bahwa mereka berada di luar memesan dan jadi kami swap mereka. Dan kita menambahkan 1 ke counter swap. Jadi sekarang Swap counter kami adalah 1, dan 2 dan 5 telah beralih. Sekarang kita ulangi proses lagi. 

Kami melihat pasangan yang berdekatan berikutnya, 5 dan 1-- mereka juga rusak, jadi kami swap mereka dan menambahkan 1 ke counter swap. Kemudian kita melihat 5 dan 3. Mereka rusak, jadi kami bertukar mereka dan kita tambahkan 1 ke counter swap. Kemudian kita melihat 5 dan 6. Mereka berada di urutan, jadi kita tidak benar-benar perlu menukar apapun saat ini. Kemudian kita melihat 6 dan 4. Mereka juga sudah rusak, jadi kami bertukar mereka dan kita tambahkan 1 ke counter swap. 

Sekarang perhatikan apa yang terjadi. Kami sudah pindah 6 sampai ke akhir. Jadi dalam pemilihan semacam, jika Anda sudah melihat video itu, apa yang kita lakukan adalah kami akhirnya memindahkan elemen terkecil di gedung array diurutkan dasarnya dari kiri ke kanan, terkecil hingga terbesar. Dalam kasus semacam gelembung, jika kita Berikut algoritma tertentu, kita benar-benar akan membangun array diurutkan dari kanan ke kiri, terbesar ke terkecil. Kami telah efektif menggelegak 6, yang nilai terbesar, semua jalan sampai akhir. 

Dan kita sekarang dapat mendeklarasikan bahwa yang diurutkan, dan di masa depan iterations-- melalui array again-- kita tidak harus mempertimbangkan 6 lagi. Kami hanya harus mempertimbangkan elemen disortir ketika kita sedang melihat pasangan yang berdekatan. Jadi kita telah selesai satu melewati bubble sort. Jadi sekarang kita kembali ke pertanyaan, ulangi sampai counter swap adalah 0. Nah counter Swap adalah 4, jadi kita akan terus mengulangi proses ini lagi. 

Kita akan me-reset counter Swap dengan 0, dan melihat setiap pasangan yang berdekatan. Jadi kita mulai dengan 2 dan 1-- mereka rusak, jadi kami swap mereka dan kita tambahkan 1 ke counter swap. 2 dan 3, mereka dalam rangka. Kita tidak perlu melakukan apa-apa. 3 dan 5 adalah dalam rangka. Kita tidak perlu melakukan apa-apa di sana. 

5 dan 4, mereka berada di luar ketertiban, dan jadi kami perlu swap mereka dan menambahkan 1 ke counter swap. Dan sekarang kita sudah pindah 5, elemen terbesar berikutnya, ke ujung bagian yang tidak dipisahkan. Jadi sekarang kita bisa menyebutnya bagian dari bagian diurutkan. 

Sekarang Anda melihat layar dan mungkin bisa mengatakan, seperti dapat saya, bahwa array diurutkan sekarang. Tapi kita tidak bisa membuktikan bahwa belum. Kami tidak memiliki jaminan bahwa itu diurutkan. Tapi ini adalah di mana swap kontra akan ikut bermain. 

Jadi kami telah menyelesaikan lulus. Swap counter 2. Jadi kita akan mengulangi Proses ini lagi, ulangi sampai counter swap adalah 0. Reset counter swap 0. Jadi kita akan me-reset. 

Sekarang lihat setiap pasangan yang berdekatan. Itu dalam rangka, 1 dan 2. 2 dan 3 adalah dalam rangka. 3 dan 4 adalah dalam rangka. Jadi pada titik ini, melihat kami sudah selesai melihat setiap pasangan yang berdekatan, tapi counter swap adalah masih 0. 

Jika kita tidak perlu beralih setiap elemen, maka mereka harus dalam rangka, oleh kebajikan dari proses ini. Dan efisiensi macam, bahwa para ilmuwan kita cintai komputer, sekarang kita dapat mendeklarasikan seluruh array harus diurutkan, karena kita tidak harus menukar elemen. Itu cukup bagus. 

Jadi apa kasus terburuk Skenario dengan bubble sort? Dalam kasus terburuk array adalah dalam rangka benar-benar terbalik, dan jadi kita harus gelembung setiap dari unsur-unsur besar semua jalan melintasi array. Dan kita juga harus efektif gelembung semua elemen kecil kembali semua jalan melintasi array, juga. Jadi masing-masing elemen n harus bergerak di semua elemen n lainnya. Jadi itulah skenario terburuk. Dalam kasus terbaik skenario walaupun, ini adalah sedikit berbeda dari pemilihan semacam. Array sudah diurutkan ketika kita masuk. Kami tidak perlu membuat swap pada lulus pertama. Jadi kita mungkin harus melihat di elemen yang lebih sedikit, kan? Kami tidak perlu mengulangi ini memproses beberapa kali lebih. 

Jadi apa artinya? Jadi apa skenario terburuk untuk bubble sort, dan apa skenario kasus terbaik untuk bubble sort? Apakah Anda kira ini? Dalam kasus terburuk Anda harus iterate di semua elemen n n kali. Jadi kasus terburuk adalah n kuadrat. 

Jika array adalah sempurna diurutkan meskipun, Anda hanya harus melihat setiap elemen sekali. Dan jika counter swap adalah masih 0, Anda bisa mengatakan array ini diurutkan. Dan dalam kasus terbaik, ini adalah sebenarnya lebih baik dari pilihan sort-- itu omega dari n. 

Aku Doug Lloyd. Ini adalah CS50.