1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Oi, eu sou Mark
Grozen-Smith, e este é Quicksort.

3
00:00:10,390 --> 00:00:13,520
Assim como tipo de inserção e da bolha
sort, Quicksort é um algoritmo para

4
00:00:13,520 --> 00:00:15,720
ordenar uma lista ou uma matriz de coisas.

5
00:00:15,720 --> 00:00:19,080
Para simplificar, vamos supor que os
coisas são apenas números inteiros, mas

6
00:00:19,080 --> 00:00:22,060
saber que Quicksort trabalha para
mais do que apenas números.

7
00:00:22,060 --> 00:00:24,720
Início rápido é um pouco mais complicado
de inserção ou bolha, mas é

8
00:00:24,720 --> 00:00:27,560
também muito mais eficiente
na maioria dos casos.

9
00:00:27,560 --> 00:00:28,150
Espere um segundo.

10
00:00:28,150 --> 00:00:30,760
Ele acabou de dizer "mais
casos, "não" todos "?

11
00:00:30,760 --> 00:00:31,710
Curiosamente, não.

12
00:00:31,710 --> 00:00:33,560
Nem todos os casos são os mesmos.

13
00:00:33,560 --> 00:00:36,650
Não se preocupe com esse detalhe, se você
não vi notação O grande ainda, mas

14
00:00:36,650 --> 00:00:39,730
Quicksort é um O (n ao quadrado) algoritmo
na pior das hipóteses, apenas como

15
00:00:39,730 --> 00:00:41,430
inserção ou bubble sort.

16
00:00:41,430 --> 00:00:44,950
No entanto, ele geralmente age muito mais
como uma m algoritmo analógico antigo.

17
00:00:44,950 --> 00:00:45,750
Por quê?

18
00:00:45,750 --> 00:00:46,810
Voltaremos a isso mais tarde.

19
00:00:46,810 --> 00:00:49,610
Mas, por enquanto, vamos apenas aprender
Quicksort como funciona.

20
00:00:49,610 --> 00:00:53,080
>> Então, vamos caminhar por este Quicksorting
array de inteiros de menor

21
00:00:53,080 --> 00:00:54,260
para o maior.

22
00:00:54,260 --> 00:01:00,110
Aqui temos os inteiros 6,
5, 1, 3, 8, 4, 7, 9, e 2.

23
00:01:00,110 --> 00:01:03,480
Primeiro, escolha o elemento final de
essa matriz - neste caso, dois -

24
00:01:03,480 --> 00:01:06,870
e chamar isso de "pivot". Em seguida, nós
começar a olhar para duas coisas -

25
00:01:06,870 --> 00:01:10,220
um, o menor índice, que vou me referir
como ficar à direita do

26
00:01:10,220 --> 00:01:13,970
a parede, e, dois, mais à esquerda
elemento, que eu vou chamar de "atual

27
00:01:13,970 --> 00:01:17,260
elemento. "O que nós vamos fazer é
olhar todos os outros elementos, outros

28
00:01:17,260 --> 00:01:20,930
que o pivô, e colocar todos os elementos
menor do que o pivô ao

29
00:01:20,930 --> 00:01:24,140
esquerda da parede e todos aqueles
maior do que o pivô ao

30
00:01:24,140 --> 00:01:25,570
direita da parede.

31
00:01:25,570 --> 00:01:29,560
Então, finalmente, vamos soltar o pivô
direito na parede para colocá-lo entre

32
00:01:29,560 --> 00:01:32,970
todos os números menores do que
e todos os números maiores.

33
00:01:32,970 --> 00:01:34,460
>> Então, vamos fazer isso.

34
00:01:34,460 --> 00:01:38,540
Pegue o 2, coloque a parede no
começando, e chamar a 6 o "atual

35
00:01:38,540 --> 00:01:41,590
elemento. "Por isso, queremos olhar para
nosso elemento atual, o 6.

36
00:01:41,590 --> 00:01:44,200
E já que é maior do que o
2, nós deixá-lo lá para o

37
00:01:44,200 --> 00:01:45,610
direita da parede.

38
00:01:45,610 --> 00:01:48,980
Em seguida, passamos a olhar para o 5 como o nosso
elemento atual e ver que esta

39
00:01:48,980 --> 00:01:51,840
é, mais uma vez, maior do que o pivô, de modo que
deixá-lo onde está à direita

40
00:01:51,840 --> 00:01:53,190
lado da parede.

41
00:01:53,190 --> 00:01:53,880
Nós seguir em frente.

42
00:01:53,880 --> 00:01:56,750
Nosso elemento atual é
agora 1 e - oh.

43
00:01:56,750 --> 00:01:58,030
Isso é diferente agora.

44
00:01:58,030 --> 00:02:00,890
O elemento atual é agora menor do que
o pivô, por isso, queremos colocá-lo

45
00:02:00,890 --> 00:02:02,570
para a esquerda da parede.

46
00:02:02,570 --> 00:02:06,555
Para fazer isso, vamos mudar o
elemento atual com o menor índice de

47
00:02:06,555 --> 00:02:07,970
sentado à direita do muro.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Agora, passamos a parede acima de um índice
de modo que o 1 está à esquerda

50
00:02:17,570 --> 00:02:19,750
lado da parede agora.

51
00:02:19,750 --> 00:02:20,310
>> Espere.

52
00:02:20,310 --> 00:02:23,450
Eu só confunde os elementos da
lado direito da parede, não foi?

53
00:02:23,450 --> 00:02:23,890
Não se preocupe.

54
00:02:23,890 --> 00:02:24,930
Isso é bom.

55
00:02:24,930 --> 00:02:27,570
A única coisa que nos preocupamos por enquanto
é que todos estes elementos para o

56
00:02:27,570 --> 00:02:29,570
direita da parede é maior
que o pivô.

57
00:02:29,570 --> 00:02:31,760
Sem ordem real é assumido ainda.

58
00:02:31,760 --> 00:02:33,200
>> Agora, de volta para a classificação.

59
00:02:33,200 --> 00:02:35,840
Então, nós continuamos a olhar para
o resto dos elementos.

60
00:02:35,840 --> 00:02:39,075
E, neste caso, vemos que há
não há outros elementos menor do que o

61
00:02:39,075 --> 00:02:42,100
pivot, por isso deixá-los todos em
no lado direito da parede.

62
00:02:42,100 --> 00:02:45,980
Finalmente, chegamos ao elemento atual
e ver que ele é o pivô.

63
00:02:45,980 --> 00:02:48,830
Agora, isso significa que temos dois
seções da matriz, sendo o primeiro

64
00:02:48,830 --> 00:02:51,820
pequeno sobre o pivô e no lado esquerdo
do muro, eo segundo sendo

65
00:02:51,820 --> 00:02:54,500
maior do que o pivô ao
lado direito da parede.

66
00:02:54,500 --> 00:02:57,040
Queremos colocar o elemento pivô entre
os dois, e então saberemos

67
00:02:57,040 --> 00:03:01,000
que o pivô está no seu direito
lugar ordenada final.

68
00:03:01,000 --> 00:03:04,980
Então trocamos o primeiro elemento na
lado direito da parede, com o pivô,

69
00:03:04,980 --> 00:03:06,410
e sabemos do pivô
na sua posição correta.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Em seguida, repita este processo para o
subarrays esquerda e à direita do pivô.

72
00:03:15,650 --> 00:03:18,700
Uma vez que a última sub-disposição é apenas um
elemento longo, sabemos que já está

73
00:03:18,700 --> 00:03:22,480
ordenada, porque como você pode estar fora de
encomendar se você é apenas um elemento?

74
00:03:22,480 --> 00:03:28,860
Para o lado direito da sub-disposição, temos
ver que o pivô é 5, e a parede

75
00:03:28,860 --> 00:03:32,250
está à esquerda do 6.

76
00:03:32,250 --> 00:03:34,970
E o elemento atual também
começa como o 6.

77
00:03:34,970 --> 00:03:36,200
Assim 6 é maior do que 5.

78
00:03:36,200 --> 00:03:38,590
Nós deixá-lo onde está a
lado direito da parede.

79
00:03:38,590 --> 00:03:41,060
Passando agora, 3 é inferior a 5.

80
00:03:41,060 --> 00:03:44,160
Então vamos mudar isso com o primeiro elemento
logo à direita da parede.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Agora, me mudei a parede até um.

83
00:03:50,750 --> 00:03:53,010
Agora, passar para a 8.

84
00:03:53,010 --> 00:03:56,480
8 é maior do que 5,
e por isso deixá-lo.

85
00:03:56,480 --> 00:03:58,720
A 4 é inferior a 5, de modo que ele mude.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
E diante.

88
00:04:03,570 --> 00:04:04,820
E diante.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Cada vez que repetir o processo no
os lados da matriz da esquerda e da direita. nós

91
00:04:13,670 --> 00:04:17,010
escolher um pivô e fazer as comparações
e criar um outro nível de esquerda e

92
00:04:17,010 --> 00:04:18,240
subarrays direita.

93
00:04:18,240 --> 00:04:21,500
Esta chamada recursiva continuará até
chegamos ao fim quando temos

94
00:04:21,500 --> 00:04:25,290
dividido a matriz global em
apenas subarrays de comprimento 1.

95
00:04:25,290 --> 00:04:28,060
De lá, sabemos que a matriz é classificada
porque cada elemento tem, pelo

96
00:04:28,060 --> 00:04:29,330
algum momento, sido um pivô.

97
00:04:29,330 --> 00:04:32,720
Em outras palavras, para cada elemento, todos
os números à esquerda são menores

98
00:04:32,720 --> 00:04:36,420
valores e todos os números para o
direito têm maiores valores.

99
00:04:36,420 --> 00:04:38,980
>> Este método funciona muito bem se o
valor do pivô é escolhido

100
00:04:38,980 --> 00:04:41,930
aproximadamente no meio
intervalo de valores da lista.

101
00:04:41,930 --> 00:04:45,630
Isto significaria que, depois de passarmos
elementos ao redor, há cerca de tantas

102
00:04:45,630 --> 00:04:48,390
elementos à esquerda do eixo de rotação
como existem para a direita.

103
00:04:48,390 --> 00:04:52,380
E a natureza divide e conquista da
Algoritmo Quicksort é então levado

104
00:04:52,380 --> 00:04:53,850
aproveitar.

105
00:04:53,850 --> 00:04:57,500
Isso cria um tempo de execução de O (n log n,)
o n porque nós temos que fazer n menos 1

106
00:04:57,500 --> 00:05:01,640
comparações em cada geração e log
n porque temos que dividir a lista

107
00:05:01,640 --> 00:05:03,210
log n vezes.

108
00:05:03,210 --> 00:05:06,160
No entanto, no pior dos casos, este
algoritmo pode realmente ser o (n

109
00:05:06,160 --> 00:05:09,850
quadrado.) Suponha em cada geração,
o pivô só acontece a ser o

110
00:05:09,850 --> 00:05:12,520
menor ou o maior dos
números que estamos classificação.

111
00:05:12,520 --> 00:05:15,870
Isto significaria quebrar a lista
n vezes e tomada n menos 1

112
00:05:15,870 --> 00:05:17,690
comparações a cada momento.

113
00:05:17,690 --> 00:05:20,490
Assim, o de n ao quadrado.

114
00:05:20,490 --> 00:05:22,000
>> Como podemos melhorar o método?

115
00:05:22,000 --> 00:05:25,100
Uma boa maneira de melhorar o método é
para reduzir a probabilidade de que

116
00:05:25,100 --> 00:05:28,150
o tempo de execução é sempre verdade
o de n ao quadrado.

117
00:05:28,150 --> 00:05:31,860
Lembre-se disso pior, pior cenário
só pode acontecer quando o

118
00:05:31,860 --> 00:05:35,320
pivô escolhido é sempre a maior
ou menor valor na matriz.

119
00:05:35,320 --> 00:05:38,630
Para garantir isso é menos provável de acontecer,
podemos encontrar o pivô por

120
00:05:38,630 --> 00:05:42,610
escolher vários elementos e
tomando o valor mediano.

121
00:05:42,610 --> 00:05:44,650
>> Meu nome é Mark Grozen-Smith,
e este é CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> Para simplificar, vamos supor que os
coisas são apenas números inteiros, mas

124
00:05:50,930 --> 00:05:51,970
saber que Quicksert -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
Desculpe.

127
00:05:55,200 --> 00:06:02,000
>> Aqui temos os números inteiros
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> COLUNA 1: Sério?

129
00:06:03,200 --> 00:06:04,850
>> COLUNA 2: Não pára por aí.

130
00:06:04,850 --> 00:06:06,100
>> COLUNA 1: Sério?

131
00:06:06,100 --> 00:06:08,491