1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Sorte de burbulla]

2
00:00:02,840 --> 00:00:04,560
[Jackson Steinkamp Universidade de Harvard]

3
00:00:04,560 --> 00:00:07,500
[Esta é CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Ordenar burbulla é un exemplo dun algoritmo de ordenación -

5
00:00:11,730 --> 00:00:14,460
é dicir, un proceso para a clasificación dun conxunto de elementos

6
00:00:14,460 --> 00:00:15,840
orde crecente ou decrecente.

7
00:00:15,840 --> 00:00:18,710
Por exemplo, se quere clasificar un array que contén os números

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], unha implementación correcta de Bubble Sort volvería

9
00:00:23,060 --> 00:00:26,260
array ordenado [2, 3, 5, 9], en orde crecente.

10
00:00:26,260 --> 00:00:28,850
Agora, eu vou explicar en pseudocódigo como o algoritmo funciona.

11
00:00:28,850 --> 00:00:34,000
>> Imos dicir que estamos ordenar unha lista de 5 números enteiros - 3, 2, 9, 6 e 5.

12
00:00:34,000 --> 00:00:37,650
O algoritmo comeza por mirar para os dous primeiros elementos, 3 e 2,

13
00:00:37,650 --> 00:00:40,850
e comprobar que eles están fóra de orde en relación ao outro.

14
00:00:40,850 --> 00:00:43,150
Son - 3 é maior que 2.

15
00:00:43,150 --> 00:00:45,190
Para estar en orde ascendente, que debe ser o contrario.

16
00:00:45,190 --> 00:00:46,610
Entón, nós troca-los.

17
00:00:46,610 --> 00:00:49,760
Agora, a lista fica así: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> A continuación, miramos para os segundo e terceiro elementos, 3 e 9.

19
00:00:52,450 --> 00:00:55,770
Eles están na orde correcta en relación ao outro.

20
00:00:55,770 --> 00:00:58,800
É dicir, 3 é inferior a 9 de modo que o algoritmo non troca-las.

21
00:00:58,800 --> 00:01:01,900
A continuación, miramos para 9 e 6. Eles están fóra de orde.

22
00:01:01,900 --> 00:01:04,260
>> Entón, necesitamos trocalos, porque 9 é maior que 6.

23
00:01:04,260 --> 00:01:08,840
Por fin, ollar para os últimos dous números enteiros, 9 e 5.

24
00:01:08,840 --> 00:01:10,850
Eles están fóra de orde, entón eles deben ser trocados.

25
00:01:10,850 --> 00:01:13,360
Tras a primeira pasaxe completa a través da lista,

26
00:01:13,360 --> 00:01:17,140
parece que esta: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Non é malo. É case clasificados.

28
00:01:19,690 --> 00:01:22,450
Pero necesitamos percorrer a lista de novo para obtelo completamente clasificados.

29
00:01:22,450 --> 00:01:29,250
Dous é menor que 3, de xeito que non troca-los.

30
00:01:29,250 --> 00:01:31,700
>> Tres é menor que 6, de modo que non troca-los.

31
00:01:31,700 --> 00:01:35,500
Seis é maior que 5. Trocamos.

32
00:01:35,500 --> 00:01:38,460
Seis é menor que 9. Non cambiar.

33
00:01:38,460 --> 00:01:42,170
Tras a segunda pasaxe, parece que este: [2, 3, 5, 6, 9]. Perfecto.

34
00:01:42,170 --> 00:01:44,680
Agora, imos escribir en pseudocódigo.

35
00:01:44,680 --> 00:01:48,450
Basicamente, para cada elemento da lista, temos que mirar para el

36
00:01:48,450 --> 00:01:50,060
eo elemento directamente á súa dereita.

37
00:01:50,060 --> 00:01:53,420
Se eles están fóra de orde en relación ao outro - é dicir, o elemento do lado esquerdo

38
00:01:53,420 --> 00:01:56,810
é maior que o da dereita - debemos cambiar os dous elementos.

39
00:01:56,810 --> 00:02:01,270
>> Facemos isto para cada elemento da lista, e nós fixemos unha pasaxe.

40
00:02:01,270 --> 00:02:05,160
Agora só temos que facer as veces de paso a través suficientes para asegurar a lista

41
00:02:05,160 --> 00:02:06,480
é totalmente, debidamente clasificados.

42
00:02:06,480 --> 00:02:08,889
Pero cantas veces temos que pasar a lista para

43
00:02:08,889 --> 00:02:10,400
garantir que estamos a facer?

44
00:02:10,400 --> 00:02:14,730
Ben, o peor escenario é se temos unha lista completamente para atrás.

45
00:02:14,730 --> 00:02:17,840
A continuación, el recibe un número de repasses igual ao número

46
00:02:17,840 --> 00:02:19,730
de elementos n-1.

47
00:02:19,730 --> 00:02:24,720
Se iso non ten sentido intuitivamente, pense en un caso sinxelo - unha lista [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Isto vai levar un paso para clasificar correctamente.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - O peor caso é que, con 3 elementos ordenados cara atrás,

50
00:02:33,060 --> 00:02:34,830
que vai levar 2 iterações para clasificar.

51
00:02:34,830 --> 00:02:37,980
Despois dunha iteração, é [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Os ingresos segundo a matriz clasificada [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Entón vostede sabe que non ten que ir a través da matriz, en xeral,

54
00:02:43,350 --> 00:02:46,790
máis que n-1 veces, onde n é o número de elementos na matriz.

55
00:02:47,090 --> 00:02:50,470
É chamado Bubble Sort porque as maiores elementos tenden a "burbulla-up '

56
00:02:50,470 --> 00:02:51,950
a dereita moi rapidamente.

57
00:02:51,950 --> 00:02:53,980
De feito, este algoritmo ten un comportamento moi interesante.

58
00:02:53,980 --> 00:02:57,410
>> Despois de iterações m través de toda a matriz,

59
00:02:57,410 --> 00:02:59,000
os elementos máis á dereita m son garantir

60
00:02:59,000 --> 00:03:01,000
para ser clasificado no seu lugar correcto.

61
00:03:01,000 --> 00:03:02,280
Se queres ver iso por si mesmo,

62
00:03:02,280 --> 00:03:05,500
podemos probalo nunha lista completamente para atrás [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Despois dunha pasaxe pola lista enteira,

64
00:03:08,220 --> 00:03:09,220
[Son da escritura]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2] [6, 5, 9, 3, 2] [6, 5, 3, 9, 2] [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
o elemento máis á dereita 9 está no seu debido lugar.

67
00:03:21,250 --> 00:03:24,760
Tras a segunda pasaxe, a 6 terá 'abrollou a' para o

68
00:03:24,760 --> 00:03:26,220
lugar máis á dereita segundo.

69
00:03:26,220 --> 00:03:28,840
Os dous elementos á dereita - 6 e 9 - estarán nos seus lugares correctos

70
00:03:28,840 --> 00:03:30,580
tras os dous primeiros repasses.

71
00:03:30,580 --> 00:03:32,590
>> Entón, como podemos usar isto para optimizar o algoritmo?

72
00:03:32,590 --> 00:03:34,850
Así, tras unha iteração través da matriz

73
00:03:34,850 --> 00:03:37,690
nós realmente non precisa comprobar o elemento máis á dereita

74
00:03:37,690 --> 00:03:39,200
porque sabemos que está clasificado.

75
00:03:39,200 --> 00:03:43,050
Despois de dúas iterações, sabemos con certeza que os dous elementos máis á dereita están no lugar.

76
00:03:43,050 --> 00:03:48,260
Polo tanto, en xeral, tras k iterações a través de todo o conxunto,

77
00:03:48,260 --> 00:03:51,550
comprobando os elementos últimas k é redundante xa que sabemos

78
00:03:51,550 --> 00:03:52,360
eles están no lugar correcto xa.

79
00:03:52,360 --> 00:03:54,870
>> Entón, se está clasificando un array de n elementos,

80
00:03:54,870 --> 00:03:57,870
na primeira iteração - ten que resolver todos os elementos - o primeiro n-0.

81
00:03:57,870 --> 00:04:04,170
Na segunda iteração, ten que mirar para todos os elementos, pero a última -

82
00:04:04,170 --> 00:04:07,090
o primeiro n-1.

83
00:04:07,090 --> 00:04:10,520
Outra optimización pode ser o de comprobar a lista xa está clasificado

84
00:04:10,520 --> 00:04:11,710
despois de cada iteração.

85
00:04:11,710 --> 00:04:13,900
Se xa clasificados, non precisamos facer algunha iterações

86
00:04:13,900 --> 00:04:15,310
a través da lista.

87
00:04:15,310 --> 00:04:16,220
Como podemos facer iso?

88
00:04:16,220 --> 00:04:19,360
Ben, se non facemos calquera cambio nunha pasaxe da lista,

89
00:04:19,360 --> 00:04:22,350
está claro que a lista xa estaba clasificado porque non cambiar nada.

90
00:04:22,350 --> 00:04:24,160
Entón, nós definitivamente non ten a sorte de novo.

91
00:04:24,160 --> 00:04:27,960
>> Talvez podes iniciar unha variable bandeira chamada "non clasificados" para

92
00:04:27,960 --> 00:04:30,990
false e cambia-lo para certo se ten que cambiar todos os elementos sobre

93
00:04:30,990 --> 00:04:32,290
unha iteração través da matriz.

94
00:04:32,290 --> 00:04:35,350
Ou mesmo, facer un contador para contar cantos swaps fai

95
00:04:35,350 --> 00:04:37,040
en calquera dada iteração.

96
00:04:37,040 --> 00:04:40,040
Ao final de cada iteração, se non cambiar calquera dos elementos,

97
00:04:40,040 --> 00:04:41,780
vostede sabe que a lista xa está clasificado e está feito.

98
00:04:41,780 --> 00:04:44,090
Ordenar burbulla, como algoritmos de ordenación outros, pode ser

99
00:04:44,090 --> 00:04:46,960
tweaked para traballar a todos os elementos que teñen un método de ordenación.

100
00:04:46,960 --> 00:04:50,610
>> É dicir, dados dous elementos que ten unha forma de dicir o primeiro

101
00:04:50,610 --> 00:04:53,770
é maior que, igual a ou menor que o segundo.

102
00:04:53,770 --> 00:04:56,870
Por exemplo, pode clasificar as letras do alfabeto, dicindo

103
00:04:56,870 --> 00:05:00,520
que a <b, b <c, etc

104
00:05:00,520 --> 00:05:03,830
Ou pode clasificar días da semana onde o domingo e menos de luns

105
00:05:03,830 --> 00:05:05,110
que é inferior a terceira.

106
00:05:05,110 --> 00:05:09,630
>> Ordenar burbulla é de ningunha maneira un algoritmo de ordenación moi eficiente ou rápido.

107
00:05:09,630 --> 00:05:12,370
Seu tempo de execución do peor caso é Big O de n ²

108
00:05:12,370 --> 00:05:14,810
porque ten que facer n iterações través dunha lista

109
00:05:14,810 --> 00:05:18,430
verificación de todos os n elementos cada paso, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Este tempo de execución significa que, como o número de elementos que está clasificando aumenta,

111
00:05:22,730 --> 00:05:24,330
o tempo de execución aumenta de forma cuadrática.

112
00:05:24,330 --> 00:05:27,330
>> Pero se a eficiencia non é unha gran preocupación do seu programa

113
00:05:27,330 --> 00:05:29,550
ou se está só a clasificación de un pequeno número de elementos,

114
00:05:29,550 --> 00:05:31,660
podes atopar Bubble Sort útil porque

115
00:05:31,660 --> 00:05:33,360
é un dos máis simple algoritmos de ordenación de entender

116
00:05:33,360 --> 00:05:34,250
e codificar.

117
00:05:34,250 --> 00:05:37,270
É tamén unha boa forma de comezar a experiencia coa tradución dun teórico

118
00:05:37,270 --> 00:05:40,220
algoritmo de código de funcionamento real.

119
00:05:40,220 --> 00:05:43,000
Ben, iso é unha especie de burbulla para ti. Grazas por asistir.

120
00:05:43,000 --> 00:05:44,000
CS50.TV