[Powered by Google Translate] TOMMY: Mari kita lihat pada pemilihan apapun, algoritma
untuk mengambil senarai nombor dan menyusun mereka.
Algoritma, ingat, adalah hanya langkah-demi-langkah
prosedur untuk mencapai tugas.
Idea asas di sebalik apapun pemilihan adalah untuk membahagi
kami senarai kepada dua bahagian -
sebahagian disusun dan bahagian Unsorted.
Pada setiap langkah algoritma, nombor dipindahkan dari
bahagian Unsorted bahagian disusun sehingga akhirnya
senarai keseluruhan disusun.
Jadi di sini adalah senarai enam nombor -
23, 42, 4, 16, 8, dan 15.
Sekarang seluruh senarai dianggap Unsorted.
Walaupun beberapa seperti 16 mungkin sudah betul
lokasi, algoritma kami tidak mempunyai cara untuk mengetahui bahawa sehingga
senarai keseluruhan disusun.
Jadi kita akan mempertimbangkan setiap nombor untuk Unsorted sehingga kita menyelesaikan
sendiri.
Kita tahu bahawa kita mahu senarai itu berada dalam susunan menaik.
Jadi kita akan mahu untuk membina bahagian disusun senarai kami
dari kiri ke kanan, terkecil hingga terbesar.
Untuk berbuat demikian, kita perlu mencari elemen Unsorted minimum
dan meletakkan ia pada akhir bahagian disusun.
Sejak senarai ini tidak diselesaikan, satu-satunya cara untuk berbuat demikian adalah untuk
melihat setiap elemen di bahagian Unsorted, mengingat
mana unsur yang terendah dan membandingkan
setiap elemen itu.
Jadi kita mula-mula akan melihat pada 23.
Ini adalah elemen pertama yang kita telah melihat, jadi kita akan ingat
sebagai minimum.
Seterusnya kita akan melihat pada 42.
42 adalah lebih besar daripada 23, jadi 23 masih minimum.
Berikut adalah 4 yang kurang dari 23, jadi kita akan ingat 4
sebagai minimum baru.
Berikut adalah 16 yang lebih besar daripada 4, jadi 4
masih minimum.
8 adalah lebih besar daripada 4, dan 15 adalah lebih besar daripada 4, jadi 4 mestilah
elemen Unsorted terkecil.
Jadi walaupun sebagai manusia kita segera boleh melihat bahawa 4 adalah
elemen minimum, algoritma kami perlu melihat
setiap elemen Unsorted, walaupun selepas kita dapati 4 -
elemen minimum.
Jadi sekarang kita dapati unsur minimum, 4, kita akan mahu
untuk bergerak ke bahagian disusun senarai.
Sejak ini adalah langkah pertama, ini bermakna kita mahu meletakkan 4 pada
permulaan senarai.
Sekarang 23 adalah pada awal senarai, jadi
mari kita swap 4 dan 23.
Jadi sekarang senarai kami kelihatan seperti ini.
Kita tahu bahawa 4 mesti berada di lokasi terakhir, kerana ia adalah
kedua-dua elemen terkecil dan elemen pada permulaan
senarai.
Jadi ini bermakna bahawa kita tidak pernah perlu untuk bergerak lagi.
Jadi mari kita mengulangi proses ini untuk menambah elemen lain untuk
bahagian yang disusun senarai.
Kita tahu bahawa kita tidak perlu melihat pada 4, kerana ia
sudah disusun.
Jadi, kita boleh mula pada 42, yang kita akan ingat sebagai
elemen minimum.
Jadi seterusnya kita akan melihat 23 yang mana adalah kurang dari 42, jadi kita
ingat 23 adalah minimum yang baru.
Seterusnya kita lihat 16 yang kurang daripada 23, jadi
16 adalah minimum yang baru.
Sekarang kita lihat pada 8 yang adalah kurang daripada 16, jadi
8 adalah minimum yang baru.
Dan akhirnya 8 adalah kurang dari 15, jadi kita tahu bahawa 8 adalah minimum
elemen Unsorted.
Jadi itu bermakna kita harus melampirkan 8 yang diisih
sebahagian daripada senarai.
Sekarang 4 adalah elemen hanya disusun, jadi kita mahu ke tempat
seterusnya 8 ke 4,.
Sejak 42 adalah elemen pertama dalam bahagian Unsorted daripada
senarai, kita akan mahu menukar 42 dan 8.
Jadi sekarang senarai kami kelihatan seperti ini.
4 dan 8 mewakili bahagian disusun senarai, dan
baki nombor mewakili Unsorted
sebahagian daripada senarai.
Jadi mari kita terus dengan lelaran lain.
Kita mulakan dengan 23 kali ini, kerana kita tidak perlu untuk melihat
4 dan 8 yang lagi kerana mereka telah
sudah disusun.
16 adalah kurang daripada 23, jadi kita akan ingat
16 sebagai minimum baru.
16 adalah kurang daripada 42, tetapi 15 adalah kurang daripada 16, jadi 15 mesti
elemen Unsorted minimum.
Jadi sekarang kita mahu untuk menukar 15 dan 23 hingga
memberikan kita senarai ini.
Bahagian disusun senarai terdiri daripada 4, 8 dan 15, dan
elemen-elemen ini masih Unsorted.
Tetapi ia hanya kebetulan bahawa seterusnya elemen Unsorted, 16,
sudah disusun.
Walau bagaimanapun, ada cara untuk algoritma kami tahu bahawa 16
sudah di lokasi yang betul, jadi kita masih perlu
mengulangi tepat proses yang sama.
Jadi kita lihat bahawa 16 adalah kurang daripada 42, dan 16 adalah kurang daripada 23, jadi
16 mesti elemen minimum.
Ia adalah mustahil untuk menukar elemen ini dengan sendiri, supaya kita boleh
hanya tinggalkan ia di lokasi ini.
Jadi kita perlu pas satu lagi algoritma kami.
42 adalah lebih besar daripada 23, jadi 23 mestilah
elemen Unsorted minimum.
Apabila kita menukar 23 dan 42, kita berakhir dengan akhir kami
senarai diisih -
4, 8, 15, 16, 23, 42.
Kita tahu 42 mesti berada di tempat yang betul kerana ia adalah
elemen-satunya kiri, dan itulah apapun pemilihan.
Mari kita sekarang merasmikan algoritma kami dengan beberapa
kod pseudo.
On line satu, kita boleh melihat bahawa kita perlu untuk mengintegrasikan lebih
setiap elemen senarai.
Kecuali elemen terakhir, kerana elemen 1
senarai sudah disusun.
On line dua, kita mempertimbangkan elemen pertama daripada Unsorted
sebahagian daripada senarai untuk menjadi minimum, seperti yang kita lakukan dengan kita
contoh, jadi kami mempunyai sesuatu untuk membandingkan.
Talian ketiga bermula gelung kedua di mana kita melelar lebih
setiap elemen Unsorted.
Kita tahu bahawa selepas i lelaran, bahagian yang disusun
senarai kami mesti mempunyai i elemen di dalamnya sejak setiap langkah
macam satu elemen.
Jadi elemen Unsorted pertama mestilah dalam kedudukan i campur 1.
On line empat, kita bandingkan elemen semasa minimum
elemen yang kita telah melihat setakat ini.
Jika elemen semasa adalah lebih kecil daripada minimum
unsur, maka kita ingat elemen semasa sebagai baru
minimum kepada lima baris.
Akhirnya, pada baris enam dan tujuh, kita swap minimum
elemen dengan elemen Unsorted pertama, sekali gus
menambah kepada bahagian disusun senarai.
Apabila kita mempunyai algoritma, satu persoalan yang penting untuk bertanya
diri kita sebagai pengaturcara berapa lama masa yang diambil?
Kita mula-mula akan bertanya soalan berapa lama ia mengambil masa untuk ini
algoritma untuk menjalankan dalam kes terburuk?
Recall kita mewakili berjalan ini
masa dengan notasi O besar.
Dalam usaha untuk menentukan elemen Unsorted minimum, kita
dasarnya terpaksa membandingkan setiap elemen dalam senarai untuk
setiap elemen lain dalam senarai.
Intuitif, ini bunyi seperti O operasi n kuasa dua.
Melihat pseudokod kami, kami juga mempunyai gelung bersarang di dalam
lagi gelung, yang sememangnya bunyi seperti O
operasi n kuasa dua.
Walau bagaimanapun, ingat bahawa kita tidak perlu untuk melihat lebih
seluruh senarai apabila menentukan elemen Unsorted minimum?
Apabila kita tahu bahawa 4 telah disusun, sebagai contoh, kita tidak
perlu melihat ia lagi.
Jadi adakah ini mengurangkan masa berjalan?
Untuk senarai kami sebanyak 6 panjang, kita diperlukan untuk membuat lima
perbandingan bagi elemen pertama, empat perbandingan untuk
elemen kedua, dan sebagainya.
Itu bermakna bahawa 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 sini.
Tetapi ternyata bahawa penjumlahan ini adalah sama untuk kali n
n tolak 1 lebih 2.
Atau sebandingnya, n kuasa dua lebih 2 tolak n lebih dari 2.
Apabila bercakap tentang runtime asimptot, n istilah kuasa dua
akan menguasai istilah ini n.
Jadi apapun pemilihan O n kuasa dua.
Ingatlah bahawa dalam contoh kita, apapun pemilihan masih diperlukan untuk
memeriksa jika nombor yang telah disusun
diperlukan untuk dipindahkan.
Supaya bermakna bahawa jika kita berlari apapun pemilihan lebih yang sudah
disusun senarai, ia akan memerlukan jumlah yang sama langkah-langkah kerana ia
akan apabila berjalan lebih senarai sepenuhnya Unsorted.
Jadi apapun pemilihan mempunyai kes prestasi terbaik n kuasa dua,
yang kita mewakili dengan omega n kuasa dua.
Dan itulah ia untuk menyelesaikan pemilihan.
Hanya salah satu algoritma banyak kita boleh
gunakan untuk menyusun senarai.
Nama saya adalah Tommy, dan ini adalah cs50.