1 00:00:00,000 --> 00:00:03,360 >> [Bermain muzik] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Baiklah, jadi semacam gelembung algoritma 4 00:00:06,730 --> 00:00:08,730 anda boleh gunakan untuk menyelesaikan satu set unsur-unsur. 5 00:00:08,730 --> 00:00:10,850 Mari kita lihat bagaimana ia berfungsi. 6 00:00:10,850 --> 00:00:13,240 >> Jadi idea asas di sebalik gelembung jenis adalah ini. 7 00:00:13,240 --> 00:00:17,340 Kita biasanya mahu untuk bergerak lebih tinggi unsur-unsur bernilai umumnya ke kanan, 8 00:00:17,340 --> 00:00:20,340 dan menurunkan unsur bernilai umumnya ke kiri, seperti yang kita jangkakan. 9 00:00:20,340 --> 00:00:23,256 Kami mahu perkara yang lebih rendah untuk berada di mulanya, dan perkara-perkara yang lebih tinggi 10 00:00:23,256 --> 00:00:24,970 untuk berada di akhir. 11 00:00:24,970 --> 00:00:26,130 >> Bagaimana kita lakukan ini? 12 00:00:26,130 --> 00:00:28,040 Well kod pseudo, kita boleh katakan, mari kita 13 00:00:28,040 --> 00:00:30,320 menetapkan kaunter pertukaran kepada nilai yang bukan sifar. 14 00:00:30,320 --> 00:00:32,570 Kami akan melihat mengapa kita berbuat demikian dalam satu saat. 15 00:00:32,570 --> 00:00:36,090 Dan kemudian kita mengulangi berikut proses sehingga kaunter pertukaran adalah 0, 16 00:00:36,090 --> 00:00:39,910 atau sehingga kami tidak membuat sebarang pertukaran pada semua. 17 00:00:39,910 --> 00:00:43,170 >> Menetapkan semula kaunter pertukaran untuk 0 jika tidak sudah 0. 18 00:00:43,170 --> 00:00:46,420 Kemudian melihat setiap pasangan bersebelahan unsur-unsur. 19 00:00:46,420 --> 00:00:49,550 Jika kedua-dua elemen ini tidak teratur, menukar mereka, 20 00:00:49,550 --> 00:00:51,620 dan tambahkan 1 ke kaunter swap. 21 00:00:51,620 --> 00:00:53,870 Jika anda berfikir tentang ini sebelum anda menggambarkan ia, 22 00:00:53,870 --> 00:00:57,471 melihat bahawa ini akan bergerak lebih rendah elemen penting ke kiri 23 00:00:57,471 --> 00:01:00,720 dan lebih tinggi bernilai unsur-unsur ke kanan, berkesan melakukan apa yang kita mahu lakukan, 24 00:01:00,720 --> 00:01:03,940 yang memindahkan kumpulan unsur-unsur dengan cara itu. 25 00:01:03,940 --> 00:01:07,035 Mari kita menggambarkan bagaimana ini mungkin kelihatan menggunakan pelbagai kami 26 00:01:07,035 --> 00:01:10,504 yang kita digunakan untuk menguji daripada algoritma ini. 27 00:01:10,504 --> 00:01:13,420 Kami mempunyai pelbagai terisih di sini lagi, ditunjukkan oleh semua unsur-unsur 28 00:01:13,420 --> 00:01:14,840 menjadi merah. 29 00:01:14,840 --> 00:01:17,970 Dan Aku menguduskan kaunter pertukaran saya kepada nilai bukan sifar. 30 00:01:17,970 --> 00:01:20,610 Saya sewenang-wenangnya memilih negatif 1-- ia bukan 0. 31 00:01:20,610 --> 00:01:23,840 Kami mahu mengulangi proses ini sehingga kaunter pertukaran adalah 0. 32 00:01:23,840 --> 00:01:26,540 Ini adalah mengapa saya menetapkan pertukaran saya bertentangan dengan beberapa nilai bukan sifar, 33 00:01:26,540 --> 00:01:29,400 kerana jika tidak, kaunter pertukaran akan menjadi 0. 34 00:01:29,400 --> 00:01:31,610 Kami akan tidak memulakan proses algoritma. 35 00:01:31,610 --> 00:01:33,610 Jadi sekali lagi, langkah-langkah ialah- menetapkan semula kaunter swap 36 00:01:33,610 --> 00:01:37,900 kepada 0, kemudian melihat setiap bersebelahan pasangan, dan jika mereka daripada perintah, 37 00:01:37,900 --> 00:01:40,514 menukar mereka, dan menambah 1 ke kaunter swap. 38 00:01:40,514 --> 00:01:41,680 Jadi mari kita memulakan proses ini. 39 00:01:41,680 --> 00:01:44,430 Jadi perkara pertama yang kita lakukan adalah kita menetapkan kaunter pertukaran ke 0, 40 00:01:44,430 --> 00:01:46,660 dan kemudian kita mula mencari di setiap pasangan bersebelahan. 41 00:01:46,660 --> 00:01:49,140 >> Oleh itu, kita mula-mula mula melihat 5 dan 2. 42 00:01:49,140 --> 00:01:52,410 Kita lihat bahawa mereka berada di luar memerintahkan dan dengan itu kita menukar mereka. 43 00:01:52,410 --> 00:01:53,830 Dan kita tambah 1 ke kaunter swap. 44 00:01:53,830 --> 00:01:57,860 Jadi sekarang kaunter pertukaran kami adalah 1, dan 2 dan 5 telah dihidupkan. 45 00:01:57,860 --> 00:01:59,370 Sekarang kita mengulangi proses lagi. 46 00:01:59,370 --> 00:02:03,540 >> Kita melihat pasangan bersebelahan yang akan datang, 5 dan 1-- mereka juga daripada perintah, 47 00:02:03,540 --> 00:02:06,960 jadi kami menukar mereka dan menambah 1 ke kaunter swap. 48 00:02:06,960 --> 00:02:08,900 Kemudian kami melihat 5 dan 3. 49 00:02:08,900 --> 00:02:13,830 Mereka adalah daripada perintah, jadi kami menukar mereka dan kami tambahkan 1 ke kaunter swap. 50 00:02:13,830 --> 00:02:15,550 Kemudian kami melihat 5 dan 6. 51 00:02:15,550 --> 00:02:18,630 Mereka berada dalam perintah, supaya kita tidak benar-benar perlu untuk menukar apa-apa masa ini. 52 00:02:18,630 --> 00:02:20,250 Kemudian kita melihat 6 dan 4. 53 00:02:20,250 --> 00:02:24,920 Mereka juga berada di luar perintah, jadi kami menukar mereka dan kami tambahkan 1 ke kaunter swap. 54 00:02:24,920 --> 00:02:26,230 >> Sekarang perhatikan apa yang berlaku. 55 00:02:26,230 --> 00:02:29,514 Kami telah berpindah 6 hingga ke akhir. 56 00:02:29,514 --> 00:02:32,180 Jadi dalam jenis pemilihan, jika anda telah melihat video itu, apa yang kami lakukan adalah 57 00:02:32,180 --> 00:02:35,290 kita berakhir menggerakkan unsur-unsur yang paling kecil di dalam bangunan 58 00:02:35,290 --> 00:02:39,640 array disusun dasarnya dari kiri ke kanan, kecik hingga besar. 59 00:02:39,640 --> 00:02:43,200 Dalam hal semacam gelembung, jika kita berikut algoritma ini khususnya, 60 00:02:43,200 --> 00:02:46,720 sedang kita benar-benar akan membina array disusun dari kanan 61 00:02:46,720 --> 00:02:49,100 ke kiri, terbesar kepada yang paling kecil. 62 00:02:49,100 --> 00:02:53,840 Kami berkesan dipam 6, nilai terbesar, sepanjang jalan ke akhir. 63 00:02:53,840 --> 00:02:56,165 >> Dan dengan itu kita kini boleh mengisytiharkan bahawa yang disusun, 64 00:02:56,165 --> 00:02:59,130 dan pada masa akan iterations-- melalui array again-- 65 00:02:59,130 --> 00:03:01,280 kita tidak perlu mengambil kira 6 lagi. 66 00:03:01,280 --> 00:03:03,850 Kita hanya perlu mengambil kira unsur-unsur terisih 67 00:03:03,850 --> 00:03:06,299 apabila kita melihat pasangan bersebelahan. 68 00:03:06,299 --> 00:03:08,340 Jadi kita telah selesai satu melalui semacam gelembung. 69 00:03:08,340 --> 00:03:11,941 Jadi sekarang kita kembali kepada soalan, ulangi sehingga kaunter pertukaran adalah 0. 70 00:03:11,941 --> 00:03:13,690 Well kaunter swap ialah 4, jadi kita akan 71 00:03:13,690 --> 00:03:15,410 untuk terus mengulangi proses ini lagi. 72 00:03:15,410 --> 00:03:19,180 >> Kami akan menetapkan semula kaunter swap kepada 0, dan melihat setiap pasangan bersebelahan. 73 00:03:19,180 --> 00:03:21,890 Oleh itu, kita mulakan dengan 2 dan 1-- mereka daripada perintah, supaya kita menukar mereka 74 00:03:21,890 --> 00:03:23,620 dan kita tambah 1 ke kaunter swap. 75 00:03:23,620 --> 00:03:25,490 2 dan 3, mereka teratur. 76 00:03:25,490 --> 00:03:27,060 Kita tidak perlu berbuat apa-apa. 77 00:03:27,060 --> 00:03:28,420 3 dan 5 adalah teratur. 78 00:03:28,420 --> 00:03:30,150 Kita tidak perlu berbuat apa-apa di sana. 79 00:03:30,150 --> 00:03:32,515 >> 5 dan 4, mereka berada di luar perintah, dan dengan itu kita 80 00:03:32,515 --> 00:03:35,130 perlu untuk menukar mereka dan menambah 1 ke kaunter swap. 81 00:03:35,130 --> 00:03:38,880 Dan sekarang kita telah berpindah 5, unsur terbesar yang akan datang, 82 00:03:38,880 --> 00:03:40,920 hingga akhir bahagian yang terisih. 83 00:03:40,920 --> 00:03:44,360 Oleh itu, kita kini boleh memanggil bahawa sebahagian daripada bahagian yang disusun. 84 00:03:44,360 --> 00:03:47,180 >> Kini anda sedang melihat skrin dan mungkin boleh beritahu, 85 00:03:47,180 --> 00:03:50,130 begitu juga saya, yang array disusun sekarang. 86 00:03:50,130 --> 00:03:51,820 Tetapi kita tidak dapat membuktikan bahawa kini. 87 00:03:51,820 --> 00:03:54,359 Kami tidak mempunyai jaminan bahawa ia disusun. 88 00:03:54,359 --> 00:03:56,900 Tetapi ini adalah di mana swap kaunter akan datang ke dalam bermain. 89 00:03:56,900 --> 00:03:59,060 >> Oleh itu, kita telah menyelesaikan lulus. 90 00:03:59,060 --> 00:04:00,357 Kaunter pertukaran ialah 2. 91 00:04:00,357 --> 00:04:02,190 Jadi, kita akan mengulangi proses ini lagi, 92 00:04:02,190 --> 00:04:04,290 ulangi sehingga kaunter pertukaran adalah 0. 93 00:04:04,290 --> 00:04:05,550 Menetapkan semula kaunter pertukaran ke 0. 94 00:04:05,550 --> 00:04:06,820 Oleh itu, kita akan menetapkan semula. 95 00:04:06,820 --> 00:04:09,810 >> Sekarang lihat pada setiap pasangan bersebelahan. 96 00:04:09,810 --> 00:04:11,880 Itulah teratur, 1 dan 2. 97 00:04:11,880 --> 00:04:13,590 2 dan 3 adalah teratur. 98 00:04:13,590 --> 00:04:15,010 3 dan 4 adalah teratur. 99 00:04:15,010 --> 00:04:19,250 Jadi pada ketika ini, melihat kami telah selesai melihat setiap pasangan yang bersebelahan, 100 00:04:19,250 --> 00:04:22,530 tetapi kaunter pertukaran itu masih 0. 101 00:04:22,530 --> 00:04:25,520 >> Jika kita tidak perlu menukar sebarang unsur-unsur, maka mereka 102 00:04:25,520 --> 00:04:28,340 hendaklah teratur, dengan menurut proses ini. 103 00:04:28,340 --> 00:04:32,000 Dan sebagainya kecekapan macam, bahawa saintis kita komputer cinta, 104 00:04:32,000 --> 00:04:35,560 adalah kita kini boleh mengisytiharkan pelbagai keseluruhan mesti 105 00:04:35,560 --> 00:04:38,160 diisih, kerana kita tidak perlu menukar mana-mana unsur-unsur. 106 00:04:38,160 --> 00:04:40,380 Itu cukup bagus. 107 00:04:40,380 --> 00:04:43,260 >> Jadi apa kes yang paling teruk senario dengan seperti gelembung? 108 00:04:43,260 --> 00:04:46,240 Dalam kes terburuk array adalah agar benar-benar terbalik, 109 00:04:46,240 --> 00:04:49,870 dan dengan itu kita perlu gelembung setiap unsur-unsur besar semua 110 00:04:49,870 --> 00:04:51,780 jalan di seluruh array. 111 00:04:51,780 --> 00:04:55,350 Dan kita berkesan juga perlu gelembung semua unsur-unsur kecil kembali 112 00:04:55,350 --> 00:04:57,050 sepanjang jalan di seluruh array, juga. 113 00:04:57,050 --> 00:05:01,950 Jadi setiap satu daripada unsur-unsur n perlu bergerak di semua unsur-unsur n lain. 114 00:05:01,950 --> 00:05:04,102 Jadi itulah senario kes terburuk. 115 00:05:04,102 --> 00:05:05,810 Dalam kes ini, senario walaupun, ini adalah 116 00:05:05,810 --> 00:05:07,880 sedikit berbeza daripada jenis pemilihan. 117 00:05:07,880 --> 00:05:10,040 Array sudah disusun apabila kita masuk ke dalam. 118 00:05:10,040 --> 00:05:12,550 Kami tidak perlu membuat sebarang swap pada pas yang pertama. 119 00:05:12,550 --> 00:05:14,940 Oleh itu, kita mungkin perlu melihat di lebih sedikit unsur-unsur, bukan? 120 00:05:14,940 --> 00:05:18,580 Kami tidak perlu mengulangi ini memproses beberapa kali. 121 00:05:18,580 --> 00:05:19,540 >> Jadi apa maksudnya? 122 00:05:19,540 --> 00:05:22,390 Jadi apa kes yang teruk untuk jenis gelembung, dan apa yang 123 00:05:22,390 --> 00:05:25,330 kes senario terbaik untuk jenis gelembung? 124 00:05:25,330 --> 00:05:27,770 Adakah anda rasa ini? 125 00:05:27,770 --> 00:05:32,420 Dalam kes terburuk anda perlu untuk melelar di semua n unsur n kali. 126 00:05:32,420 --> 00:05:34,220 Jadi kes yang paling teruk adalah n kuasa dua. 127 00:05:34,220 --> 00:05:36,550 >> Jika array adalah sempurna disusun walaupun, anda hanya 128 00:05:36,550 --> 00:05:38,580 perlu melihat setiap satu elemen sekali. 129 00:05:38,580 --> 00:05:42,670 Dan jika kaunter pertukaran itu masih 0, anda boleh berkata pelbagai ini disusun. 130 00:05:42,670 --> 00:05:45,780 Dan sebagainya dalam kes ini, ini adalah sebenarnya lebih baik daripada pilihan 131 00:05:45,780 --> 00:05:49,230 sort-- ia omega n. 132 00:05:49,230 --> 00:05:50,270 >> Saya Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Ini adalah CS50. 134 00:05:52,140 --> 00:05:54,382