1 00:00:00,000 --> 00:00:03,360 >> [MUSIC PLAYING] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Bütün sağ, belə ki, bubble sırala alqoritm 4 00:00:06,730 --> 00:00:08,730 siz elementləri bir sıra düzmək üçün istifadə edə bilərsiniz. 5 00:00:08,730 --> 00:00:10,850 Nin bu işləri necə bir nəzər salaq. 6 00:00:10,850 --> 00:00:13,240 >> Belə ki, əsas fikir arxasında bubble sort bu. 7 00:00:13,240 --> 00:00:17,340 Biz, ümumiyyətlə, yüksək hərəkət etmək istəyirəm ümumiyyətlə sağ üçün dəyərli elementləri, 8 00:00:17,340 --> 00:00:20,340 və ümumiyyətlə qiymətləndirilir elementləri aşağı sol, biz gözləmək kimi. 9 00:00:20,340 --> 00:00:23,256 Biz aşağı şeylər olmaq istəyirəm başlanğıcı və ali şeyi 10 00:00:23,256 --> 00:00:24,970 sonunda olacaq. 11 00:00:24,970 --> 00:00:26,130 >> Bunu necə edə bilərəm? 12 00:00:26,130 --> 00:00:28,040 Yaxşı pseudocode kodu, biz edək, deyə bilər 13 00:00:28,040 --> 00:00:30,320 qeyri-sıfır dəyəri bir svop counter seçin. 14 00:00:30,320 --> 00:00:32,570 Biz ikinci ki, niyə biz görəcəksiniz. 15 00:00:32,570 --> 00:00:36,090 Və sonra biz aşağıdakı təkrar svop counter 0 qədər prosesi, 16 00:00:36,090 --> 00:00:39,910 və ya biz heç svopları etmək qədər. 17 00:00:39,910 --> 00:00:43,170 >> Svop counter sıfırlamak 0 artıq 0 deyil, əgər. 18 00:00:43,170 --> 00:00:46,420 Sonra hər baxmaq elementləri qonşu cüt. 19 00:00:46,420 --> 00:00:49,550 Bu iki elementlər varsa etməmək üçün, onları dəyişdirmək, 20 00:00:49,550 --> 00:00:51,620 və svop counter 1 əlavə edin. 21 00:00:51,620 --> 00:00:53,870 Siz haqqında düşünür istəyirsinizsə bu görüntüləmək əvvəl, 22 00:00:53,870 --> 00:00:57,471 Bu aşağı hərəkət edəcək ki, görürsünüz sol qiymətləndirilir elementləri 23 00:00:57,471 --> 00:01:00,720 və ali sağ elementləri qiymətləndirilir səmərəli biz istəyirik nə, 24 00:01:00,720 --> 00:01:03,940 olan qruplar hərəkət edir ki, yol elementləri. 25 00:01:03,940 --> 00:01:07,035 Nin necə görüntüləmək imkan bizim array istifadə ola bilər 26 00:01:07,035 --> 00:01:10,504 Biz test üçün istifadə ki, bu alqoritmlər həyata. 27 00:01:10,504 --> 00:01:13,420 Biz yenə burada çeşidlənməmiş sıra var elementləri bütün göstərilən 28 00:01:13,420 --> 00:01:14,840 qırmızı olan. 29 00:01:14,840 --> 00:01:17,970 Mən svop counter müəyyən bir nonzero dəyəri. 30 00:01:17,970 --> 00:01:20,610 Mən özbaşına seçdi mənfi 1 var Bu 0 deyil. 31 00:01:20,610 --> 00:01:23,840 Biz bu prosesi təkrar etmək istəyirəm swap counter qədər 0. 32 00:01:23,840 --> 00:01:26,540 Mən svop müəyyən Buna görə bəzi qeyri-sıfır dəyəri counter, 33 00:01:26,540 --> 00:01:29,400 başqa, çünki svop counter 0 olardı. 34 00:01:29,400 --> 00:01:31,610 Biz hətta başlamaq deyil alqoritmi prosesi. 35 00:01:31,610 --> 00:01:33,610 Belə ki, yenə addımlar are-- svop counter sıfırlamak 36 00:01:33,610 --> 00:01:37,900 0, sonra hər bitişik baxmaq cüt və onlar üçün həyata əgər, 37 00:01:37,900 --> 00:01:40,514 onları dəyişdirmək və 1 əlavə svop counter. 38 00:01:40,514 --> 00:01:41,680 Belə ki, bu prosesi başlasın. 39 00:01:41,680 --> 00:01:44,430 Beləliklə, biz nə ilk şey biz 0 svop counter müəyyən 40 00:01:44,430 --> 00:01:46,660 və sonra axtarır başlamaq hər bitişik cüt. 41 00:01:46,660 --> 00:01:49,140 >> Beləliklə, biz ilk 5 və 2 baxaraq başlamaq. 42 00:01:49,140 --> 00:01:52,410 Biz onların həyata var ki, görəcəksiniz sifariş və biz onları dəyişdirmək. 43 00:01:52,410 --> 00:01:53,830 Və biz mübadilə counter 1 əlavə edin. 44 00:01:53,830 --> 00:01:57,860 Belə ki, indi bizim svop counter 1, və 2 və 5 işə edilmişdir. 45 00:01:57,860 --> 00:01:59,370 İndi biz yenidən prosesi təkrar edin. 46 00:01:59,370 --> 00:02:03,540 >> Biz növbəti bitişik cüt baxmaq, 5 və onlar da üçün bitti 1 var, 47 00:02:03,540 --> 00:02:06,960 belə ki, biz onları dəyişdirmək və əlavə Svop counter 1. 48 00:02:06,960 --> 00:02:08,900 Sonra biz 5 və 3 oldu. 49 00:02:08,900 --> 00:02:13,830 Onlar üçün həyata, belə ki, biz dəyişdirmək Onlara və biz mübadilə counter 1 əlavə edin. 50 00:02:13,830 --> 00:02:15,550 Sonra biz 5 və 6 oldu. 51 00:02:15,550 --> 00:02:18,630 Onlar üçün istəyirik, biz, həqiqətən, yoxdur bir şey bu dəfə dəyişdirmək lazımdır. 52 00:02:18,630 --> 00:02:20,250 Sonra biz 6 və 4 oldu. 53 00:02:20,250 --> 00:02:24,920 Onlar qaydada həyata də istəyirik, biz dəyişdirmək Onlara və biz mübadilə counter 1 əlavə edin. 54 00:02:24,920 --> 00:02:26,230 >> İndi baş nə görürsünüz. 55 00:02:26,230 --> 00:02:29,514 Biz sonuna 6 bütün yol hərəkət etdik. 56 00:02:29,514 --> 00:02:32,180 Seçim sort Belə ki, siz var əgər video görüldü nə etdik oldu 57 00:02:32,180 --> 00:02:35,290 biz hərəkət sona çatdı binasında kiçik elementləri 58 00:02:35,290 --> 00:02:39,640 mahiyyətcə sorted array ən böyük, kiçik sağ. 59 00:02:39,640 --> 00:02:43,200 Bubble növ halda, biz əgər bu alqoritm sonra, 60 00:02:43,200 --> 00:02:46,720 biz, həqiqətən, bina olacaq sağdan sıralanır array 61 00:02:46,720 --> 00:02:49,100 kiçik, böyük sol. 62 00:02:49,100 --> 00:02:53,840 Biz səmərəli 6, bubbled var böyük dəyəri, sonuna bütün yol. 63 00:02:53,840 --> 00:02:56,165 >> Və belə ki, biz indi elan edə bilər ki, çeşidlənir ki, 64 00:02:56,165 --> 00:02:59,130 və gələcəkdə iterations-- array keçir again-- 65 00:02:59,130 --> 00:03:01,280 biz artıq 6 hesab yoxdur. 66 00:03:01,280 --> 00:03:03,850 Biz yalnız hesab etmək lazımdır çeşidlənməmiş elementləri 67 00:03:03,850 --> 00:03:06,299 zaman biz qonşu cüt baxırıq. 68 00:03:06,299 --> 00:03:08,340 Beləliklə, biz bir başa bubble sırala keçir. 69 00:03:08,340 --> 00:03:11,941 Belə ki, indi biz suala geri, svop counter 0 qədər deyirəm. 70 00:03:11,941 --> 00:03:13,690 Yaxşı svop counter 4, belə ki, biz gedirik 71 00:03:13,690 --> 00:03:15,410 yenidən bu prosesi təkrar saxlamaq. 72 00:03:15,410 --> 00:03:19,180 >> Biz svop counter sıfırlamak olacaq 0 və hər bitişik cüt baxmaq. 73 00:03:19,180 --> 00:03:21,890 Belə ki, biz onlar 1 var 2 ilə başlamaq və qaydada həyata, belə ki, biz onları dəyişdirmək 74 00:03:21,890 --> 00:03:23,620 və biz mübadilə counter 1 əlavə edin. 75 00:03:23,620 --> 00:03:25,490 2 və 3, onlar üçün istəyirik. 76 00:03:25,490 --> 00:03:27,060 Biz bir şey etmək lazım deyil. 77 00:03:27,060 --> 00:03:28,420 3 və 5 üçün var. 78 00:03:28,420 --> 00:03:30,150 Biz orada bir şey etmək lazım deyil. 79 00:03:30,150 --> 00:03:32,515 >> 5 və 4, onlar həyata sifariş və biz 80 00:03:32,515 --> 00:03:35,130 onları dəyişdirmək və əlavə etmək lazımdır Svop counter 1. 81 00:03:35,130 --> 00:03:38,880 İndi biz, 5 hərəkət etdik növbəti böyük element, 82 00:03:38,880 --> 00:03:40,920 çeşidlənməmiş hissəsi sonuna. 83 00:03:40,920 --> 00:03:44,360 Beləliklə, biz indi zəng edə bilərsiniz sıralanır hissəsinin hissəsidir. 84 00:03:44,360 --> 00:03:47,180 >> İndi baxırıq ekran və yəqin ki, demək olar, 85 00:03:47,180 --> 00:03:50,130 , mən array kimi İndi çeşidlənir. 86 00:03:50,130 --> 00:03:51,820 Amma biz hələ ki, sübut edə bilməz. 87 00:03:51,820 --> 00:03:54,359 Biz zəmanət yoxdur ki, sıralanır. 88 00:03:54,359 --> 00:03:56,900 Amma bu harada svop deyil counter oyun minir olacaq. 89 00:03:56,900 --> 00:03:59,060 >> Beləliklə, biz bir keçid tamamladım. 90 00:03:59,060 --> 00:04:00,357 svop counter 2. 91 00:04:00,357 --> 00:04:02,190 Beləliklə, biz demək olacaq yenə bu proses, 92 00:04:02,190 --> 00:04:04,290 svop counter 0 qədər deyirəm. 93 00:04:04,290 --> 00:04:05,550 0 svop counter sıfırlamak. 94 00:04:05,550 --> 00:04:06,820 Belə ki, biz yenidən lazımdır. 95 00:04:06,820 --> 00:04:09,810 >> İndi hər bitişik cüt baxmaq. 96 00:04:09,810 --> 00:04:11,880 Ki, üçün 1 və 2 var. 97 00:04:11,880 --> 00:04:13,590 2 və 3 üçün var. 98 00:04:13,590 --> 00:04:15,010 3 və 4 üçün var. 99 00:04:15,010 --> 00:04:19,250 Belə ki, bu nöqtədə, biz tamamladım qeyd hər bitişik cüt baxaraq, 100 00:04:19,250 --> 00:04:22,530 lakin swap counter hələ 0. 101 00:04:22,530 --> 00:04:25,520 >> Biz keçid yoxsa hansı elementləri, onlar 102 00:04:25,520 --> 00:04:28,340 ilə, qaydada olmalıdır Bu prosesin əsasında. 103 00:04:28,340 --> 00:04:32,000 Və belə növ bir səmərəliliyinin, ki, biz kompüter alimləri sevgi, 104 00:04:32,000 --> 00:04:35,560 indi elan edə bilər ki, bütün array olmalıdır 105 00:04:35,560 --> 00:04:38,160 Biz çünki, sıralaması hər hansı elementləri dəyişdirmək lazımdır. 106 00:04:38,160 --> 00:04:40,380 Bu olduqca gözəl. 107 00:04:40,380 --> 00:04:43,260 >> Belə ki, nə ən pis halda var bubble növ ilə ssenari? 108 00:04:43,260 --> 00:04:46,240 Ən pis halda array var tamamilə əks qaydada, 109 00:04:46,240 --> 00:04:49,870 və biz hər bir bubble var böyük elementləri bütün 110 00:04:49,870 --> 00:04:51,780 array arasında bir yoldur. 111 00:04:51,780 --> 00:04:55,350 Və biz səmərəli də var bubble kiçik elementləri bütün geri 112 00:04:55,350 --> 00:04:57,050 Çox array arasında bütün yol. 113 00:04:57,050 --> 00:05:01,950 Belə ki, n elementlərin hər hərəkət var digər n elementləri bütün arasında. 114 00:05:01,950 --> 00:05:04,102 Belə ki, ən pis ssenari var. 115 00:05:04,102 --> 00:05:05,810 Ən yaxşı halda ssenari olsa da, bu 116 00:05:05,810 --> 00:05:07,880 seçim sort qədər fərqli. 117 00:05:07,880 --> 00:05:10,040 array artıq biz getmək zaman sıralanır. 118 00:05:10,040 --> 00:05:12,550 Biz hər hansı bir etmək yoxdur ilk pası svopları. 119 00:05:12,550 --> 00:05:14,940 Belə ki, biz baxmaq üçün ola bilər az elementləri, sağ? 120 00:05:14,940 --> 00:05:18,580 Biz bu təkrar yoxdur artıq bir neçə dəfə emal. 121 00:05:18,580 --> 00:05:19,540 >> Belə ki, nə deməkdir? 122 00:05:19,540 --> 00:05:22,390 Belə ki, nə ən pis ssenari var bubble sort üçün, və nə 123 00:05:22,390 --> 00:05:25,330 bubble sort üçün ən yaxşı ssenari? 124 00:05:25,330 --> 00:05:27,770 Bu tahmin mi? 125 00:05:27,770 --> 00:05:32,420 Ən pis halda təkrarlamaq lazımdır bütün n elementləri n dəfə arasında. 126 00:05:32,420 --> 00:05:34,220 Belə ki, ən pis halda kvadrat n edilir. 127 00:05:34,220 --> 00:05:36,550 >> Array mükəmməl olarsa sorted baxmayaraq, yalnız 128 00:05:36,550 --> 00:05:38,580 hər baxmaq bir dəfə elementləri. 129 00:05:38,580 --> 00:05:42,670 Və svop counter hələ 0 olduqda, Bu array çeşidlənir demək olar. 130 00:05:42,670 --> 00:05:45,780 Və belə ən yaxşı halda, bu seçilməsi daha həqiqətən yaxşı 131 00:05:45,780 --> 00:05:49,230 sort N omega var. 132 00:05:49,230 --> 00:05:50,270 >> Mən Doug Lloyd edirəm. 133 00:05:50,270 --> 00:05:52,140 Bu CS50 edir. 134 00:05:52,140 --> 00:05:54,382