Doug LLOYD: Jadi di CS50 kami belajar tentang berbagai memilah dan mencari algoritma. Dan kadang-kadang bisa sedikit rumit untuk menjaga melacak apa algoritma melakukan apa. Kami sudah benar-benar hanya skim permukaan juga, ada banyak pencarian lain dan algoritma pengurutan. Jadi di video ini mari kita hanya mengambil beberapa menit untuk mencoba dan menyaring setiap algoritma ke elemen inti sehingga Anda dapat mengingat paling informasi penting tentang mereka dan mampu mengartikulasikan perbedaan, jika perlu. 

Yang pertama adalah semacam seleksi. Ide dasar di balik pilihan semacam adalah menemukan elemen terkecil disortir dalam array dan swap dengan elemen disortir pertama dari array itu. Kami mengatakan bahwa kasus terburuk menjalankan waktu yang n kuadrat. Dan jika Anda ingin mengingat mengapa, mengambil a melihat pilihan semacam video. Yang terbaik-kasus jangka waktu juga n kuadrat. 

Bubble sort, ide di balik itu salah satunya adalah dengan menukar pasangan yang berdekatan. Jadi itulah kunci yang membantu Anda ingat perbedaan di sini. Seleksi semacam adalah, sejauh ini, menemukan gelembung smallest-- semacam yaitu menukar pasangan yang berdekatan. Kami bertukar pasangan yang berdekatan elemen jika mereka adalah rusak, yang secara efektif gelembung elemen yang lebih besar ke kanan, dan pada saat yang sama juga mulai untuk memindahkan elemen yang lebih kecil ke kiri. Terburuk-kasus waktu kasus run dari bubble sort adalah n kuadrat. Yang terbaik-kasus jangka waktu dari bubble sort adalah n. Karena dalam situasi yang kita tidak actually-- kita mungkin tidak perlu membuat swap sama sekali. Kami hanya perlu membuat satu lulus di semua elemen n. 

Dalam insertion sort, yang Ide dasar di sini bergeser. Itulah kata kunci untuk insertion sort. Kita akan melangkah sekali melalui array dari kiri ke kanan. Dan seperti yang kita lakukan, kita akan menggeser elemen kita sudah melihat untuk memberikan ruang bagi yang lebih kecil yang harus sesuai tempat kembali bahwa sebagian diurutkan. Jadi kami membangun array diurutkan satu elemen pada suatu waktu, kiri ke kanan, dan kita menggeser hal untuk membuat ruang. The terburuk run time dari insertion sort adalah n kuadrat. Yang terbaik-kasus berjalan waktu n. 

Menggabungkan sort-- kata kunci di sini adalah membagi dan menggabungkan. Kami membagi array penuh, apakah itu enam elemen, delapan elemen, 10.000 elements-- kita membaginya turun hingga setengahnya, setengahnya, setengahnya, sampai kita memiliki array yang di bawah n satu elemen array. Satu set n satu elemen array. Jadi kita mulai dengan satu Array 1.000-elemen, dan kami sampai ke titik di mana kita memiliki 1.000 array satu-elemen. Kemudian kita mulai untuk menggabungkan mereka sub array kembali bersama-sama dalam urutan yang benar. Jadi kami mengambil dua array satu-elemen dan membuat array dua-elemen. Kami mengambil dua array dua-elemen dan membuat array empat-elemen dan seterusnya dan seterusnya sampai kita sudah lagi dibangun kembali satu array elemen n. 

The terburuk run time dari menggabungkan semacam yaitu n kali log n. Kami memiliki n elemen, tetapi proses recombining ini Dibutuhkan log n langkah-langkah untuk mendapatkan kembali ke array penuh. Kasus terbaik menjalankan waktu juga n log n karena proses ini tidak benar-benar peduli apakah array adalah diurutkan atau tidak untuk memulai dengan. Proses ini sama, ada ada cara untuk hal hubungan pendek. Jadi n log n dalam kasus terburuk, n log n dalam kasus terbaik. 

Kami berbicara tentang dua algoritma pencarian. Jadi pencarian linear adalah tentang iterasi. Kami melanjutkan di array sekali, dari kiri ke kanan, mencoba untuk menemukan nomor bahwa kita sedang mencari. The terburuk waktu berjalan adalah O besar n. Mungkin membawa kita iterasi di setiap elemen tunggal untuk menemukan elemen yang kita cari untuk, baik di posisi terakhir, atau tidak sama sekali. Tapi kita tidak bisa mengkonfirmasi bahwa sampai kita telah melihat segalanya. m kasus terbaik, kita menemukan segera. Yang terbaik-kasus run time dari pencarian linear adalah omega dari 1. 

Terakhir, ada pencarian biner, yang membutuhkan berbagai macam array. Ingat itu sangat pertimbangan penting ketika bekerja dengan pencarian biner. Ini prasyarat untuk menggunakan itu-- array yang Anda cari melalui harus dipilah. Jika tidak, kata kunci adalah membagi dan menaklukkan. Membagi array menjadi setengah dan menghilangkan setengah dari elemen setiap kali Anda melanjutkan melalui. Karena membagi ini dan menaklukkan dan hal membelah dua pendekatan, yang terburuk run time dari pencarian biner adalah log n, yang secara substansial lebih baik daripada pencarian linear ini n. Yang terbaik-kasus berjalan waktu masih salah. 

Kami mungkin akan segera pertama kali kita membuat divisi, tapi, lagi, ingat bahwa meskipun pencarian biner adalah jauh lebih baik dibandingkan pencarian linear berdasarkan menjadi log n terhadap n, Anda mungkin harus melalui pekerjaan penyortiran array pertama, yang mungkin membuatnya kurang efektif tergantung pada ukuran dari iterasi diurutkan. 

Aku Doug Lloyd, ini CS50.