[MUSIC PLAYING] 

Doug LLOYD: Jadi insertion sort adalah lain algoritma bisa kita gunakan untuk mengurutkan array. Ide di balik algoritma ini adalah untuk membangun array diurutkan Anda di tempat, pergeseran unsur dari cara saat Anda pergi, untuk membuat ruang. Ini sedikit berbeda dari pemilihan semacam atau gelembung semacam, misalnya, di mana kita menyesuaikan lokasi, di mana kita membuat swap. 

Dalam hal ini apa yang kita benar-benar lakukan adalah elemen geser lebih, keluar dari jalan. Bagaimana algoritma ini bekerja di pseudocode? Nah mari kita sewenang-wenang mengatakan bahwa elemen pertama dari array diurutkan. Kami sedang membangun di tempat. 

Kita akan pergi satu elemen pada suatu waktu dan membangunnya, dan hal pertama yang kita lihat adalah array satu elemen. Dan menurut definisi, satu elemen array diurutkan. 

Kemudian kita akan mengulangi proses ini until-- kita akan mengulangi proses berikut sampai semua elemen diurutkan. Lihatlah elemen disortir berikutnya dan masukkan ke bagian diurutkan, dengan menggeser jumlah yang diperlukan elemen keluar dari jalan. Semoga visualisasi ini akan membantu Anda melihat apa yang terjadi dengan insertion sort. 

Jadi sekali lagi, inilah kami seluruh array disortir, semua elemen yang ditunjukkan dengan warna merah. Dan mari kita ikuti langkah dari pseudocode kami. Hal pertama yang kita lakukan, adalah kita sebut elemen pertama dari array, diurutkan. Jadi kita hanya akan mengatakan lima, Anda sekarang diurutkan. 

Kemudian kita melihat ke depan elemen dari array disortir dan kami ingin memasukkan bahwa ke bagian diurutkan, dengan menggeser elemen lebih. Jadi keduanya adalah disortir berikutnya elemen dari array. Jelas itu milik sebelum lima, jadi apa yang akan kami lakukan adalah semacam memegang dua disisihkan untuk kedua, bergeser lima lebih, dan kemudian memasukkan dua sebelum lima, di mana untuk harus pergi. Dan sekarang kita dapat mengatakan bahwa dua diurutkan. 

Jadi seperti yang Anda lihat, kami telah hanya sejauh melihat dua elemen array. Kami belum melihat di beristirahat sama sekali, tapi kami sudah mendapat dua elemen Buruk cara mekanisme pergeseran. 

Jadi kita ulangi proses lagi. Lihatlah disortir berikutnya elemen, itu salah satu. Mari kita terus bahwa selain untuk kedua, bergeser segalanya lebih, dan menempatkan satu di mana ia harus pergi. 

Sekali lagi, masih, kami telah hanya pernah memandang satu, dua, dan lima. Kami tidak tahu apa lagi yang akan datang, tapi kami sudah diurutkan tiga unsur. 

Unsur berikutnya adalah disortir tiga, jadi kita akan sisihkan. Kami akan bergeser atas apa yang kita perlu yang, saat ini bukan segalanya seperti pada sebelumnya dua kasus, itu hanya lima. Dan kemudian kita akan tetap tiga, antara dua dan lima. 

Enam adalah berikutnya disortir elemen array. Dan pada kenyataannya enam lebih besar dari lima, sehingga kita bahkan tidak perlu melakukan swapping apapun. Kami hanya dapat taktik enam tepat ke akhir dari bagian diurutkan. 

Terakhir, empat adalah elemen disortir lalu. Jadi kita akan sisihkan, bergeser lebih unsur-unsur yang kita perlu menggeser lebih, dan kemudian menempatkan empat tempatnya. Dan sekarang lihat, kita sudah semacam dari semua elemen. Perhatikan dengan penyisipan semacam, kami tidak memiliki untuk pergi bolak-balik melintasi array. Kami hanya pergi di array satu waktu, dan kami bergeser hal-hal bahwa kita sudah dihadapi, dalam rangka untuk memberikan ruang bagi elemen baru. 

Jadi apa kasus terburuk Skenario dengan insertion sort? Dalam kasus terburuk, array dalam urutan terbalik. Anda harus menggeser masing-masing elemen n hingga posisi n, setiap kali kita tunggal membuat penyisipan. Itu banyak pergeseran. 

Dalam kasus terbaik, array sempurna diurutkan. Dan semacam seperti apa yang terjadi dengan lima dan enam dalam contoh, di mana kita bisa taktik pada tanpa harus melakukan pergeseran, kita pada dasarnya akan melakukan itu. 

Jika Anda membayangkan bahwa kami Array adalah satu sampai enam, kami akan memulai dengan menyatakan satu diurutkan. Dua datang setelah satu sehingga kita bisa hanya mengatakan, OK, baik satu dan dua diurutkan. Tiga datang setelah dua demikian, OK, satu dan dua dan tiga diurutkan. 

Kami tidak membuat swap, kami hanya bergerak baris sewenang-wenang ini antara diurutkan dan disortir seperti yang kita pergi. Seefektif yang kita lakukan pada contoh, mengubah elemen biru, seperti yang kita lanjutkan. Jadi apa kasus runtime terburuk, maka? Ingat, jika kita harus menggeser setiap elemen n mungkin posisi n, mudah-mudahan yang memberi Anda ide bahwa kasus terburuk runtime adalah O Big n kuadrat. 

Jika array adalah sempurna diurutkan, semua harus kita lakukan adalah melihat setiap elemen tunggal sekali, dan kemudian kami sudah selesai. Jadi dalam kasus terbaik, itu omega dari n. 

Aku Doug Lloyd. Ini adalah CS50.