1 00:00:00,000 --> 00:00:03,360 >> [MUSIC JOC] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Bine, așa bule fel este un algoritm 4 00:00:06,730 --> 00:00:08,730 puteți utiliza pentru a sorta un set de elemente. 5 00:00:08,730 --> 00:00:10,850 Să aruncăm o privire la modul în care funcționează. 6 00:00:10,850 --> 00:00:13,240 >> Deci, ideea de bază din spatele bubble fel este aceasta. 7 00:00:13,240 --> 00:00:17,340 Noi, în general doresc să se deplaseze mai mare elemente de valoare, în general, la dreapta, 8 00:00:17,340 --> 00:00:20,340 și coborâți elemente evaluate, în general, la stânga, așa cum ne-am aștepta. 9 00:00:20,340 --> 00:00:23,256 Ne dorim lucrurile mai mici pentru a fi la la început, și lucrurile mai mari 10 00:00:23,256 --> 00:00:24,970 să fie la sfârșitul anului. 11 00:00:24,970 --> 00:00:26,130 >> Cum facem acest lucru? 12 00:00:26,130 --> 00:00:28,040 Ei bine, în codul pseudocod, am putea spune, să 13 00:00:28,040 --> 00:00:30,320 stabilit un contor de schimb la o valoare diferită de zero. 14 00:00:30,320 --> 00:00:32,570 Vom vedea ce vom face acest lucru într-o secundă. 15 00:00:32,570 --> 00:00:36,090 Și apoi ne-am repeta următoarele proces până când contorul de swap este 0, 16 00:00:36,090 --> 00:00:39,910 sau până când vom face nici un swap-uri, la toate. 17 00:00:39,910 --> 00:00:43,170 >> Reseta contorul de swap pentru a 0 daca nu e deja 0. 18 00:00:43,170 --> 00:00:46,420 Apoi uita-te la fiecare pereche adiacentă de elemente. 19 00:00:46,420 --> 00:00:49,550 Dacă aceste două elemente sunt nu în ordine, le schimba, 20 00:00:49,550 --> 00:00:51,620 și se adaugă 1 la ghișeul de schimb. 21 00:00:51,620 --> 00:00:53,870 Dacă te gândești acest înainte de a le vizualiza, 22 00:00:53,870 --> 00:00:57,471 observați că acest lucru va muta mai mici elemente evaluate la stânga 23 00:00:57,471 --> 00:01:00,720 și mai mari elemente la dreapta de prim rang, face în mod eficient ceea ce vrem să facem, 24 00:01:00,720 --> 00:01:03,940 care este muta acele grupuri de elemente în acest fel. 25 00:01:03,940 --> 00:01:07,035 Să vizualiza modul în care acest s-ar putea uita-te folosind gama noastră 26 00:01:07,035 --> 00:01:10,504 care am folosit pentru a testa aceste algoritmi. 27 00:01:10,504 --> 00:01:13,420 Avem o gamă nesortate aici, din nou, indicat prin toate elementele 28 00:01:13,420 --> 00:01:14,840 fiind în roșu. 29 00:01:14,840 --> 00:01:17,970 Și am pus contra mea de schimb la o valoare diferită de zero. 30 00:01:17,970 --> 00:01:20,610 Am ales în mod arbitrar negativ 1-- nu este 0. 31 00:01:20,610 --> 00:01:23,840 Ne dorim să se repete acest proces până contorul de swap este 0. 32 00:01:23,840 --> 00:01:26,540 Acesta este motivul pentru care am stabilit de swap meu în contradicție cu o valoare diferită de zero, 33 00:01:26,540 --> 00:01:29,400 pentru ca altfel contor de swap ar fi 0. 34 00:01:29,400 --> 00:01:31,610 Noi nici măcar nu s-ar începe proces a algoritmului. 35 00:01:31,610 --> 00:01:33,610 Deci, din nou, pașii are-- reseta contorul de swap 36 00:01:33,610 --> 00:01:37,900 la 0, apoi uita-te la fiecare adiacente pereche, iar în cazul în care acestea sunt de ordine, 37 00:01:37,900 --> 00:01:40,514 swap-le, și se adaugă 1 la ghișeul de schimb. 38 00:01:40,514 --> 00:01:41,680 Așa că haideți să începem acest proces. 39 00:01:41,680 --> 00:01:44,430 Deci, primul lucru ce facem este ne-am stabilit contorul de swap la 0, 40 00:01:44,430 --> 00:01:46,660 și apoi vom începe căutarea la fiecare pereche adiacentă. 41 00:01:46,660 --> 00:01:49,140 >> Deci, vom începe mai întâi căutarea la 5 și 2. 42 00:01:49,140 --> 00:01:52,410 Vedem că acestea sunt în afara comandă și așa le-am schimba. 43 00:01:52,410 --> 00:01:53,830 Și vom adăuga 1 la contorul de swap. 44 00:01:53,830 --> 00:01:57,860 Deci, acum contra noastră de swap este de 1, și 2 și 5 au fost pornit. 45 00:01:57,860 --> 00:01:59,370 Acum vom repeta din nou acest proces. 46 00:01:59,370 --> 00:02:03,540 >> Ne uităm la următoarea pereche adiacentă, 5 și 1-- sunt, de asemenea, din ordin, 47 00:02:03,540 --> 00:02:06,960 asa ca am le schimba și se adaugă 1 la contorul de swap. 48 00:02:06,960 --> 00:02:08,900 Apoi ne uităm la 5 și 3. 49 00:02:08,900 --> 00:02:13,830 Ele sunt în afara de ordine, asa ca am schimba ei și vom adăuga 1 la contorul de swap. 50 00:02:13,830 --> 00:02:15,550 Apoi ne uităm la 5 și 6. 51 00:02:15,550 --> 00:02:18,630 Sunt în ordine, așa că nu face de fapt Trebuie să schimb ceva de data asta. 52 00:02:18,630 --> 00:02:20,250 Apoi ne uităm la 6 și 4. 53 00:02:20,250 --> 00:02:24,920 Sunt, de asemenea, din ordin, asa ca am schimba ei și vom adăuga 1 la contorul de swap. 54 00:02:24,920 --> 00:02:26,230 >> Acum observați ce sa întâmplat. 55 00:02:26,230 --> 00:02:29,514 Ne-am mutat 6 tot drumul până la sfârșit. 56 00:02:29,514 --> 00:02:32,180 Deci, în alegerea fel, dacă ați văzut că video, ceea ce am făcut a fost 57 00:02:32,180 --> 00:02:35,290 am ajuns deplasând mai mici elemente în clădire 58 00:02:35,290 --> 00:02:39,640 matrice sortate, în esență, de la la stânga la dreapta, mai mic la cel mai mare. 59 00:02:39,640 --> 00:02:43,200 În cazul bule fel, dacă suntem în urma acestui algoritm special, 60 00:02:43,200 --> 00:02:46,720 ne de fapt, va fi construirea matrice sortate de la dreapta 61 00:02:46,720 --> 00:02:49,100 la stânga, cel mai mare la cel mai mic. 62 00:02:49,100 --> 00:02:53,840 Am barbotat efectiv lui 6, cea mai mare valoare, tot drumul până la sfârșit. 63 00:02:53,840 --> 00:02:56,165 >> Și astfel încât să putem declara acum că este sortată, 64 00:02:56,165 --> 00:02:59,130 și în viitor iterations-- trece prin matrice again-- 65 00:02:59,130 --> 00:03:01,280 noi nu trebuie să ia în considerare mai 6. 66 00:03:01,280 --> 00:03:03,850 Trebuie doar să ia în considerare elementele nesortate 67 00:03:03,850 --> 00:03:06,299 când ne uităm la perechi adiacente. 68 00:03:06,299 --> 00:03:08,340 Deci, ne-am terminat unul trece prin balon fel. 69 00:03:08,340 --> 00:03:11,941 Deci, acum ne întoarcem la întrebarea, repetă până când contorul de swap este 0. 70 00:03:11,941 --> 00:03:13,690 Ei bine, contra schimb este de 4, asa ca vom 71 00:03:13,690 --> 00:03:15,410 a repeta din nou acest proces. 72 00:03:15,410 --> 00:03:19,180 >> Mergem pentru a reseta contorul de swap la 0, si uita-te la fiecare pereche adiacentă. 73 00:03:19,180 --> 00:03:21,890 Deci, vom începe cu 2 și 1-- sunt din ordin, asa ca le-am schimba 74 00:03:21,890 --> 00:03:23,620 și vom adăuga 1 la contorul de swap. 75 00:03:23,620 --> 00:03:25,490 2 și 3, sunt în ordine. 76 00:03:25,490 --> 00:03:27,060 Noi nu trebuie să facem nimic. 77 00:03:27,060 --> 00:03:28,420 3 și 5 sunt în ordine. 78 00:03:28,420 --> 00:03:30,150 Noi nu trebuie să facem nimic acolo. 79 00:03:30,150 --> 00:03:32,515 >> 5 și 4, acestea sunt în afara de ordine, și așa ne-am 80 00:03:32,515 --> 00:03:35,130 Trebuie să le schimba și se adaugă 1 la contorul de swap. 81 00:03:35,130 --> 00:03:38,880 Și acum ne-am mutat 5, următoarea cea mai mare element, 82 00:03:38,880 --> 00:03:40,920 la sfârșitul porțiunii nesortate. 83 00:03:40,920 --> 00:03:44,360 Deci, putem apela acum că parte a porțiunii sortate. 84 00:03:44,360 --> 00:03:47,180 >> Acum sunteți în căutarea la Cinema și, probabil, pot spune, 85 00:03:47,180 --> 00:03:50,130 cum aș putea, ca matrice este sortata acum. 86 00:03:50,130 --> 00:03:51,820 Dar nu putem dovedi că încă. 87 00:03:51,820 --> 00:03:54,359 Noi nu avem o garanție că este sortate. 88 00:03:54,359 --> 00:03:56,900 Dar acest lucru este în cazul în care swap- contra va intra în joc. 89 00:03:56,900 --> 00:03:59,060 >> Deci, am finalizat o pasă. 90 00:03:59,060 --> 00:04:00,357 Contorul de swap este de 2. 91 00:04:00,357 --> 00:04:02,190 Așa că am de gând să repet acest proces, din nou, 92 00:04:02,190 --> 00:04:04,290 repetă până când contorul de swap este 0. 93 00:04:04,290 --> 00:04:05,550 Reseta contorul de swap la 0. 94 00:04:05,550 --> 00:04:06,820 Deci vom reseta. 95 00:04:06,820 --> 00:04:09,810 >> Acum uita-te la fiecare pereche adiacentă. 96 00:04:09,810 --> 00:04:11,880 Asta e în ordine, 1 și 2. 97 00:04:11,880 --> 00:04:13,590 2 și 3 sunt în ordine. 98 00:04:13,590 --> 00:04:15,010 3 și 4 sunt în ordine. 99 00:04:15,010 --> 00:04:19,250 Deci, la acest punct, ne-am completat observa uita la fiecare pereche adiacentă, 100 00:04:19,250 --> 00:04:22,530 dar contorul de swap este încă 0. 101 00:04:22,530 --> 00:04:25,520 >> Dacă nu avem pentru a comuta orice elemente, atunci ele 102 00:04:25,520 --> 00:04:28,340 trebuie să fie în ordine, de virtutea acestui proces. 103 00:04:28,340 --> 00:04:32,000 Și astfel o eficiență de soiuri, că oameni de știință de calculator ne place, 104 00:04:32,000 --> 00:04:35,560 este putem declara acum întreaga rețea trebuie să 105 00:04:35,560 --> 00:04:38,160 fi sortate, pentru că nu am Trebuie să schimb elemente. 106 00:04:38,160 --> 00:04:40,380 Asta e destul de frumos. 107 00:04:40,380 --> 00:04:43,260 >> Deci, ce este cel mai rău caz scenariu cu bule fel? 108 00:04:43,260 --> 00:04:46,240 În cel mai rău caz matrice este în ordine inversă complet, 109 00:04:46,240 --> 00:04:49,870 și așa că trebuie să bule fiecare a elementelor mari tot 110 00:04:49,870 --> 00:04:51,780 drumul peste matrice. 111 00:04:51,780 --> 00:04:55,350 Și în mod eficient, de asemenea, să avem balon toate elementele mici din spate 112 00:04:55,350 --> 00:04:57,050 tot drumul peste matrice, de asemenea. 113 00:04:57,050 --> 00:05:01,950 Deci fiecare dintre cele n elemente trebuie să se deplaseze in toate celelalte n elemente. 114 00:05:01,950 --> 00:05:04,102 Deci, asta e cel mai rău caz. 115 00:05:04,102 --> 00:05:05,810 În cel mai bun caz scenariu deși, aceasta este 116 00:05:05,810 --> 00:05:07,880 ușor diferite de selecție fel. 117 00:05:07,880 --> 00:05:10,040 Matrice este deja clasificate în funcție atunci când vom merge în. 118 00:05:10,040 --> 00:05:12,550 Noi nu avem de a face orice swap-uri pe prima trecere. 119 00:05:12,550 --> 00:05:14,940 Deci, am putea avea să te uiți la mai puține elemente, nu? 120 00:05:14,940 --> 00:05:18,580 Noi nu trebuie să repetați acest procesa un număr de ori peste. 121 00:05:18,580 --> 00:05:19,540 >> Deci, ce înseamnă asta? 122 00:05:19,540 --> 00:05:22,390 Deci, ce este cel mai rău caz pentru bule de sortare, și ceea ce este 123 00:05:22,390 --> 00:05:25,330 cel mai bun caz pentru bule fel? 124 00:05:25,330 --> 00:05:27,770 Ai ghicit asta? 125 00:05:27,770 --> 00:05:32,420 În cel mai rău caz, trebuie să repeta în toate elementele n n ori. 126 00:05:32,420 --> 00:05:34,220 Deci cel mai rău caz este n pătrat. 127 00:05:34,220 --> 00:05:36,550 >> În cazul în care matricea este perfect sortat deși, doar 128 00:05:36,550 --> 00:05:38,580 trebuie să se uite la fiecare a elementelor dată. 129 00:05:38,580 --> 00:05:42,670 Și dacă contorul de swap este încă 0, vă pot spune acest lucru este matrice sortate. 130 00:05:42,670 --> 00:05:45,780 Și astfel, în cel mai bun caz, acest lucru este de fapt, mai bine decât de selecție 131 00:05:45,780 --> 00:05:49,230 sort-- este omega de n. 132 00:05:49,230 --> 00:05:50,270 >> Sunt Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Acest lucru este CS50. 134 00:05:52,140 --> 00:05:54,382