1
00:00:00,000 --> 00:00:03,360
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Molt bé, així
ordenament de bombolla és un algoritme

4
00:00:06,730 --> 00:00:08,730
es pot utilitzar per ordenar un conjunt d'elements.

5
00:00:08,730 --> 00:00:10,850
Fem una ullada a com funciona.

6
00:00:10,850 --> 00:00:13,240
>> Així que la idea bàsica darrera
ordenament de bombolla és això.

7
00:00:13,240 --> 00:00:17,340
Generalment Volem avançar més alta
elements valorats generalment a la dreta,

8
00:00:17,340 --> 00:00:20,340
i baixar elements valorats generalment
a l'esquerra, com era d'esperar.

9
00:00:20,340 --> 00:00:23,256
Volem que les coses inferiors a estar a
el principi, i les coses més elevades

10
00:00:23,256 --> 00:00:24,970
a estar a l'extrem.

11
00:00:24,970 --> 00:00:26,130
>> Com fem això?

12
00:00:26,130 --> 00:00:28,040
Bé en el codi de pseudocodi,
podríem dir, anem a

13
00:00:28,040 --> 00:00:30,320
fixar un comptador de bescanvi a un valor diferent de zero.

14
00:00:30,320 --> 00:00:32,570
Ja veurem què fem això en un segon.

15
00:00:32,570 --> 00:00:36,090
I després repetim el següent
procés fins que el comptador d'intercanvi és 0,

16
00:00:36,090 --> 00:00:39,910
o fins que no fem canvis en absolut.

17
00:00:39,910 --> 00:00:43,170
>> Restablir el comptador d'intercanvi d'
0 si no ho és ja 0.

18
00:00:43,170 --> 00:00:46,420
Després, busquin en cada
parell adjacent d'elements.

19
00:00:46,420 --> 00:00:49,550
Si aquests dos elements són
no en ordre, ells intercanviar,

20
00:00:49,550 --> 00:00:51,620
i afegeix 1 al comptador d'intercanvi.

21
00:00:51,620 --> 00:00:53,870
Si vostè està pensant en
això abans de visualitzar-lo,

22
00:00:53,870 --> 00:00:57,471
observi que aquest es mourà més baixa
elements valuosos a l'esquerra

23
00:00:57,471 --> 00:01:00,720
i més alt elements a la dreta valorada,
fent amb eficàcia el que volem fer,

24
00:01:00,720 --> 00:01:03,940
que és moure aquests grups
d'elements en aquesta forma.

25
00:01:03,940 --> 00:01:07,035
Anem a visualitzar com aquest
podria semblar utilitzant la nostra gamma

26
00:01:07,035 --> 00:01:10,504
que utilitzem per provar
aquests algoritmes.

27
00:01:10,504 --> 00:01:13,420
Tenim una gran varietat classificar aquí de nou,
indicat per tots els elements

28
00:01:13,420 --> 00:01:14,840
estant en vermell.

29
00:01:14,840 --> 00:01:17,970
I vaig tornar el meu comptador d'intercanvi
a un valor diferent de zero.

30
00:01:17,970 --> 00:01:20,610
Jo vaig triar arbitràriament
negatiu 1-- no és 0.

31
00:01:20,610 --> 00:01:23,840
Volem repetir aquest procés
fins que el comptador d'intercanvi és de 0.

32
00:01:23,840 --> 00:01:26,540
Per això em vaig posar el meu permuta
comptador a algun valor diferent de zero,

33
00:01:26,540 --> 00:01:29,400
perquè en cas contrari la
comptador d'intercanvi seria 0.

34
00:01:29,400 --> 00:01:31,610
Ni tan sols podríem començar el
procés de l'algorisme.

35
00:01:31,610 --> 00:01:33,610
Així que de nou, els passos són--
restablir el comptador d'intercanvi

36
00:01:33,610 --> 00:01:37,900
a 0, a continuació, cerqueu a cada costat
parell, i si estan fora de servei,

37
00:01:37,900 --> 00:01:40,514
intercanviar-los, i afegir 1
al taulell d'intercanvi.

38
00:01:40,514 --> 00:01:41,680
Així que anem a començar aquest procés.

39
00:01:41,680 --> 00:01:44,430
Així que el primer que fem és
ens vam posar al taulell d'intercanvi a 0,

40
00:01:44,430 --> 00:01:46,660
i després començar a cercar
en cada parell adjacent.

41
00:01:46,660 --> 00:01:49,140
>> Així que primer començar a buscar a les 5 i 2.

42
00:01:49,140 --> 00:01:52,410
Veiem que estan fora de
Ordre i així que els swap.

43
00:01:52,410 --> 00:01:53,830
I afegim 1 al comptador d'intercanvi.

44
00:01:53,830 --> 00:01:57,860
Així que ara el nostre comptador d'intercanvi és 1,
i 2 i 5 han estat commutada.

45
00:01:57,860 --> 00:01:59,370
Ara repetim el procés de nou.

46
00:01:59,370 --> 00:02:03,540
>> Ens fixem en el següent parell adjacent,
5 i 1-- estan també fora d'ordre,

47
00:02:03,540 --> 00:02:06,960
així que els swap i afegim
1 al comptador d'intercanvi.

48
00:02:06,960 --> 00:02:08,900
Llavors ens fixem en 5 i 3.

49
00:02:08,900 --> 00:02:13,830
Ells estan fora de servei, de manera que intercanvien
ells i afegim 1 al comptador d'intercanvi.

50
00:02:13,830 --> 00:02:15,550
Llavors ens fixem en 5 i 6.

51
00:02:15,550 --> 00:02:18,630
Estan en ordre, així que en realitat no
necessitarà canviar res aquesta vegada.

52
00:02:18,630 --> 00:02:20,250
Llavors ens fixem en 6 i 4.

53
00:02:20,250 --> 00:02:24,920
Són també fora de servei, així que intercanvien
ells i afegim 1 al comptador d'intercanvi.

54
00:02:24,920 --> 00:02:26,230
>> Ara noti el que ha passat.

55
00:02:26,230 --> 00:02:29,514
Hem passat 6 de tot el camí fins al final.

56
00:02:29,514 --> 00:02:32,180
Així que en la selecció d'espècie, si tens
vist aquest vídeo, el que vam fer va ser

57
00:02:32,180 --> 00:02:35,290
Acabem canviant la
els elements més petits de la construcció

58
00:02:35,290 --> 00:02:39,640
la matriu ordenada essencialment de
esquerra a dreta, de menor a major.

59
00:02:39,640 --> 00:02:43,200
En el cas d'ordenament de bombolla, si som
seguint aquest algorisme en particular,

60
00:02:43,200 --> 00:02:46,720
estem en realitat serà la construcció
la matriu ordenada de dreta

61
00:02:46,720 --> 00:02:49,100
a esquerra, de major a menor.

62
00:02:49,100 --> 00:02:53,840
Hem bombolleig eficaçment 6, la
valor més gran, tot el camí fins al final.

63
00:02:53,840 --> 00:02:56,165
>> I així podem ara declarar
que això es va solucionar,

64
00:02:56,165 --> 00:02:59,130
i en el futur iterations--
passant per la matriu nou--

65
00:02:59,130 --> 00:03:01,280
no hem de considerar 6 més.

66
00:03:01,280 --> 00:03:03,850
Només hem de considerar
els elements sense classificar

67
00:03:03,850 --> 00:03:06,299
quan estem veient parells adjacents.

68
00:03:06,299 --> 00:03:08,340
Així que hem acabat un sol
passar a través d'ordenament de bombolla.

69
00:03:08,340 --> 00:03:11,941
Així que ara tornem a la pregunta,
repetir fins que el comptador d'intercanvi és 0.

70
00:03:11,941 --> 00:03:13,690
Bé el comptador d'intercanvi
és 4, per la qual cosa anem

71
00:03:13,690 --> 00:03:15,410
seguir repetint aquest procés de nou.

72
00:03:15,410 --> 00:03:19,180
>> Anem a zero el comptador d'intercanvi
a 0, i buscar en cada parell adjacent.

73
00:03:19,180 --> 00:03:21,890
Així que vam començar amb 2 i 1-- són
fora de servei, de manera que els intercanviem

74
00:03:21,890 --> 00:03:23,620
i sumem 1 al comptador d'intercanvi.

75
00:03:23,620 --> 00:03:25,490
2 i 3, estan en ordre.

76
00:03:25,490 --> 00:03:27,060
No necessitem fer res.

77
00:03:27,060 --> 00:03:28,420
3 i 5 són en ordre.

78
00:03:28,420 --> 00:03:30,150
No necessitem fer res allà.

79
00:03:30,150 --> 00:03:32,515
>> 5 i 4, estan fora
d'ordre, de manera que

80
00:03:32,515 --> 00:03:35,130
necessari per intercanviar i afegir
1 al comptador d'intercanvi.

81
00:03:35,130 --> 00:03:38,880
I ara ens hem mogut 5,
el següent element més gran,

82
00:03:38,880 --> 00:03:40,920
fins al final de la porció sense classificar.

83
00:03:40,920 --> 00:03:44,360
Així que ara podem anomenar a això
part de la porció ordenats.

84
00:03:44,360 --> 00:03:47,180
>> Ara vostè està buscant en el
pantalla i probablement pot dir,

85
00:03:47,180 --> 00:03:50,130
igual que jo, que la matriu
es classifica en aquest moment.

86
00:03:50,130 --> 00:03:51,820
Però no podem provar que encara.

87
00:03:51,820 --> 00:03:54,359
No tenim una garantia
que està ordenada.

88
00:03:54,359 --> 00:03:56,900
Però aquí és on el bescanvi
comptador que va entrar en joc.

89
00:03:56,900 --> 00:03:59,060
>> Així que hem completat una passada.

90
00:03:59,060 --> 00:04:00,357
El comptador d'intercanvi és de 2.

91
00:04:00,357 --> 00:04:02,190
Així que repetirem
aquest procés de nou,

92
00:04:02,190 --> 00:04:04,290
repetir fins que el comptador d'intercanvi és 0.

93
00:04:04,290 --> 00:04:05,550
Restablir el comptador d'intercanvi a 0.

94
00:04:05,550 --> 00:04:06,820
Així que anem a restablir-la.

95
00:04:06,820 --> 00:04:09,810
>> Ara mira cada parell adjacent.

96
00:04:09,810 --> 00:04:11,880
Aquest és la fi, 1 i 2.

97
00:04:11,880 --> 00:04:13,590
2 i 3 són en ordre.

98
00:04:13,590 --> 00:04:15,010
3 i 4 són en ordre.

99
00:04:15,010 --> 00:04:19,250
Així que en aquest punt, notem que hem completat
buscant en cada parell adjacent,

100
00:04:19,250 --> 00:04:22,530
però el comptador d'intercanvi continua sent 0.

101
00:04:22,530 --> 00:04:25,520
>> Si nosaltres no hem de canviar
qualsevol element, llavors

102
00:04:25,520 --> 00:04:28,340
ha d'estar en ordre, per
virtut d'aquest procés.

103
00:04:28,340 --> 00:04:32,000
I així una eficiència de classes,
que els científics de la computació ens encanta,

104
00:04:32,000 --> 00:04:35,560
està ara podem Declarem
tota la matriu ha de

105
00:04:35,560 --> 00:04:38,160
ser resolt, perquè no vam fer
haver de canviar cap element.

106
00:04:38,160 --> 00:04:40,380
Això és bastant agradable.

107
00:04:40,380 --> 00:04:43,260
>> Quin és el pitjor dels casos
escenari amb la bombolla del tipus?

108
00:04:43,260 --> 00:04:46,240
En el pitjor dels casos la matriu és
per tal completament inversa,

109
00:04:46,240 --> 00:04:49,870
i així tenim que la bombolla de cada
dels grans elements de tot

110
00:04:49,870 --> 00:04:51,780
el camí a través de la matriu.

111
00:04:51,780 --> 00:04:55,350
I efectivament tenim també
bombolla de tots els petits elements de retorn

112
00:04:55,350 --> 00:04:57,050
tot el camí a través de la matriu, també.

113
00:04:57,050 --> 00:05:01,950
Així cada un dels n elements ha de moure
a través de tots els altres elements n.

114
00:05:01,950 --> 00:05:04,102
Així que aquest és el pitjor dels casos.

115
00:05:04,102 --> 00:05:05,810
En el millor dels casos
escenari però, això és

116
00:05:05,810 --> 00:05:07,880
lleugerament diferent d'ordenació per selecció.

117
00:05:07,880 --> 00:05:10,040
La matriu és ja
ordenats quan anem a.

118
00:05:10,040 --> 00:05:12,550
Nosaltres no hem de fer cap
swaps en la primera passada.

119
00:05:12,550 --> 00:05:14,940
Així que pot ser que haguem de mirar
almenys elements, oi?

120
00:05:14,940 --> 00:05:18,580
No hem de repetir aquest
processar un nombre de vegades.

121
00:05:18,580 --> 00:05:19,540
>> Llavors, què vol dir això?

122
00:05:19,540 --> 00:05:22,390
Quin és el pitjor dels casos
d'ordenament de bombolla, i el que és

123
00:05:22,390 --> 00:05:25,330
el millor dels casos per a l'ordenació de bombolla?

124
00:05:25,330 --> 00:05:27,770
Sabia vostè endevina això?

125
00:05:27,770 --> 00:05:32,420
En el pitjor dels casos vostè ha de repetir
a través de tots els n elements n vegades.

126
00:05:32,420 --> 00:05:34,220
Així que el pitjor dels casos és N al quadrat.

127
00:05:34,220 --> 00:05:36,550
>> Si la matriu és perfectament
ordenada, però, només es

128
00:05:36,550 --> 00:05:38,580
cal mirar cada
dels elements d'una vegada.

129
00:05:38,580 --> 00:05:42,670
I si el comptador d'intercanvi segueix sent 0,
es pot dir que aquesta sèrie està ordenada.

130
00:05:42,670 --> 00:05:45,780
I així, en el millor dels casos, es tracta de
en realitat millor que la selecció

131
00:05:45,780 --> 00:05:49,230
sort-- és l'omega de n.

132
00:05:49,230 --> 00:05:50,270
>> Sóc Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Això és CS50.

134
00:05:52,140 --> 00:05:54,382