[Bermain muzik] DOUG LLOYD: jenis Pemilihan adalah algoritma yang, seperti yang anda jangkakan, menyusun satu set unsur-unsur. Dan algoritma ingat adalah satu set langkah-demi-langkah arahan untuk menyiapkan tugas. 

Dalam pemilihan menyusun Idea asas adalah ini, mencari elemen terisih yang paling kecil dan menambah kepada akhir senarai disusun. Berkesan apa yang dilakukan adalah membina senarai disusun, satu elemen pada satu masa. Memecahkannya kepada kod pseudo kita boleh menyatakan algoritma ini seperti berikut, ulangi ini sehingga tiada unsur terisih kekal. Mencari melalui terisih data untuk mencari nilai yang paling kecil, kemudian menukar nilai yang paling kecil dengan Elemen pertama bahagian terisih. 

Ia boleh membantu untuk menggambarkan ini, jadi mari kita lihat ini. Jadi ini, saya berpendapat, adalah lokasi terisih dan saya telah menunjukkan ia dengan menunjukkan bahawa semua unsur-unsur yang berwarna merah, mereka belum disusun. Ini adalah keseluruhan sebahagian terisih array. 

Jadi mari kita pergi melalui langkah-langkah jenis pemilihan untuk menyusun pelbagai ini. Jadi sekali lagi, kita akan berulang sehingga tidak ada unsur-unsur terisih kekal. Kami carian gonna melalui data untuk mencari nilai yang paling kecil, dan kemudian menukar nilai itu dengan Elemen pertama bahagian terisih. 

Buat masa ini, sekali lagi, keseluruhan lokasi adalah bahagian yang terisih. Semua unsur-unsur merah terisih. Oleh itu, kita mencari melalui dan kita mencari nilai yang paling kecil. Kami bermula pada awal, kita pergi ke akhirnya, kita mencari nilai yang paling kecil adalah, satu. Jadi itulah bahagian satu. Dan kemudian bahagian dua, menukar nilai itu dengan elemen pertama bahagian terisih, atau unsur merah yang pertama. 

Dalam hal ini yang akan menjadi lima, jadi kami menukar satu dan lima. Apabila kita melakukan ini, kita boleh visual melihat bahawa kami telah berpindah elemen terkecil bernilai array, untuk awal-awal lagi. Berkesan menyusun elemen yang. 

Dan supaya kita memang boleh mengesahkan dan negeri yang satu, disusun. Dan dengan itu kita akan menunjukkan bahagian yang disusun pelbagai kami, dengan mewarna ia biru. 

Sekarang kita hanya mengulangi proses lagi. Mencari melalui bahagian Unsorted mudah untuk mencari elemen yang paling kecil. Dalam kes ini, ia dua. 

Kami menukar bahawa dengan yang pertama elemen bahagian terisih. Dalam kes ini dua juga berlaku untuk menjadi elemen pertama bahagian terisih. Oleh itu, kita swap dua dengan sendiri, yang benar-benar hanya meninggalkan dua di mana ia adalah, dan ia disusun. Meneruskan, kita mencari melalui untuk mencari elemen yang paling kecil. Ia adalah tiga. Kami tukar dengan yang pertama elemen, iaitu lima. Dan kini tiga disusun. 

Kami mencari melalui lagi, dan kami mencari elemen yang paling kecil adalah empat. Kami tukar dengan unsur pertama sebahagian terisih, dan kini empat disusun. 

Kami mendapati bahawa lima adalah unsur yang paling kecil. Kami tukar dengan yang pertama elemen bahagian terisih. Dan kini lima disusun. 

Dan kemudian akhir sekali, kami sebahagian terisih terdiri hanya satu unsur, jadi kami mencari melalui dan kita dapati bahawa enam adalah paling kecil, dan sebenarnya, hanya unsur. Dan kemudian kita boleh menyatakan bahawa ia disusun. Dan sekarang kita telah bertukar pelbagai kami daripada sepenuhnya terisih merah, untuk benar-benar disusun biru, menggunakan jenis pemilihan. 

Jadi apa kes yang teruk di sini? Baik dalam yang paling teruk mutlak kes, kita perlu melihat ke atas semua elemen array untuk mencari elemen terisih yang paling kecil, dan kita perlu mengulangi proses ini n masa. Sebaik sahaja untuk setiap elemen array kerana kita sahaja, dalam algoritma ini, semacam satu elemen pada satu masa. 

Apakah senario kes terbaik? Biasanya tidak sama, bukan? Kami benar-benar perlu masih melangkah melalui setiap elemen tunggal array untuk mengesahkan bahawa ia adalah, sebenarnya, elemen yang paling kecil. 

Oleh itu, kes runtime paling teruk, kita perlu mengulangi proses n kali, sekali untuk setiap n unsur-unsur. Dan dalam kes senario yang terbaik, kita perlu melakukan perkara yang sama. 

Jadi memikirkan kembali kami toolbox kerumitan pengiraan, apa yang anda fikir adalah yang paling teruk kes runtime untuk jenis pemilihan? Apa yang anda fikir adalah yang terbaik kes runtime untuk jenis pemilihan? 

Adakah anda rasa Big O n kuasa dua, dan Big Omega n kuasa dua? Anda akan menjadi betul. Mereka adalah, sebenarnya, kes yang paling teruk dan kes terbaik jangka kali, untuk jenis pemilihan. 

Saya Doug Lloyd. Ini adalah CS50.