>> [MUSIC PLAYING]
>> Doug LLOYD: OK, jadi penggabungan semacam belum algoritma lain
yang bisa kita gunakan untuk memilah elemen array.
Tapi seperti yang kita akan lihat, itu punya perbedaan yang sangat mendasar
dari pemilihan semacam, bubble macam, dan insertion sort
yang membuatnya benar-benar cukup pintar.
>> Ide dasar di balik merge semacam ini untuk mengurutkan array yang lebih kecil
dan kemudian menggabungkan mereka array bersama-sama, atau menggabungkan them--
maka name-- untuk disortir.
Cara menggabungkan semacam tidak ini adalah dengan memanfaatkan alat
disebut rekursi, yang adalah apa yang kita akan berbicara tentang segera,
tapi kita belum benar-benar berbicara tentang belum.
>> Berikut ide dasar di balik merge sort.
Urutkan kiri setengah dari array, asumsi n lebih besar dari 1.
Dan apa yang saya maksud ketika saya mengatakan asumsi n lebih besar dari 1 adalah,
Saya pikir kita bisa setuju bahwa jika sebuah array hanya terdiri dari satu elemen,
itu diurutkan.
Kami tidak benar-benar perlu melakukan apapun untuk itu.
Kami hanya dapat mendeklarasikan akan diurutkan.
Ini hanya satu elemen.
>> Jadi pseudocode, sekali lagi, adalah mengurutkan setengah kiri dari array,
kemudian mengurutkan bagian kanan array, kemudian menggabungkan dua bagian bersama-sama.
Sekarang, Anda mungkin sudah berpikir, itu jenis hanya
Kedengarannya seperti Anda menunda the-- Anda tidak benar-benar melakukan apa-apa.
Anda mengatakan menyortir kiri setengah, mengurutkan bagian kanan,
tapi kau tidak mengatakan saya bagaimana Anda melakukannya.
>> Tapi ingat bahwa selama array adalah elemen tunggal,
kita dapat mendeklarasikan diurutkan.
Maka kita bisa menggabungkan mereka bersama-sama.
Dan itulah sebenarnya Ide dasar di balik semacam penggabungan,
adalah untuk memecahnya sehingga array Anda adalah ukuran satu.
Dan kemudian Anda kembali dari sana.
>> Menggabungkan semacam pasti algoritma yang rumit.
Dan itu juga sedikit rumit untuk memvisualisasikan.
Jadi mudah-mudahan, visualisasi yang saya miliki di sini akan membantu Anda mengikuti bersama.
Dan aku akan mencoba yang terbaik untuk menceritakan hal-hal dan melanjutkan melalui ini lebih sedikit
lambat dari yang lain hanya untuk mudah-mudahan mendapatkan kepala Anda
sekitar ide dibalik merge sort.
>> Jadi kita memiliki array sama dengan video algoritma sorting lainnya
jika Anda pernah melihat them-- array enam elemen.
Dan kode pseudo kami di sini adalah semacam kiri setengah, mengurutkan bagian kanan,
menggabungkan dua bagian bersama-sama.
Jadi mari kita bata merah ini sangat gelap array dan mengurutkan setengah kiri itu.
>> Jadi untuk saat ini, kita akan mengabaikan hal-hal di sebelah kanan.
Itu ada, tapi kami tidak pada langkah belum.
Kami tidak di semacam itu kanan setengah dari array.
Kami berada di semacam kiri setengah dari array.
Dan hanya demi menjadi sedikit lebih
jelas, jadi saya dapat merujuk apa langkah kita berada di,
Aku akan mengganti warna set ini untuk oranye.
Sekarang, kita masih berbicara tentang kiri setengah sama array asli.
Tapi aku berharap bahwa dengan mampu mengacu pada warna dari berbagai item,
itu akan membuatnya sedikit lebih jelas apa yang terjadi di sini.
>> OK, jadi sekarang kita memiliki tiga elemen array.
Bagaimana kita mengurutkan setengah kiri ini array, yang masih langkah ini?
Kami mencoba untuk memilah kiri setengah dari bata merah array--
kiri setengah dari yang Saya sekarang sudah berwarna oranye.
>> Nah, kita bisa mencoba dan ulangi proses ini lagi.
Jadi kita masih di tengah berusaha untuk menyortir
kiri setengah dari array penuh.
Kiri setengah dari array, aku hanya akan
untuk sewenang-wenang memutuskan bahwa setengah kiri akan lebih kecil dari bagian kanan,
karena hal ini terjadi pada terdiri dari tiga elemen.
>> Dan jadi saya akan mengatakan bahwa kiri setengah dari kiri setengah array
hanya elemen lima.
Lima, menjadi satu elemen array, kita tahu bagaimana mengatasinya.
Dan lima diurutkan.
Kami hanya akan menyatakan bahwa.
Ini array elemen tunggal.
>> Jadi sekarang kami telah diurutkan kiri setengah dari half-- kiri
atau lebih tepatnya, kami telah diurutkan kiri setengah dari jeruk.
Jadi sekarang, untuk masih lengkap kiri setengah array keseluruhan itu,
kita perlu memilah bagian kanan dari jeruk, atau hal-hal ini.
Bagaimana kita melakukannya?
Nah, kita memiliki array dua elemen.
Jadi kita dapat menyusun setengah kiri dari array, yang merupakan dua.
Dua adalah elemen tunggal.
Jadi itu diurutkan secara default. Kemudian kita bisa memilah bagian kanan
yang bagian dari array, satu.
Itu semacam secara default.
>> Ini adalah pertama kalinya sekarang kami telah mencapai langkah penggabungan.
Kami telah selesai, meskipun kita sekarang jenis bersarang down--
dan itu semacam rumit Hal dengan rekursi adalah,
Anda perlu menjaga Anda kepala tentang di mana kita berada.
Jadi kita sudah semacam kiri setengah dari porsi jeruk.
>> Dan sekarang, kita berada di tengah-tengah menyortir kanan setengah dari porsi jeruk.
Dan dalam proses itu, kita sekarang akan berada di langkah,
menggabungkan dua bagian bersama-sama.
Ketika kita melihat dua bagian dari array, kita melihat dua dan satu.
Yang elemen lebih kecil?
Satu.
>> Kemudian yang elemen lebih kecil?
Nah, itu dua atau tidak.
Jadi dua.
Jadi sekarang, hanya untuk membingkai lagi di mana kita berada dalam konteks,
kami telah diurutkan kiri setengah dari jeruk
dan bagian kanan asal.
Aku tahu aku sudah berubah warna lagi, tapi itu di mana kita berada.
Dan alasan saya melakukan ini karena proses ini
akan terus, iterasi turun.
Kami telah diurutkan kiri setengah dari mantan orange
dan kanan setengah dari mantan oranye.
>> Sekarang, kita perlu menggabungkan mereka dua bagian bersama-sama juga.
Itulah langkah kami di.
Jadi kita mempertimbangkan semua elemen yang sekarang hijau,
kiri setengah dari array asli.
Dan kami gabungkan menggunakan proses yang sama
kami lakukan untuk penggabungan dua dan satu hanya beberapa saat yang lalu.
>> Kiri setengah, yang terkecil elemen pada kiri setengah lima.
Elemen terkecil pada bagian kanan adalah salah satu.
Mana yang lebih kecil?
Satu.
>> Elemen terkecil pada kiri setengah lima.
Elemen terkecil pada kanan setengah dua.
Apa yang terkecil?
Dua.
Dan kemudian terakhir lima dan apa-apa, kita dapat mengatakan lima.
>> OK, gambar begitu besar, mari kita istirahat untuk kedua
dan mencari tahu di mana kita berada.
Jika kita mulai dari awal, kami
sekarang telah diselesaikan untuk array secara keseluruhan hanya
satu langkah dari kode pseudocode sini.
Kami telah diurutkan kiri setengah dari array.
>> Ingat bahwa asli Agar lima, dua, satu.
Dengan pergi melalui proses ini dan bersarang ke bawah dan mengulangi,
terus memecahkan masalah ke dalam bagian yang lebih kecil dan lebih kecil,
kita sekarang telah menyelesaikan langkah salah pseudocode
untuk seluruh array awal.
Kami telah diurutkan setengah kiri.
>> Jadi sekarang mari kita membeku di sana.
Dan sekarang mari kita mengurutkan kanan setengah dari array asli.
Dan kita akan melakukannya dengan akan melalui iterasi yang sama
Proses melanggar segalanya dan kemudian menggabungkan mereka bersama-sama.
>> Jadi kiri setengah dari merah, atau setengah kiri
dari kanan setengah dari aslinya array, saya akan katakan adalah tiga.
Sekali lagi, aku bersikap konsisten di sini.
Jika Anda memiliki aneh jumlah elemen, itu
tidak benar-benar peduli apakah Anda membuat satu kiri lebih kecil
atau hak yang lebih kecil.
>> Yang penting adalah bahwa setiap kali Anda menghadapi masalah ini dalam melakukan
gabungan, Anda harus konsisten.
Anda juga harus selalu membuat sisi kiri lebih kecil
atau selalu perlu membuat sisi kanan yang lebih kecil.
Di sini, saya telah memilih untuk selalu membuat sisi kiri lebih kecil
ketika array saya, atau saya sub-array, adalah ukuran yang aneh.
>> Tiga adalah satu elemen, dan karena itu diurutkan.
Kami telah memanfaatkan asumsi bahwa sepanjang seluruh proses kami sejauh ini.
Jadi sekarang mari kita mengurutkan kanan setengah dari setengah benar,
atau bagian kanan merah.
>> Sekali lagi, kita perlu untuk membagi ini turun.
Ini bukan array elemen tunggal.
Kita tidak bisa menyatakan itu diurutkan.
Dan jadi pertama, kita akan memilah kiri setengah.
>> Setengah kiri adalah elemen tunggal, jadi semacam secara default.
Kemudian kita akan mengurutkan kanan setengah, yang merupakan elemen tunggal.
Ini diurutkan secara default. Dan sekarang, kita bisa menggabungkan dua bersama-sama.
Empat lebih kecil, dan kemudian enam lebih kecil.
>> Sekali lagi, apa yang telah kita lakukan pada saat ini?
Kami telah diurutkan kiri setengah dari setengah benar.
Atau akan kembali ke aslinya warna yang ada,
kami telah diurutkan kiri setengah dari merah lembut.
Awalnya batu bata gelap merah dan sekarang itu lebih lembut merah,
atau itu merah lembut.
>> Dan kemudian kami telah diurutkan setengah kanan merah lembut.
Sekarang, baik, mereka hijau lagi, hanya karena kita akan melalui sebuah proses.
Dan kita harus mengulang ini berulang.
>> Jadi sekarang kita bisa menggabungkan mereka dua bagian bersama-sama.
Dan itulah yang kami lakukan di sini.
Jadi garis hitam hanya dibagi kiri setengah
dan kanan setengah dari semacam bagian ini.
>> Kami membandingkan nilai terkecil di sisi kiri array-- yang
atau permisi, terkecil nilai kiri setengah
dengan nilai terkecil dari kanan setengah dan menemukan bahwa tiga lebih kecil.
Dan sekarang sedikit optimasi, kan?
Sebenarnya ada apa-apa kiri di sisi kiri.
>> Tidak ada yang tersisa di sisi kiri,
sehingga kita bisa efisien hanya move-- kita dapat mendeklarasikan
sisanya sebenarnya diurutkan dan hanya taktik itu
pada, karena tidak ada lain untuk membandingkan terhadap.
Dan kita tahu bahwa sisi kanan dari sisi kanan diurutkan.
>> OK, jadi sekarang mari kita membekukan lagi dan mencari tahu di mana kita berada dalam cerita.
Dalam array secara keseluruhan, apa yang telah kita capai?
Kami benar-benar telah mencapai sekarang langkah satu dan langkah dua.
Kami diurutkan kiri setengah, dan kami diurutkan kanan setengah.
>> Jadi sekarang, semua yang tersisa adalah bagi kita untuk menggabungkan dua bagian bersama-sama.
Jadi kita membandingkan termurah dihargai unsur masing-masing setengah dari array
pada gilirannya dan melanjutkan.
Salah satunya adalah kurang dari tiga, jadi satu pergi.
>> Dua kurang dari tiga, sehingga dua pergi.
Tiga kurang dari 5, sehingga tiga pergi.
Empat kurang dari 5, sehingga empat pergi.
Kemudian lima kurang dari enam, dan enam adalah semua yang tersisa.
>> Sekarang, saya tahu, itu banyak langkah-langkah.
Dan kami telah meninggalkan banyak memori di bangun kami.
Dan itulah yang mereka kotak abu-abu.
Dan mungkin merasa seperti itu mengambil banyak lebih lama dari insertion sort, bubble
semacam, atau semacam seleksi.
>> Tapi sebenarnya, karena banyak proses ini
yang terjadi di time-- sama yang merupakan sesuatu yang kita akan, lagi,
berbicara tentang ketika kita berbicara tentang rekursi di masa depan video--
algoritma ini benar-benar jelas adalah fundamental
yang berbeda dari apa pun kita telah melihat sebelumnya
tetapi juga secara signifikan lebih hemat.
>> Kenapa itu?
Nah, di terburuk skenario, kita memiliki
untuk membagi n elemen up dan kemudian bergabung kembali mereka.
Tetapi ketika kita bergabung mereka, apa yang kita lakukan
pada dasarnya menggandakan ukuran array yang lebih kecil.
Kami memiliki sekelompok satu elemen array yang kita efektif
menggabungkan ke dua array elemen.
Dan kemudian kita mengambil mereka dua array elemen
dan menggabungkannya ke empat elemen array, dan sebagainya,
dan seterusnya, dan seterusnya, sampai kita memiliki array elemen n tunggal.
>> Tapi berapa banyak doubling yang dibutuhkan untuk sampai ke n?
Pikirkan kembali ke contoh buku telepon.
Berapa kali kita harus merobek buku telepon di setengah, berapa banyak lagi
kali kita harus merobek buku telepon dalam setengah, jika ukuran buku telepon
dua kali lipat?
Hanya ada satu, kan?
>> Jadi ada semacam elemen logaritmik sini.
Tapi kami juga masih harus setidaknya melihat semua elemen n.
Jadi dalam skenario terburuk, menggabungkan semacam berjalan di n log n.
Kita harus melihat semua elemen n,
dan kita harus menggabungkan mereka bersama-sama dalam log n set langkah.
Dalam skenario kasus terbaik, array sempurna diurutkan.
Itu bagus.
Tetapi berdasarkan algoritma yang kita miliki di sini, kita masih harus membagi dan bergabung kembali.
Meskipun dalam hal ini, recombining adalah jenis yang tidak efektif.
Hal ini tidak diperlukan.
Tapi kami masih pergi melalui seluruh proses pula.
>> Jadi dalam kasus terbaik dan dalam kasus terburuk,
algoritma ini berjalan di n log n waktu.
Menggabungkan semacam pasti sedikit lebih sulit dari algoritma pemilahan utama lainnya
kita bicarakan CS50 tetapi substansial lebih kuat.
>> Dan jadi jika Anda pernah menemukan kesempatan untuk membutuhkannya
atau menggunakannya untuk mengurutkan set data yang besar, mendapatkan
kepala Anda sekitar gagasan rekursi akan menjadi benar-benar kuat.
Dan itu akan membuat Anda program benar-benar jauh lebih efisien
menggunakan menggabungkan semacam dibandingkan apa pun.
Aku Doug Lloyd.
Ini adalah CS50.