[Powered by Google Translate] [Sortir Penyisipan]
[Tommy MacWilliam] [Harvard University]
[Ini adalah CS50.TV]
Mari kita lihat insertion sort, algoritma untuk mengambil daftar nomor dan menyortir mereka.
Sebuah algoritma, ingat, hanyalah sebuah prosedur langkah-demi-langkah untuk menyelesaikan suatu tugas.
Ide dasar dibalik insertion sort, adalah untuk membagi daftar kami menjadi dua bagian,
sebagian diurutkan dan bagian unsorted.
>> Pada setiap langkah algoritma, nomor tersebut akan dipindahkan
dari bagian unsorted ke bagian diurutkan
sampai akhirnya seluruh daftar yang diurutkan.
Berikut adalah daftar dari enam nomor disortir - 23, 42, 4, 16, 8, dan 15.
Karena angka-angka ini tidak semua dalam urutan, mereka unsorted.
Karena kita belum mulai menyortir lagi, kami akan mempertimbangkan semua enam elemen sebagian unsorted kami.
>> Setelah kita mulai menyortir, kita akan menempatkan angka-angka diurutkan di sebelah kiri ini.
Jadi, mari kita mulai dengan 23, elemen pertama dalam daftar kami.
Kami tidak memiliki unsur-unsur dalam porsi kami belum diurutkan,
jadi mari kita hanya mempertimbangkan 23 menjadi awal dan akhir dari bagian kami diurutkan.
Sekarang, sebagian kami diurutkan memiliki satu nomor, 23,
dan bagian unsorted kami memiliki lima angka.
Sekarang mari kita masukkan nomor berikutnya di bagian unsorted kami,, 42 ke bagian diurutkan.
>> Untuk melakukannya, kita harus membandingkan 42 ke 23 - satu-satunya unsur dalam porsi kami diurutkan sejauh ini.
Empat puluh dua lebih besar dari 23, sehingga kita hanya dapat menambahkan 42 sampai akhir
dari bagian diurutkan dari daftar. Great!
Sekarang bagian kami diurutkan memiliki dua elemen, dan bagian unsorted kami memiliki empat elemen.
Jadi, mari kita sekarang pindah ke 4, elemen berikutnya di bagian unsorted.
Jadi, di mana hal ini harus ditempatkan di bagian diurutkan?
>> Ingat, kita ingin menempatkan nomor ini dalam rangka diurutkan
sehingga porsi kami diurutkan tetap benar diurutkan setiap saat.
Jika kita menempatkan 4 di sebelah kanan dari 42, maka daftar kami akan rusak.
Jadi, mari kita terus bergerak kanan-ke-kiri di bagian semacam kami.
Ketika kita bergerak, mari kita bergeser ke setiap nomor tempat untuk memberikan ruang bagi nomor baru.
Oke, 4 juga kurang dari 23, jadi kami tidak dapat menempatkan di sini baik.
Mari kita memindahkan 23 tepat satu tempat.
>> Itu berarti kita ingin menempatkan 4 ke dalam slot pertama di bagian diurutkan.
Perhatikan bagaimana ruang ini dalam daftar itu sudah kosong,
karena kami sudah bergerak elemen diurutkan turun seperti yang kita temui mereka.
Baiklah. Jadi, kami setengah jalan di sana.
Mari kita lanjutkan algoritma kami dengan memasukkan 16 ke bagian diurutkan.
Enam belas kurang dari 42, jadi mari kita menggeser ke kanan 42.
Enam belas juga kurang dari 23, jadi mari kita juga menggeser elemen.
>> Sekarang, 16 lebih besar dari 4. Jadi, sepertinya kita ingin memasukkan 16 antara 4 dan 23.
Sementara bergerak melalui bagian diurutkan daftar dari kanan ke kiri,
4 adalah angka pertama kita lihat yang lebih kecil dari jumlah
kami mencoba untuk memasukkan.
Jadi, sekarang kita bisa memasukkan 16 ke slot yang kosong ini,
yang, ingat, kami telah diciptakan oleh elemen bergerak di bagian atas semacam
seperti yang kita temui mereka.
>> Baiklah. Sekarang, kami memiliki empat elemen diurutkan dan dua elemen unsorted.
Jadi, mari kita memindahkan 8 ke bagian diurutkan.
Delapan kurang dari 42.
Delapan kurang dari 23.
Dan 8 adalah kurang dari 16.
Tapi 8 lebih besar dari 4.
Jadi, kami ingin memasukkan 8 antara 4 dan 16.
Dan sekarang kita hanya memiliki satu elemen yang tersisa untuk memilah - 15.
Lima belas kurang dari 42,
Lima belas kurang dari 23.
Dan 15 adalah kurang dari 16.
Tapi 15 lebih besar dari 8.
>> Jadi, di sini adalah di mana kita ingin membuat penyisipan akhir kami.
Dan kita sudah selesai.
Kami tidak memiliki elemen lebih di bagian unsorted,
dan bagian kami diurutkan dalam urutan yang benar.
Angka-angka yang dipesan dari terkecil sampai terbesar.
Jadi, mari kita lihat beberapa pseudocode yang menggambarkan langkah-langkah kita hanya dilakukan.
>> On line 1, kita dapat melihat bahwa kita harus iterate atas setiap elemen dalam daftar
kecuali yang pertama, sejak elemen pertama di bagian unsorted hanya akan menjadi
elemen pertama di bagian diurutkan.
Pada baris 2 dan 3, kita melacak tempat kami saat ini di bagian unsorted.
Elemen merupakan jumlah kami sedang bergerak ke bagian diurutkan,
dan j merupakan indeks kami ke bagian unsorted.
>> On line 4, kita iterasi melalui bagian diurutkan dari kanan ke kiri.
Kami ingin menghentikan iterasi sekali elemen di sebelah kiri posisi kita saat ini
kurang dari elemen kita mencoba untuk memasukkan.
Pada baris 5, kita menggeser setiap elemen yang kita temui satu ruang ke kanan.
Dengan begitu, kita akan memiliki ruang yang jelas untuk memasukkan ke dalam ketika kita menemukan elemen pertama
kurang dari elemen kita bergerak.
On line 6, kami meng-update counter kami untuk terus bergerak ke kiri melalui bagian diurutkan.
Akhirnya, pada baris 7, kita memasukkan elemen ke bagian diurutkan dari daftar.
>> Kita tahu bahwa tidak apa-apa untuk memasukkan ke posisi j,
karena kita sudah pindah elemen yang digunakan untuk berada di sana satu ruang ke kanan.
Ingat, kita bergerak melalui bagian diurutkan dari kanan ke kiri,
tapi kami bergerak melalui bagian unsorted dari kiri ke kanan.
Baiklah. Mari sekarang kita lihat berapa lama berjalan yang mengambil algoritma.
Kami pertama-tama akan bertanya berapa lama waktu yang diperlukan untuk algoritma ini berjalan dalam kasus terburuk.
Ingatlah bahwa kita mewakili kali ini berjalan dengan notasi Big O.
Untuk menyelesaikan daftar kami, kami harus iterate atas unsur-unsur di bagian unsorted,
dan untuk masing-masing elemen, berpotensi atas seluruh elemen di bagian diurutkan.
Secara intuitif, ini terdengar seperti operasi (n ^ 2) O.
>> Melihat pseudocode kami, kami memiliki loop bersarang di dalam loop lain,
yang, memang, terdengar seperti sebuah operasi (n ^ 2) O.
Namun, bagian diurutkan daftar tidak mengandung seluruh daftar sampai akhir.
Namun, kita berpotensi bisa memasukkan unsur baru pada awal dari bagian diurutkan
pada setiap iterasi algoritma,
yang berarti bahwa kita harus melihat setiap elemen saat ini di bagian diurutkan.
Jadi, itu berarti kita berpotensi bisa membuat satu perbandingan untuk elemen kedua,
dua perbandingan untuk elemen ketiga, dan seterusnya.
Jadi, jumlah langkah adalah jumlah dari bilangan bulat dari 1 sampai panjang daftar dikurangi 1.
Kita bisa mewakili ini dengan penjumlahan.
>> Kami tidak akan masuk ke penjumlahan di sini, tapi ternyata bahwa penjumlahan ini sama dengan
n (n - 1) lebih dari 2, yang adalah n setara ^ 2/2 - n / 2.
Ketika berbicara tentang runtime asimtotik,
ini n ^ 2 istilah yang akan mendominasi istilah n.
Jadi, insertion sort adalah Big O (n ^ 2).
Bagaimana jika kita berlari insertion sort pada daftar yang sudah diurutkan.
Dalam hal ini, kita hanya akan membangun bagian diurutkan dari kiri ke kanan.
Jadi, kita hanya perlu pada urutan langkah n.
>> Itu berarti bahwa insertion sort memiliki performa terbaik-kasus n,
yang kami mewakili dengan Ω (n).
Dan itu untuk insertion sort,
hanya salah satu dari banyak algoritma yang bisa kita gunakan untuk mengurutkan daftar.
Nama saya Tommy, dan ini adalah CS50.
[CS50.TV]
Oh, Anda tidak bisa berhenti bahwa setelah dimulai.
Oh, kami melakukan itu - Boom >>!