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: Tudo bem, então
bubble sort é um algoritmo

4
00:00:06,730 --> 00:00:08,730
você pode usar para classificar um conjunto de elementos.

5
00:00:08,730 --> 00:00:10,850
Vamos dar uma olhada em como ele funciona.

6
00:00:10,850 --> 00:00:13,240
>> Assim, a idéia básica por trás
bubble sort é este.

7
00:00:13,240 --> 00:00:17,340
Nós geralmente querem mover superior
elementos valorizados geralmente para a direita,

8
00:00:17,340 --> 00:00:20,340
e diminuir elementos valorizados em geral
para a esquerda, como seria de esperar.

9
00:00:20,340 --> 00:00:23,256
Queremos que as coisas mais baixas para estar em
o início, e as coisas mais elevadas

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

11
00:00:24,970 --> 00:00:26,130
>> Como vamos fazer isso?

12
00:00:26,130 --> 00:00:28,040
Bem no código pseudocódigo,
poderíamos dizer, vamos

13
00:00:28,040 --> 00:00:30,320
definir um contador de swap para um valor diferente de zero.

14
00:00:30,320 --> 00:00:32,570
Vamos ver por que fazemos isso em um segundo.

15
00:00:32,570 --> 00:00:36,090
E, depois, repetir o seguinte
processo até que o contador de swap é 0,

16
00:00:36,090 --> 00:00:39,910
ou até que não fazemos swaps em tudo.

17
00:00:39,910 --> 00:00:43,170
>> Reinicie o contador de swap para
0 se não é já 0.

18
00:00:43,170 --> 00:00:46,420
Em seguida, olhar para cada
par adjacente de elementos.

19
00:00:46,420 --> 00:00:49,550
Se esses dois elementos são
não em ordem, trocá-los,

20
00:00:49,550 --> 00:00:51,620
e adicionar 1 para o contador de swap.

21
00:00:51,620 --> 00:00:53,870
Se você está pensando em
isso antes de visualizá-la,

22
00:00:53,870 --> 00:00:57,471
notar que este irá mover mais baixo
elementos valiosos para a esquerda

23
00:00:57,471 --> 00:01:00,720
e elementos para a direita valorizado superior,
efetivamente fazendo o que nós queremos fazer,

24
00:01:00,720 --> 00:01:03,940
que é mover esses grupos
de elementos em que maneira.

25
00:01:03,940 --> 00:01:07,035
Vamos visualizar como este
pode parecer usando a nossa gama

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

27
00:01:10,504 --> 00:01:13,420
Nós temos uma matriz unsorted aqui novamente,
indicado por todos os elementos

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

29
00:01:14,840 --> 00:01:17,970
E eu definir o meu contador de swap
para um valor diferente de zero.

30
00:01:17,970 --> 00:01:20,610
Eu escolhi arbitrariamente
1-- negativo não é 0.

31
00:01:20,610 --> 00:01:23,840
Queremos repetir este processo
até que o contador de swap é 0.

32
00:01:23,840 --> 00:01:26,540
É por isso que eu definir a minha troca
contador para um valor diferente de zero,

33
00:01:26,540 --> 00:01:29,400
porque caso contrário o
contador de swap seria 0.

34
00:01:29,400 --> 00:01:31,610
Nós nem sequer começar a
processo do algoritmo.

35
00:01:31,610 --> 00:01:33,610
Então, novamente, os passos é--
redefinir o contador de swap

36
00:01:33,610 --> 00:01:37,900
a 0, em seguida, olhar para cada lado
par, e se eles estão fora de ordem,

37
00:01:37,900 --> 00:01:40,514
trocá-los, e adicionar 1
para o contador swap.

38
00:01:40,514 --> 00:01:41,680
Então, vamos começar esse processo.

39
00:01:41,680 --> 00:01:44,430
Então a primeira coisa que fazemos é
vamos definir o contador de swap a 0,

40
00:01:44,430 --> 00:01:46,660
e, depois, começar a olhar
em cada par adjacente.

41
00:01:46,660 --> 00:01:49,140
>> Assim que começamos a olhar para 5 e 2.

42
00:01:49,140 --> 00:01:52,410
Nós vemos que eles estão fora de
ordem e para que trocá-los.

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

44
00:01:53,830 --> 00:01:57,860
Portanto, agora o nosso contador de swap é um,
e 2 e 5 foram trocados.

45
00:01:57,860 --> 00:01:59,370
Agora vamos repetir o processo novamente.

46
00:01:59,370 --> 00:02:03,540
>> Nós olhamos para a próxima par adjacente,
5 e 1-- eles são também fora de ordem,

47
00:02:03,540 --> 00:02:06,960
assim que nós trocá-los e adicionar
1 para o balcão swap.

48
00:02:06,960 --> 00:02:08,900
Então, olhamos para 5 e 3.

49
00:02:08,900 --> 00:02:13,830
Eles estão fora de ordem, por isso, trocar
eles e nós adicionamos 1 ao contador swap.

50
00:02:13,830 --> 00:02:15,550
Então, olhamos para 5 e 6.

51
00:02:15,550 --> 00:02:18,630
Eles estão em ordem, por isso, na verdade, não
precisa trocar qualquer coisa neste momento.

52
00:02:18,630 --> 00:02:20,250
Então, olhamos para 6 e 4.

53
00:02:20,250 --> 00:02:24,920
Eles também estão fora de ordem, por isso, trocar
eles e nós adicionamos 1 ao contador swap.

54
00:02:24,920 --> 00:02:26,230
>> Agora, observe o que aconteceu.

55
00:02:26,230 --> 00:02:29,514
Nós movemos 6 todo o caminho até o fim.

56
00:02:29,514 --> 00:02:32,180
Então, na seleção tipo, se você tiver
visto que o vídeo, o que fizemos foi

57
00:02:32,180 --> 00:02:35,290
acabamos mudando a
menores elementos em construção

58
00:02:35,290 --> 00:02:39,640
a matriz classificada essencialmente da
esquerda para a direita, menor para o maior.

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

60
00:02:43,200 --> 00:02:46,720
nós estamos indo realmente para ser a construção de
a matriz classificada da direita

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

62
00:02:49,100 --> 00:02:53,840
Temos efetivamente borbulhar 6, a
O maior valor, todo o caminho até ao fim.

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

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

65
00:02:59,130 --> 00:03:01,280
não temos de considerar 6 anymore.

66
00:03:01,280 --> 00:03:03,850
Nós só temos que considerar
os elementos não triados

67
00:03:03,850 --> 00:03:06,299
quando nós estamos olhando para pares adjacentes.

68
00:03:06,299 --> 00:03:08,340
Então, temos que terminar uma
passar por bubble sort.

69
00:03:08,340 --> 00:03:11,941
Então agora vamos voltar para a questão,
repetir até que o contador de swap é 0.

70
00:03:11,941 --> 00:03:13,690
Bem, o contador de swap
é 4, então vamos

71
00:03:13,690 --> 00:03:15,410
para continuar a repetir esse processo novamente.

72
00:03:15,410 --> 00:03:19,180
>> Nós estamos indo para redefinir o contador de swap
a 0, e olhar para cada par adjacente.

73
00:03:19,180 --> 00:03:21,890
Então, vamos começar com dois e eles são 1--
fora de ordem, de modo que trocá-los

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

75
00:03:23,620 --> 00:03:25,490
2 e 3, eles estão em ordem.

76
00:03:25,490 --> 00:03:27,060
Nós não precisamos fazer nada.

77
00:03:27,060 --> 00:03:28,420
3 e 5 estão em ordem.

78
00:03:28,420 --> 00:03:30,150
Nós não precisamos fazer nada lá.

79
00:03:30,150 --> 00:03:32,515
>> 5 e 4, eles estão fora
de ordem, e por isso,

80
00:03:32,515 --> 00:03:35,130
precisa trocá-los e adicionar
1 para o balcão swap.

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

82
00:03:38,880 --> 00:03:40,920
para o fim da porção não triados.

83
00:03:40,920 --> 00:03:44,360
Então agora podemos chamar isso
parte da porção classificada.

84
00:03:44,360 --> 00:03:47,180
>> Agora você está olhando para o
tela e provavelmente pode dizer,

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

86
00:03:50,130 --> 00:03:51,820
Mas não podemos provar isso ainda.

87
00:03:51,820 --> 00:03:54,359
Não temos uma garantia
que está classificado.

88
00:03:54,359 --> 00:03:56,900
Mas é aí que o swap
contador vai entrar em jogo.

89
00:03:56,900 --> 00:03:59,060
>> Então, nós completamos um passe.

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

91
00:04:00,357 --> 00:04:02,190
Então, nós estamos indo para repetir
este processo novo,

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

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

94
00:04:05,550 --> 00:04:06,820
Então, vamos redefini-la.

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

96
00:04:09,810 --> 00:04:11,880
Isso é em ordem, 1 e 2.

97
00:04:11,880 --> 00:04:13,590
2 e 3 estão em ordem.

98
00:04:13,590 --> 00:04:15,010
3 e 4 estão em ordem.

99
00:04:15,010 --> 00:04:19,250
Portanto, neste ponto, observe nós completamos
olhando para cada par adjacente,

100
00:04:19,250 --> 00:04:22,530
mas o contador de swap ainda é 0.

101
00:04:22,530 --> 00:04:25,520
>> Se não temos de mudar
quaisquer elementos, em seguida, eles

102
00:04:25,520 --> 00:04:28,340
devem estar em ordem, por
virtude deste processo.

103
00:04:28,340 --> 00:04:32,000
E assim uma eficiência de tipos,
que os cientistas da computação que amamos,

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

105
00:04:35,560 --> 00:04:38,160
são ordenados, porque não
ter que trocar todos os elementos.

106
00:04:38,160 --> 00:04:40,380
Isso é muito bom.

107
00:04:40,380 --> 00:04:43,260
>> Então, qual é o pior caso
cenário com bubble sort?

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

109
00:04:46,240 --> 00:04:49,870
e por isso temos de bolha cada
dos grandes elementos todos

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

111
00:04:51,780 --> 00:04:55,350
E nós também temos que efetivamente
bolha todos os pequenos elementos de volta

112
00:04:55,350 --> 00:04:57,050
em toda a extensão da matriz, também.

113
00:04:57,050 --> 00:05:01,950
Assim, cada um dos elementos n tem de se mover
entre todos os outros elementos n.

114
00:05:01,950 --> 00:05:04,102
Então esse é o pior cenário possível.

115
00:05:04,102 --> 00:05:05,810
No melhor dos casos
cenário, porém, este é

116
00:05:05,810 --> 00:05:07,880
ligeiramente diferente da seleção de classificação.

117
00:05:07,880 --> 00:05:10,040
A matriz é já
classificadas quando vamos.

118
00:05:10,040 --> 00:05:12,550
Não temos de fazer qualquer
swaps sobre a primeira passagem.

119
00:05:12,550 --> 00:05:14,940
Por isso, pode ter que olhar
pelo menos elementos, certo?

120
00:05:14,940 --> 00:05:18,580
Nós não temos que repetir este
processar um certo número de vezes.

121
00:05:18,580 --> 00:05:19,540
>> Então, o que isso significa?

122
00:05:19,540 --> 00:05:22,390
Então, qual é o pior cenário
para bubble sort, eo que é

123
00:05:22,390 --> 00:05:25,330
o melhor cenário para bubble sort?

124
00:05:25,330 --> 00:05:27,770
Você acho que isso?

125
00:05:27,770 --> 00:05:32,420
No pior dos casos você tem que fazer uma iteração
em todos os elementos n vezes n.

126
00:05:32,420 --> 00:05:34,220
Assim, o pior caso é n ao quadrado.

127
00:05:34,220 --> 00:05:36,550
>> Se a matriz é perfeitamente
ordenada, porém, você só

128
00:05:36,550 --> 00:05:38,580
tem que olhar para cada
os elementos de uma vez.

129
00:05:38,580 --> 00:05:42,670
E se o contador de permuta ainda é 0,
você pode dizer que esta matriz é classificada.

130
00:05:42,670 --> 00:05:45,780
E assim, no melhor dos casos, isto é
realmente melhor do que a seleção

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

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

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

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