1
00:00:00,000 --> 00:00:03,360
>> [Música tocando]

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

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: Todo ben, entón
bubble sort é un algoritmo

4
00:00:06,730 --> 00:00:08,730
pode usar para clasificar un conxunto de elementos.

5
00:00:08,730 --> 00:00:10,850
Imos dar un ollo a como funciona.

6
00:00:10,850 --> 00:00:13,240
>> Así, a idea básica por tras
bubble sort é este.

7
00:00:13,240 --> 00:00:17,340
Nós xeralmente queren mover superior
elementos valorados xeralmente cara á dereita,

8
00:00:17,340 --> 00:00:20,340
e diminuír elementos valorados en xeral
á esquerda, como sería de esperar.

9
00:00:20,340 --> 00:00:23,256
Queremos que as cousas máis baixas para estar en
o principio, e as cousas máis elevadas

10
00:00:23,256 --> 00:00:24,970
ser ao final.

11
00:00:24,970 --> 00:00:26,130
>> Como podemos facer isto?

12
00:00:26,130 --> 00:00:28,040
Ben no código pseudocódigo,
poderiamos dicir, imos

13
00:00:28,040 --> 00:00:30,320
definir un contador de intercambio para un valor distinto de cero.

14
00:00:30,320 --> 00:00:32,570
A ver por que facemos isto nun segundo.

15
00:00:32,570 --> 00:00:36,090
E, despois, repetir o seguinte
proceso ata que o contador de intercambio é 0,

16
00:00:36,090 --> 00:00:39,910
ou ata que non facemos swaps en todo.

17
00:00:39,910 --> 00:00:43,170
>> Reinicie o contador de intercambio para
0 se non é xa 0.

18
00:00:43,170 --> 00:00:46,420
A continuación, ollar para cada
par adxacente de elementos.

19
00:00:46,420 --> 00:00:49,550
Se estes dous elementos son
non en orde, troca-los,

20
00:00:49,550 --> 00:00:51,620
e engadir 1 ao contador de intercambio.

21
00:00:51,620 --> 00:00:53,870
Se está a pensar en
que antes de vela,

22
00:00:53,870 --> 00:00:57,471
notar que este pode mover máis baixo
elementos valiosos á esquerda

23
00:00:57,471 --> 00:01:00,720
e elementos para a dereita valorado superior,
efectivamente facendo o que queremos facer,

24
00:01:00,720 --> 00:01:03,940
que é mover eses grupos
de elementos en que xeito.

25
00:01:03,940 --> 00:01:07,035
Imos ver como este
pode parecer a través da nosa gama

26
00:01:07,035 --> 00:01:10,504
que foi utilizado para probar
estes algoritmos.

27
00:01:10,504 --> 00:01:13,420
Temos unha matriz unsorted aquí de novo,
indicado por todos os elementos

28
00:01:13,420 --> 00:01:14,840
sendo a vermello.

29
00:01:14,840 --> 00:01:17,970
E eu que o meu contador de intercambio
para un valor distinto de cero.

30
00:01:17,970 --> 00:01:20,610
Eu escollín arbitrariamente
1-- negativo non é 0.

31
00:01:20,610 --> 00:01:23,840
Queremos repetir este proceso
ata que o contador de intercambio é 0.

32
00:01:23,840 --> 00:01:26,540
É por iso que eu definir a miña cambio
contador para un valor distinto de cero,

33
00:01:26,540 --> 00:01:29,400
porque se non o
contador de intercambio sería 0.

34
00:01:29,400 --> 00:01:31,610
Nós nin sequera comezar a
proceso do algoritmo.

35
00:01:31,610 --> 00:01:33,610
Entón, de novo, os pasos é--
axustar o temporizador de intercambio

36
00:01:33,610 --> 00:01:37,900
a 0, a continuación, ollar para cada lado
par, e no caso de que están fóra de orde,

37
00:01:37,900 --> 00:01:40,514
trocalos e engadir 1
para o contador de intercambio.

38
00:01:40,514 --> 00:01:41,680
Entón, imos comezar este proceso.

39
00:01:41,680 --> 00:01:44,430
Entón o primeiro que facemos é
imos definir o contador de intercambio a 0,

40
00:01:44,430 --> 00:01:46,660
e, despois, comezar a ollar
en cada par adxacente.

41
00:01:46,660 --> 00:01:49,140
>> Así que comezamos a mirar para 5 e 2.

42
00:01:49,140 --> 00:01:52,410
Vemos que están fóra de
orde e para que trocalos.

43
00:01:52,410 --> 00:01:53,830
E nós engadimos 1 ao contador intercambio.

44
00:01:53,830 --> 00:01:57,860
Polo tanto, agora o noso contador de intercambio é un,
e 2 e 5 foron trocados.

45
00:01:57,860 --> 00:01:59,370
Agora imos repetir o proceso de novo.

46
00:01:59,370 --> 00:02:03,540
>> Nós miramos para a próxima par adxacente,
5 e 1-- son tamén fóra de orde,

47
00:02:03,540 --> 00:02:06,960
así que trocalos e engadir
1 ao balcón intercambio.

48
00:02:06,960 --> 00:02:08,900
Entón, miramos para 5 e 3.

49
00:02:08,900 --> 00:02:13,830
Eles están fóra de orde, polo que trocar
eles e nós engadimos 1 ao contador intercambio.

50
00:02:13,830 --> 00:02:15,550
Entón, miramos para 5 e 6.

51
00:02:15,550 --> 00:02:18,630
Eles están en orde, polo que, en realidade, non
Debe cambiar calquera cousa neste momento.

52
00:02:18,630 --> 00:02:20,250
Entón, miramos para 6 e 4.

53
00:02:20,250 --> 00:02:24,920
Eles están fóra de orde, polo que trocar
eles e nós engadimos 1 ao contador intercambio.

54
00:02:24,920 --> 00:02:26,230
>> Agora, teña en conta o que pasou.

55
00:02:26,230 --> 00:02:29,514
Nós movemos 6 todo o camiño ata o final.

56
00:02:29,514 --> 00:02:32,180
Entón, na selección tipo, se ten
visto que o vídeo, o que fixemos foi

57
00:02:32,180 --> 00:02:35,290
acabamos cambiando a
menores elementos en construción

58
00:02:35,290 --> 00:02:39,640
a matriz clasificada esencialmente da
esquerda a dereita, menor ao maior.

59
00:02:39,640 --> 00:02:43,200
No caso de bubble sort, se estamos
seguindo este algoritmo en particular,

60
00:02:43,200 --> 00:02:46,720
imos realmente a ser a construción de
a matriz clasificada da dereita

61
00:02:46,720 --> 00:02:49,100
á esquerda, maior a menor.

62
00:02:49,100 --> 00:02:53,840
Temos efectivamente borbulhar 6, a
O maior valor, todo o camiño ata o final.

63
00:02:53,840 --> 00:02:56,165
>> E así podemos agora declarar
que é ordenada,

64
00:02:56,165 --> 00:02:59,130
e no futuro iterations--
pasando a matriz novamente--

65
00:02:59,130 --> 00:03:01,280
non hai que considerar 6 anymore.

66
00:03:01,280 --> 00:03:03,850
Nós só temos que considerar
os elementos sen clasificar

67
00:03:03,850 --> 00:03:06,299
cando nós estamos mirando para pares adxacentes.

68
00:03:06,299 --> 00:03:08,340
Entón, temos que rematar unha
pasar por bubble sort.

69
00:03:08,340 --> 00:03:11,941
Entón agora imos voltar á cuestión,
repetir ata que o contador de intercambio é 0.

70
00:03:11,941 --> 00:03:13,690
Ben, o contador de intercambio
é 4, entón imos

71
00:03:13,690 --> 00:03:15,410
para continuar a repetir este proceso de novo.

72
00:03:15,410 --> 00:03:19,180
>> Estamos indo para axustar o temporizador de intercambio
a 0, e ollar para cada par adxacente.

73
00:03:19,180 --> 00:03:21,890
Entón, imos comezar con dous e son 1--
fóra de orde, de xeito que trocalos

74
00:03:21,890 --> 00:03:23,620
e nós engadimos 1 ao contador intercambio.

75
00:03:23,620 --> 00:03:25,490
2 e 3, están en orde.

76
00:03:25,490 --> 00:03:27,060
Non necesitamos facer nada.

77
00:03:27,060 --> 00:03:28,420
3 e 5 están en orde.

78
00:03:28,420 --> 00:03:30,150
Non necesitamos facer nada alí.

79
00:03:30,150 --> 00:03:32,515
>> 5 e 4, están fóra
de orde, e por iso,

80
00:03:32,515 --> 00:03:35,130
Debe trocalos e engadir
1 ao balcón intercambio.

81
00:03:35,130 --> 00:03:38,880
E agora nós movemo 5,
o segundo elemento,

82
00:03:38,880 --> 00:03:40,920
para o fin da porción sen clasificar.

83
00:03:40,920 --> 00:03:44,360
Entón agora podemos chamar
parte da porción clasificada.

84
00:03:44,360 --> 00:03:47,180
>> Agora está mirando para o
pantalla e probablemente pode dicir,

85
00:03:47,180 --> 00:03:50,130
como pode I, que a matriz
se clasifica no momento.

86
00:03:50,130 --> 00:03:51,820
Pero non podemos probalo aínda.

87
00:03:51,820 --> 00:03:54,359
Non temos unha garantía
que está clasificado.

88
00:03:54,359 --> 00:03:56,900
Pero é aí onde o intercambio
contador vai entrar en xogo.

89
00:03:56,900 --> 00:03:59,060
>> Entón, nós completados un pase.

90
00:03:59,060 --> 00:04:00,357
O contador de intercambio é de 2.

91
00:04:00,357 --> 00:04:02,190
Entón, nós estamos indo a repetir
este proceso novo,

92
00:04:02,190 --> 00:04:04,290
repetir ata que o contador de intercambio é 0.

93
00:04:04,290 --> 00:04:05,550
Reinicie o contador de intercambio a 0.

94
00:04:05,550 --> 00:04:06,820
Entón, imos axustar-la.

95
00:04:06,820 --> 00:04:09,810
>> Agora mire para cada par adxacente.

96
00:04:09,810 --> 00:04:11,880
Isto é en orde, 1 e 2.

97
00:04:11,880 --> 00:04:13,590
2 e 3 están en orde.

98
00:04:13,590 --> 00:04:15,010
3 e 4 están en orde.

99
00:04:15,010 --> 00:04:19,250
Polo tanto, neste punto, observe nós completados
mirando para cada par adxacente,

100
00:04:19,250 --> 00:04:22,530
pero o contador de intercambio que é 0.

101
00:04:22,530 --> 00:04:25,520
>> Se non temos que cambiar
calquera elementos, a continuación, eles

102
00:04:25,520 --> 00:04:28,340
deben estar en orde, por
virtude deste proceso.

103
00:04:28,340 --> 00:04:32,000
E así unha eficiencia de tipos,
que os científicos da computación que amamos,

104
00:04:32,000 --> 00:04:35,560
agora podemos declarar
toda a matriz debe

105
00:04:35,560 --> 00:04:38,160
son ordenados, porque non
ter que cambiar todos os elementos.

106
00:04:38,160 --> 00:04:40,380
Iso é moi bo.

107
00:04:40,380 --> 00:04:43,260
>> Entón, cal é o peor caso
escenario con bubble sort?

108
00:04:43,260 --> 00:04:46,240
No peor caso, a matriz é
a fin completamente inversa,

109
00:04:46,240 --> 00:04:49,870
e por iso temos que burbulla cada
dos grandes elementos todos

110
00:04:49,870 --> 00:04:51,780
a maneira a través da matriz.

111
00:04:51,780 --> 00:04:55,350
E nós tamén temos que efectivamente
burbulla todos os pequenos elementos de volta

112
00:04:55,350 --> 00:04:57,050
en toda a extensión da matriz, tamén.

113
00:04:57,050 --> 00:05:01,950
Así, cada un dos elementos n debe moverse
entre todos os outros elementos n.

114
00:05:01,950 --> 00:05:04,102
Entón ese é o peor escenario posible.

115
00:05:04,102 --> 00:05:05,810
No mellor dos casos
escenario, con todo, este é

116
00:05:05,810 --> 00:05:07,880
lixeiramente diferente da selección de clasificación.

117
00:05:07,880 --> 00:05:10,040
A matriz é xa
clasificadas cando imos.

118
00:05:10,040 --> 00:05:12,550
Non hai que facer calquera
swaps sobre a primeira pasaxe.

119
00:05:12,550 --> 00:05:14,940
Por iso, pode ter que ollar
polo menos elementos, non?

120
00:05:14,940 --> 00:05:18,580
Non temos que repetir este
procesar un certo número de veces.

121
00:05:18,580 --> 00:05:19,540
>> Entón, o que significa isto?

122
00:05:19,540 --> 00:05:22,390
Entón, cal é o peor escenario
para bubble sort, eo que é

123
00:05:22,390 --> 00:05:25,330
o mellor escenario para bubble sort?

124
00:05:25,330 --> 00:05:27,770
Vostede creo que iso?

125
00:05:27,770 --> 00:05:32,420
No peor dos casos ten que facer unha iteración
en todos os elementos n veces n.

126
00:05:32,420 --> 00:05:34,220
Así, o peor caso é n ao cadrado.

127
00:05:34,220 --> 00:05:36,550
>> Se a matriz é perfectamente
ordenada, porén, só

128
00:05:36,550 --> 00:05:38,580
Ten que mirar para cada
os elementos dunha vez.

129
00:05:38,580 --> 00:05:42,670
E se o contador de intercambio que é 0,
pode dicir que esta matriz é clasificada.

130
00:05:42,670 --> 00:05:45,780
E así, no mellor dos casos, é dicir
realmente mellor que a selección

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

132
00:05:49,230 --> 00:05:50,270
>> Eu son Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Este é CS50.

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