[Powered by Google Translate] [Insertion Sort] [Tommy MacWilliam] [Universiti Harvard] [Ini adalah CS50.TV] Mari kita lihat pada apapun kemasukan, algoritma untuk mengambil senarai nombor dan menyusun mereka. Algoritma, ingat, hanya satu prosedur langkah-demi-langkah untuk mencapai tugas. Idea asas di sebalik jenis kemasukan, adalah untuk membahagikan senarai kami ke dalam dua bahagian, sebahagian disusun dan bahagian Unsorted. 

Pada setiap langkah algoritma, nombor berpindah dari bahagian Unsorted untuk bahagian disusun sehingga akhirnya seluruh senarai diisih. Berikut adalah senarai enam nombor Unsorted - 23, 42, 4, 16, 8, dan 15. Sejak nombor-nombor ini tidak semua dalam tertib menaik, mereka Unsorted. Kerana kita telah tidak mula sorting lagi, kita akan mempertimbangkan kesemua enam elemen bahagian Unsorted kami. 

Sebaik sahaja kita mula menyusun, kami akan meletakkan nombor-nombor yang disusun di sebelah kiri ini. Jadi, mari kita mulakan dengan 23, elemen pertama dalam senarai kami. Kami tidak mempunyai sebarang unsur-unsur di bahagian disusun kami lagi, jadi mari kita hanya mempertimbangkan 23 hingga menjadi permulaan dan akhir bahagian disusun kami. Sekarang, bahagian kami disusun mempunyai satu nombor, 23, dan bahagian Unsorted kami mempunyai kelima-lima nombor. Mari kita kini memasukkan nombor seterusnya dalam bahagian Unsorted kami, 42, ke bahagian disusun. 

Untuk berbuat demikian, kita akan perlu untuk membandingkan 42 hingga 23 - elemen hanya di bahagian disusun kami setakat ini. Empat puluh dua adalah lebih besar daripada 23, jadi kita hanya boleh menambah 42 hingga akhir bahagian disusun senarai. Hebat! Sekarang bahagian kami disusun mempunyai dua unsur, dan bahagian Unsorted kami mempunyai empat unsur. Jadi, mari kita kini bergerak ke 4, elemen seterusnya dalam bahagian Unsorted. Jadi, di mana ini harus diletakkan di bahagian disusun? 

Ingat, kita mahu meletakkan nombor ini dalam usaha disusun jadi bahagian kita disusun kekal disusun dengan betul pada setiap masa. Jika kita meletakkan 4, ke kanan daripada 42, maka senarai kami akan keluar perintah. Jadi, mari kita terus bergerak ke kanan-ke-kiri di bahagian apapun kami. Seperti yang kita bergerak, mari kita beralih setiap nombor ke tempat untuk membuat ruang untuk nombor baru. Okay, 4 adalah juga kurang daripada 23, jadi kita tidak boleh meletakkan di sini sama ada. Mari kita bergerak 23 betul satu tempat. 

Ini bermakna kita ingin meletakkan 4, ke dalam slot yang pertama di bahagian disusun. Perhatikan bagaimana ruang ini dalam senarai sudah kosong, kerana kita telah bergerak disusun unsur-unsur seperti yang kita temui mereka. Semua hak. Jadi, kita sudah separuh di sana. Mari kita terus algoritma kami dengan memasukkan 16 ke bahagian disusun. Sixteen adalah kurang dari 42, jadi mari kita beralih daripada 42 ke kanan. Sixteen juga kurang dari 23, jadi mari kita juga beralih elemen yang. 

Sekarang, 16 adalah lebih besar daripada 4. Jadi, ia kelihatan seperti kita ingin memasukkan 16 antara 4 dan 23. Walaupun bergerak melalui bahagian disusun senarai dari kanan ke kiri, 4 adalah nombor pertama kita telah melihat yang lebih kecil daripada bilangan kita sedang berusaha untuk memasukkan. Jadi, sekarang kita boleh memasukkan 16 ke dalam slot ini kosong, ingat, kita telah dicipta oleh unsur-unsur yang bergerak di bahagian apapun lebih seperti yang kita temui mereka. 

Semua hak. Sekarang, kita mempunyai empat unsur-unsur disusun dan dua elemen Unsorted. Jadi, mari kita menggerakkan 8 ke bahagian disusun. Lapan adalah kurang daripada 42. Lapan adalah kurang daripada 23. Dan 8 adalah kurang daripada 16. Tetapi 8 adalah lebih besar daripada 4. Jadi, kami ingin untuk memasukkan 8 antara 4 dan 16 yang. Dan sekarang kita hanya mempunyai satu elemen yang lebih ditinggalkan untuk menyusun - 15 hingga. Lima belas adalah kurang daripada 42, Lima belas adalah kurang daripada 23. Dan 15 adalah kurang daripada 16. Tetapi 15 adalah lebih besar daripada 8. 

Jadi, di sini adalah di mana kita mahu untuk membuat kemasukan akhir kami. Dan kami sudah selesai. Kami tidak mempunyai unsur-unsur yang lebih dalam bahagian Unsorted, dan bahagian kami disusun dalam susunan yang betul. Nombor disusun daripada yang terkecil hingga terbesar. Jadi, mari kita melihat pseudokod beberapa yang menerangkan langkah-langkah yang kita hanya dilakukan. 

On line 1, kita dapat melihat bahawa kita perlukan untuk melelar atas setiap elemen dalam senarai kecuali yang pertama, kerana elemen yang pertama dalam bahagian Unsorted hanya akan menjadi elemen pertama dalam bahagian disusun. Pada baris 2 dan 3, kami sedang mengesan tempat semasa kami di bahagian Unsorted. Unsur mewakili bilangan yang kita sedang bergerak ke bahagian disusun, dan j mewakili indeks kami ke bahagian Unsorted. 

On line 4, kita iterating melalui bahagian yang disusun dari kanan ke kiri. Kami mahu menghentikan iterating sekali unsur ke kiri kedudukan semasa kami adalah kurang daripada elemen yang kita sedang berusaha untuk memasukkan. Pada baris 5, kita beralih setiap elemen kita menghadapi satu ruang ke kanan. Cara itu, kita akan mempunyai ruang yang jelas untuk memasukkan ke dalam apabila kita dapati elemen pertama kurang daripada elemen yang kita sedang bergerak. On line 6, kami sedang mengemaskini kaunter kami untuk terus bergerak kiri melalui bahagian disusun. Akhirnya, on line 7, kita sedang memasukkan unsur ke bahagian disusun senarai. 

Kita tahu bahawa ia adalah ok untuk masukkan ke dalam kedudukan j, kerana kita sudah berpindah elemen yang digunakan untuk berada di sana satu ruang ke kanan. Ingat, kita sedang bergerak melalui bahagian yang disusun dari kanan ke kiri, tetapi kita bergerak melalui bahagian Unsorted dari kiri ke kanan. Semua hak. Mari kita kini mengambil melihat berapa lama berjalan bahawa algoritma mengambil. Kita mula-mula akan bertanya soalan berapa lama ia mengambil masa untuk algoritma ini untuk menjalankan dalam kes terburuk. Ingatlah bahawa kita mewakili kali ini berjalan dengan notasi O Big. Dalam usaha untuk menyusun senarai kami, kami terpaksa untuk melelar lebih unsur-unsur di bahagian Unsorted, dan bagi setiap unsur-unsur, yang berpotensi ke atas semua unsur dalam bahagian disusun. Intuitif, ini bunyi seperti operasi O (n ^ 2). 

Melihat pseudokod kita, kita mempunyai gelung bersarang di dalam gelung lain, yang, sememangnya, bunyi seperti operasi O (n ^ 2). Walau bagaimanapun, bahagian yang disusun senarai tidak mengandungi senarai keseluruhan sehingga akhir sangat. Namun, kita berpotensi memasukkan elemen baru pada awal-awal bahagian disusun pada setiap lelaran algoritma, yang bermaksud bahawa kita akan perlu untuk melihat setiap elemen kini dalam bahagian disusun. Jadi, ini bermakna kita berpotensi membuat satu perbandingan untuk elemen kedua, dua perbandingan bagi unsur ketiga, dan sebagainya. Jadi, jumlah langkah-langkah adalah jumlah integer dari 1 hingga panjang senarai tolak 1. Kita boleh mewakili ini dengan penjumlahan. 

Kami tidak akan pergi ke dalam penjumlahan di sini, tetapi ia ternyata bahawa penjumlahan ini adalah sama dengan n (n - 1) lebih dari 2, yang bersamaan n ^ 2/2 - n / 2. Apabila bercakap tentang runtime asimptot, ini n ^ 2 istilah itu akan menguasai istilah ini n. Jadi, apapun kemasukan adalah Big O (n ^ 2). Bagaimana jika kita berlari apapun kemasukan dalam senarai yang sudah disusun. Dalam kes itu, kita hanya mahu membina bahagian yang disusun dari kiri ke kanan. Jadi, kita hanya perlukan atas perintah langkah n. 

Ini bermakna bahawa apapun kemasukan mempunyai prestasi terbaik kes n, yang kita mewakili Ω (n). Dan itulah ia untuk menyelesaikan kemasukan, hanya salah satu daripada banyak algoritma yang boleh kita gunakan untuk menyusun senarai. Nama saya adalah Tommy, dan ini adalah CS50. [CS50.TV] Oh, anda hanya tidak boleh menghentikan bahawa apabila ia bermula. Oh, kita lakukan bahawa - >> Boom!