[MUSIC PLAYING] Doug LLOYD: Seleksi semacam adalah algoritma yang, seperti yang Anda harapkan, macam satu set elemen. Dan algoritma recall adalah langkah-demi-langkah set instruksi untuk menyelesaikan tugas. 

Dalam seleksi mengurutkan Ide dasarnya adalah ini, menemukan elemen terkecil dan disortir menambahkannya ke akhir daftar diurutkan. Efektif apa yang dilakukan adalah membangun daftar diurutkan, salah satu elemen pada suatu waktu. Memecahnya ke pseudocode kita bisa menyatakan algoritma ini sebagai berikut, ulangi ini sampai tidak ada unsur disortir tetap. Cari melalui disortir Data untuk mencari nilai terkecil, kemudian swap nilai terkecil dengan elemen pertama dari bagian yang tidak dipisahkan. 

Ini dapat membantu untuk memvisualisasikan ini, jadi mari kita lihat ini. Jadi ini, saya berpendapat, adalah Array disortir dan saya sudah ditunjukkan dengan menunjukkan bahwa semua dari unsur-unsur yang berwarna merah, mereka belum diurutkan. Ini adalah seluruh yang disortir bagian dari array. 

Jadi mari kita pergi melalui langkah-langkah Temukan sort untuk mengurutkan array ini. Jadi sekali lagi, kita akan ulangi sampai tidak ada unsur disortir tetap. Kita akan cari melalui Data untuk mencari nilai terkecil, dan kemudian menukar bahwa nilai dengan elemen pertama dari bagian yang tidak dipisahkan. 

Sekarang, sekali lagi, seluruh yang Array adalah bagian yang tidak dipisahkan. Semua elemen merah disortir. Jadi kita mencari melalui dan kita menemukan nilai terkecil. Kami mulai dari awal, kita pergi ke akhir, kita menemukan nilai terkecil adalah, salah satu. Jadi itu bagian satu. Dan kemudian bagian dua, menukar yang nilai dengan elemen pertama dari bagian disortir, atau elemen merah pertama. 

Dalam hal ini yang akan lima, jadi kami bertukar satu dan lima. Ketika kita melakukan ini, kita bisa visual melihat bahwa kami telah pindah elemen terkecil dihargai dari array, untuk awal. Efektif menyortir elemen. 

Dan jadi kita memang bisa mengkonfirmasi dan negara yang satu, diurutkan. Dan jadi kita akan menunjukkan bagian diurutkan dari array kita, dengan mewarnai biru. 

Sekarang kita hanya mengulang proses lagi. Kami mencari melalui bagian disortir dari array untuk menemukan elemen terkecil. Dalam hal ini, itu dua. 

Kami menukar bahwa dengan yang pertama unsur bagian yang tidak dipisahkan. Dalam hal ini dua juga terjadi menjadi elemen pertama dari bagian yang tidak dipisahkan. Jadi kita menukar dua dengan dirinya sendiri, yang benar-benar hanya meninggalkan dua mana itu, dan itu diurutkan. Melanjutkan, kami mencari melalui untuk menemukan elemen terkecil. Ini tiga. Kami swap dengan yang pertama elemen, yaitu lima. Dan sekarang tiga diurutkan. 

Kami mencari melalui lagi, dan kami menemukan elemen terkecil adalah empat. Kami swap dengan elemen pertama dari bagian disortir, dan sekarang empat diurutkan. 

Kami menemukan bahwa lima adalah elemen terkecil. Kami swap dengan yang pertama unsur bagian yang tidak dipisahkan. Dan sekarang lima diurutkan. 

Dan kemudian terakhir, kami bagian disortir terdiri hanya satu elemen, jadi kami mencari melalui dan kami menemukan bahwa enam adalah terkecil, dan pada kenyataannya, hanya elemen. Dan kemudian kita dapat menyatakan bahwa itu diurutkan. Dan sekarang kami sudah beralih array kita dari yang benar-benar unsorted merah, untuk benar-benar diurutkan warna biru, menggunakan semacam seleksi. 

Jadi apa skenario terburuk di sini? Baik di terburuk mutlak kasus, kita harus melihat lebih semua elemen dari array untuk menemukan elemen disortir terkecil, dan kami harus mengulangi Proses ini n kali. Sekali untuk setiap elemen dari array karena kita hanya, dalam algoritma ini, semacam satu elemen pada waktu. 

Apa skenario kasus terbaik? Baik itu persis sama, kan? Kami benar-benar harus tetap melangkah melalui setiap elemen dari array untuk mengkonfirmasi bahwa itu adalah, pada kenyataannya, elemen terkecil. 

Jadi kasus runtime terburuk, kami harus mengulangi proses n kali, sekali untuk setiap elemen n. Dan dalam skenario kasus terbaik, kita harus melakukan hal yang sama. 

Jadi berpikir kembali ke kami komputasi toolbox kompleksitas, apa yang Anda pikirkan adalah yang terburuk kasus runtime untuk seleksi semacam? Apa yang Anda pikirkan adalah yang terbaik kasus runtime untuk seleksi semacam? 

Apakah Anda menebak Big O n kuadrat, dan Big Omega n kuadrat? Anda akan benar. Mereka adalah, pada kenyataannya, kasus terburuk dan kasus terbaik run kali, untuk seleksi semacam. 

Aku Doug Lloyd. Ini adalah CS50.