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

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Muy bien, así
ordenamiento de burbuja es un algoritmo

4
00:00:06,730 --> 00:00:08,730
se puede utilizar para ordenar un conjunto de elementos.

5
00:00:08,730 --> 00:00:10,850
Echemos un vistazo a cómo funciona.

6
00:00:10,850 --> 00:00:13,240
>> Así que la idea básica detrás
ordenamiento de burbuja es esto.

7
00:00:13,240 --> 00:00:17,340
Generalmente Queremos avanzar más alta
elementos valorados generalmente a la derecha,

8
00:00:17,340 --> 00:00:20,340
y bajar elementos valorados generalmente
a la izquierda, como era de esperar.

9
00:00:20,340 --> 00:00:23,256
Queremos que las cosas inferiores a estar en
el principio, y las cosas más elevadas

10
00:00:23,256 --> 00:00:24,970
a estar en el extremo.

11
00:00:24,970 --> 00:00:26,130
>> Cómo hacemos esto?

12
00:00:26,130 --> 00:00:28,040
Bueno en el código de pseudocódigo,
podríamos decir, vamos a

13
00:00:28,040 --> 00:00:30,320
fijar un contador de canje a un valor distinto de cero.

14
00:00:30,320 --> 00:00:32,570
Ya veremos qué hacemos eso en un segundo.

15
00:00:32,570 --> 00:00:36,090
Y luego repetimos el siguiente
proceso hasta que el contador de intercambio es 0,

16
00:00:36,090 --> 00:00:39,910
o hasta que no hacemos canjes en absoluto.

17
00:00:39,910 --> 00:00:43,170
>> Restablecer el contador de intercambio de
0 si no lo es ya 0.

18
00:00:43,170 --> 00:00:46,420
Luego, busquen en cada
par adyacente de elementos.

19
00:00:46,420 --> 00:00:49,550
Si esos dos elementos son
no en orden, ellos intercambiar,

20
00:00:49,550 --> 00:00:51,620
y añade 1 al contador de intercambio.

21
00:00:51,620 --> 00:00:53,870
Si usted está pensando en
esto antes de visualizarlo,

22
00:00:53,870 --> 00:00:57,471
observe que este se moverá más baja
elementos valiosos a la izquierda

23
00:00:57,471 --> 00:01:00,720
y más alto elementos a la derecha valorada,
haciendo con eficacia lo que queremos hacer,

24
00:01:00,720 --> 00:01:03,940
que es mover esos grupos
de elementos en esa forma.

25
00:01:03,940 --> 00:01:07,035
Vamos a visualizar cómo este
podría parecer utilizando nuestra gama

26
00:01:07,035 --> 00:01:10,504
que utilizamos para probar
estos algoritmos.

27
00:01:10,504 --> 00:01:13,420
Tenemos una gran variedad clasificar aquí de nuevo,
indicado por todos los elementos

28
00:01:13,420 --> 00:01:14,840
estando en rojo.

29
00:01:14,840 --> 00:01:17,970
Y volví mi contador de intercambio
a un valor distinto de cero.

30
00:01:17,970 --> 00:01:20,610
Yo elegí arbitrariamente
negativo 1-- no es 0.

31
00:01:20,610 --> 00:01:23,840
Queremos repetir este proceso
hasta que el contador de intercambio es de 0.

32
00:01:23,840 --> 00:01:26,540
Por eso me puse mi permuta
contador a algún valor distinto de cero,

33
00:01:26,540 --> 00:01:29,400
porque de lo contrario la
contador de intercambio sería 0.

34
00:01:29,400 --> 00:01:31,610
Ni siquiera podríamos comenzar el
proceso del algoritmo.

35
00:01:31,610 --> 00:01:33,610
Así que de nuevo, los pasos son--
restablecer el contador de intercambio

36
00:01:33,610 --> 00:01:37,900
a 0, a continuación, busque en cada lado
par, y si están fuera de servicio,

37
00:01:37,900 --> 00:01:40,514
intercambiarlos, y añadir 1
al mostrador de intercambio.

38
00:01:40,514 --> 00:01:41,680
Así que vamos a comenzar este proceso.

39
00:01:41,680 --> 00:01:44,430
Así que lo primero que hacemos es
nos pusimos en el mostrador de intercambio a 0,

40
00:01:44,430 --> 00:01:46,660
y luego empezar a buscar
en cada par adyacente.

41
00:01:46,660 --> 00:01:49,140
>> Así que primero empezar a buscar a las 5 y 2.

42
00:01:49,140 --> 00:01:52,410
Vemos que están fuera de
Orden y así que los swap.

43
00:01:52,410 --> 00:01:53,830
Y añadimos 1 al contador de intercambio.

44
00:01:53,830 --> 00:01:57,860
Así que ahora nuestro contador de intercambio es 1,
y 2 y 5 han sido conmutada.

45
00:01:57,860 --> 00:01:59,370
Ahora repetimos el proceso de nuevo.

46
00:01:59,370 --> 00:02:03,540
>> Nos fijamos en el siguiente par adyacente,
5 y 1-- están también fuera de orden,

47
00:02:03,540 --> 00:02:06,960
así que los swap y añadimos
1 al contador de intercambio.

48
00:02:06,960 --> 00:02:08,900
Entonces nos fijamos en 5 y 3.

49
00:02:08,900 --> 00:02:13,830
Ellos están fuera de servicio, por lo que intercambian
ellos y añadimos 1 al contador de intercambio.

50
00:02:13,830 --> 00:02:15,550
Entonces nos fijamos en 5 y 6.

51
00:02:15,550 --> 00:02:18,630
Están en orden, así que en realidad no
necesitará cambiar nada esta vez.

52
00:02:18,630 --> 00:02:20,250
Entonces nos fijamos en 6 y 4.

53
00:02:20,250 --> 00:02:24,920
Son también fuera de servicio, así que intercambian
ellos y añadimos 1 al contador de intercambio.

54
00:02:24,920 --> 00:02:26,230
>> Ahora note lo que ha pasado.

55
00:02:26,230 --> 00:02:29,514
Hemos pasado 6 de todo el camino hasta el final.

56
00:02:29,514 --> 00:02:32,180
Así que en la selección de especie, si tienes
visto ese video, lo que hicimos fue

57
00:02:32,180 --> 00:02:35,290
Terminamos cambiando la
los elementos más pequeños de la construcción

58
00:02:35,290 --> 00:02:39,640
la matriz ordenada esencialmente de
izquierda a derecha, de menor a mayor.

59
00:02:39,640 --> 00:02:43,200
En el caso de ordenamiento de burbuja, si somos
siguiendo este algoritmo en particular,

60
00:02:43,200 --> 00:02:46,720
estamos en realidad va a ser la construcción
la matriz ordenada de derecha

61
00:02:46,720 --> 00:02:49,100
a izquierda, de mayor a menor.

62
00:02:49,100 --> 00:02:53,840
Hemos burbujeó eficazmente 6, la
valor más grande, todo el camino hasta el final.

63
00:02:53,840 --> 00:02:56,165
>> Y así podemos ahora declarar
que eso se solucionó,

64
00:02:56,165 --> 00:02:59,130
y en el futuro iterations--
pasando por la matriz nuevo--

65
00:02:59,130 --> 00:03:01,280
no tenemos que considerar 6 más.

66
00:03:01,280 --> 00:03:03,850
Sólo tenemos que considerar
los elementos sin clasificar

67
00:03:03,850 --> 00:03:06,299
cuando estamos viendo pares adyacentes.

68
00:03:06,299 --> 00:03:08,340
Así que hemos terminado un solo
pasar a través de ordenamiento de burbuja.

69
00:03:08,340 --> 00:03:11,941
Así que ahora volvemos a la pregunta,
repetir hasta que el contador de intercambio es 0.

70
00:03:11,941 --> 00:03:13,690
Bueno el contador de intercambio
es 4, por lo que vamos

71
00:03:13,690 --> 00:03:15,410
seguir repitiendo este proceso de nuevo.

72
00:03:15,410 --> 00:03:19,180
>> Vamos a cero el contador de intercambio
a 0, y buscar en cada par adyacente.

73
00:03:19,180 --> 00:03:21,890
Así que empezamos con 2 y 1-- son
fuera de servicio, por lo que los intercambiamos

74
00:03:21,890 --> 00:03:23,620
y sumamos 1 al contador de intercambio.

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

76
00:03:25,490 --> 00:03:27,060
No necesitamos hacer nada.

77
00:03:27,060 --> 00:03:28,420
3 y 5 son en orden.

78
00:03:28,420 --> 00:03:30,150
No necesitamos hacer nada allí.

79
00:03:30,150 --> 00:03:32,515
>> 5 y 4, están fuera
de orden, por lo que

80
00:03:32,515 --> 00:03:35,130
necesario para intercambiarlas y añadir
1 al contador de intercambio.

81
00:03:35,130 --> 00:03:38,880
Y ahora nos hemos movido 5,
el siguiente elemento más grande,

82
00:03:38,880 --> 00:03:40,920
hasta el final de la porción sin clasificar.

83
00:03:40,920 --> 00:03:44,360
Así que ahora podemos llamar a eso
parte de la porción ordenados.

84
00:03:44,360 --> 00:03:47,180
>> Ahora usted está buscando en el
pantalla y probablemente puede decir,

85
00:03:47,180 --> 00:03:50,130
al igual que yo, que la matriz
se clasifica en este momento.

86
00:03:50,130 --> 00:03:51,820
Pero no podemos probar que todavía.

87
00:03:51,820 --> 00:03:54,359
No tenemos una garantía
que está ordenada.

88
00:03:54,359 --> 00:03:56,900
Pero aquí es donde el canje
contador que va a entrar en juego.

89
00:03:56,900 --> 00:03:59,060
>> Así que hemos completado un pase.

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

91
00:04:00,357 --> 00:04:02,190
Así que vamos a repetir
este proceso de nuevo,

92
00:04:02,190 --> 00:04:04,290
repetir hasta que el contador de intercambio es 0.

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

94
00:04:05,550 --> 00:04:06,820
Así que vamos a restablecerla.

95
00:04:06,820 --> 00:04:09,810
>> Ahora mira a cada par adyacente.

96
00:04:09,810 --> 00:04:11,880
Ese es el fin, 1 y 2.

97
00:04:11,880 --> 00:04:13,590
2 y 3 son en orden.

98
00:04:13,590 --> 00:04:15,010
3 y 4 son en orden.

99
00:04:15,010 --> 00:04:19,250
Así que en este punto, notamos que hemos completado
buscando en cada par adyacente,

100
00:04:19,250 --> 00:04:22,530
pero el contador de intercambio sigue siendo 0.

101
00:04:22,530 --> 00:04:25,520
>> Si nosotros no tenemos que cambiar
cualquier elemento, entonces

102
00:04:25,520 --> 00:04:28,340
debe estar en orden, por
virtud de este proceso.

103
00:04:28,340 --> 00:04:32,000
Y así una eficiencia de clases,
que los científicos de la computación nos encanta,

104
00:04:32,000 --> 00:04:35,560
está ahora podemos Declaramos
toda la matriz debe

105
00:04:35,560 --> 00:04:38,160
ser resuelto, porque no hicimos
tener que cambiar ningún elemento.

106
00:04:38,160 --> 00:04:40,380
Eso es bastante agradable.

107
00:04:40,380 --> 00:04:43,260
>> ¿Cuál es el peor de los casos
escenario con la burbuja del tipo?

108
00:04:43,260 --> 00:04:46,240
En el peor de los casos la matriz es
con el fin completamente inversa,

109
00:04:46,240 --> 00:04:49,870
y así tenemos que la burbuja de cada
de los grandes elementos de todo

110
00:04:49,870 --> 00:04:51,780
el camino a través de la matriz.

111
00:04:51,780 --> 00:04:55,350
Y efectivamente tenemos también
burbuja de todos los pequeños elementos de regreso

112
00:04:55,350 --> 00:04:57,050
todo el camino a través de la matriz, también.

113
00:04:57,050 --> 00:05:01,950
Así cada uno de los n elementos tiene que mover
a través de todos los otros elementos n.

114
00:05:01,950 --> 00:05:04,102
Así que ese es el peor de los casos.

115
00:05:04,102 --> 00:05:05,810
En el mejor de los casos
escenario sin embargo, esto es

116
00:05:05,810 --> 00:05:07,880
ligeramente diferente de ordenación por selección.

117
00:05:07,880 --> 00:05:10,040
La matriz es ya
ordenados cuando vamos en.

118
00:05:10,040 --> 00:05:12,550
Nosotros no tenemos que hacer ninguna
swaps en la primera pasada.

119
00:05:12,550 --> 00:05:14,940
Así que puede ser que tengamos que mirar
por lo menos elementos, ¿verdad?

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

121
00:05:18,580 --> 00:05:19,540
>> ¿Entonces que significa eso?

122
00:05:19,540 --> 00:05:22,390
¿Cuál es el peor de los casos
de ordenamiento de burbuja, y lo que es

123
00:05:22,390 --> 00:05:25,330
el mejor de los casos para la ordenación de burbuja?

124
00:05:25,330 --> 00:05:27,770
¿Sabía usted adivina esto?

125
00:05:27,770 --> 00:05:32,420
En el peor de los casos usted tiene que repetir
a través de todos los n elementos n veces.

126
00:05:32,420 --> 00:05:34,220
Así que el peor de los casos es N al cuadrado.

127
00:05:34,220 --> 00:05:36,550
>> Si la matriz es perfectamente
ordenada, sin embargo, sólo se

128
00:05:36,550 --> 00:05:38,580
hay que mirar en cada
de los elementos de una vez.

129
00:05:38,580 --> 00:05:42,670
Y si el contador de intercambio sigue siendo 0,
se puede decir que esta serie está ordenada.

130
00:05:42,670 --> 00:05:45,780
Y así, en el mejor de los casos, se trata de
en realidad mejor que la selección

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

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

133
00:05:50,270 --> 00:05:52,140
Esto es CS50.

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