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

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

3
00:00:10,390 --> 00:00:13,520
Así como tipo de inserción e da burbulla
sort, Quicksort é un algoritmo para

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

5
00:00:15,720 --> 00:00:19,080
Para simplificar, imos supor que os
cousas son só números enteiros, pero

6
00:00:19,080 --> 00:00:22,060
saber que Quicksort traballa para
máis que números.

7
00:00:22,060 --> 00:00:24,720
Inicio rápido é un pouco máis complicado
de inserción ou burbulla, pero é

8
00:00:24,720 --> 00:00:27,560
tamén moito máis eficiente
na maioría dos casos.

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

10
00:00:28,150 --> 00:00:30,760
El acaba de dicir "máis
casos "non" todo "?

11
00:00:30,760 --> 00:00:31,710
Curiosamente, non.

12
00:00:31,710 --> 00:00:33,560
Non todos os problemas son os mesmos.

13
00:00:33,560 --> 00:00:36,650
Non hai problema con ese detalle, se
non vin notación O gran aínda, pero

14
00:00:36,650 --> 00:00:39,730
Quicksort é un O (n ao cadrado) algoritmo
no peor dos casos, só como

15
00:00:39,730 --> 00:00:41,430
inserción ou bubble sort.

16
00:00:41,430 --> 00:00:44,950
Con todo, el xeralmente actúa moito máis
como unha m algoritmo analóxico antigo.

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

18
00:00:45,750 --> 00:00:46,810
Volveremos a iso máis tarde.

19
00:00:46,810 --> 00:00:49,610
Pero, polo de agora, imos só aprender
Quicksort como funciona.

20
00:00:49,610 --> 00:00:53,080
>> Entón, imos camiñar por este Quicksorting
array de enteiros de menor

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

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

23
00:01:00,110 --> 00:01:03,480
Primeiro, seleccione o elemento final de
esa matriz - neste caso, dous -

24
00:01:03,480 --> 00:01:06,870
e chamar iso de "pivot". Logo nós
comezar a ollar para dúas cousas -

25
00:01:06,870 --> 00:01:10,220
un, o menor índice, que vou referir
como ir á dereita do

26
00:01:10,220 --> 00:01:13,970
a parede, e, dous, máis á esquerda
elemento, que eu vou chamar de "actual

27
00:01:13,970 --> 00:01:17,260
elemento. "Que imos facer é
mirar todos os outros elementos, outros

28
00:01:17,260 --> 00:01:20,930
que o pivote, e poñer todos os elementos
menor que o pivote ao

29
00:01:20,930 --> 00:01:24,140
esquerda do muro e todos aqueles
maior que o pivote ao

30
00:01:24,140 --> 00:01:25,570
dereita da pantalla.

31
00:01:25,570 --> 00:01:29,560
Entón, finalmente, imos soltar o pivote
dereito na parede para poñelas entre

32
00:01:29,560 --> 00:01:32,970
todos os números menores que
e todos os números máis grandes.

33
00:01:32,970 --> 00:01:34,460
>> Entón, imos facelo.

34
00:01:34,460 --> 00:01:38,540
Colla o 2, engada a parede no
comezando, e chamar a 6 o "actual

35
00:01:38,540 --> 00:01:41,590
elemento. "Por iso, queremos mirar
noso elemento actual, o 6.

36
00:01:41,590 --> 00:01:44,200
E xa que é maior que o
2, nós deixar alí para o

37
00:01:44,200 --> 00:01:45,610
dereita da pantalla.

38
00:01:45,610 --> 00:01:48,980
Logo pasamos a mirar o 5 como o noso
elemento actual e ver que esta

39
00:01:48,980 --> 00:01:51,840
é, unha vez máis, maior que o pivote, de xeito que
deixar onde está á dereita

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

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

42
00:01:53,880 --> 00:01:56,750
O noso elemento actual é
agora 1 e - oh.

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

44
00:01:58,030 --> 00:02:00,890
O elemento actual é agora menor que
o pivote, polo que queremos poñelas

45
00:02:00,890 --> 00:02:02,570
á esquerda da pantalla.

46
00:02:02,570 --> 00:02:06,555
Para iso, imos cambiar o
elemento actual co menor índice de

47
00:02:06,555 --> 00:02:07,970
sentado á dereita do muro.

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

49
00:02:14,050 --> 00:02:17,570
Agora pasamos a parede por riba de un índice
de xeito que o 1 está á esquerda

50
00:02:17,570 --> 00:02:19,750
lado do muro agora.

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

52
00:02:20,310 --> 00:02:23,450
Eu só confunde os elementos da
parte dereita da pantalla, non foi?

53
00:02:23,450 --> 00:02:23,890
Non te preocupes.

54
00:02:23,890 --> 00:02:24,930
Iso é bo.

55
00:02:24,930 --> 00:02:27,570
O único que nos preocupa polo de agora
é que todos estes elementos ao

56
00:02:27,570 --> 00:02:29,570
dereita do muro é maior
que o pivote.

57
00:02:29,570 --> 00:02:31,760
Sen orde real é asumido aínda.

58
00:02:31,760 --> 00:02:33,200
>> Agora, de volta á clasificación.

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

60
00:02:35,840 --> 00:02:39,075
E neste caso, podemos ver que hai
non hai outros elementos menor que o

61
00:02:39,075 --> 00:02:42,100
pivot, polo que deixalos todos na
na parte dereita da pantalla.

62
00:02:42,100 --> 00:02:45,980
Por último, chegamos ao elemento actual
e ver que é o pivote.

63
00:02:45,980 --> 00:02:48,830
Agora, isto significa que temos dous
seccións da matriz, sendo o primeiro

64
00:02:48,830 --> 00:02:51,820
pequeno sobre o pivote e na parte esquerda
do muro, eo segundo sendo

65
00:02:51,820 --> 00:02:54,500
maior que o pivote ao
lado dereito da pantalla.

66
00:02:54,500 --> 00:02:57,040
Queremos poñer o elemento pivote entre
os dous, e entón saberemos

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

68
00:03:01,000 --> 00:03:04,980
Entón trocamos o primeiro elemento na
parte dereita da pantalla, co pivote,

69
00:03:04,980 --> 00:03:06,410
e sabemos do pivote
na súa posición correcta.

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

71
00:03:11,130 --> 00:03:15,650
>> A continuación, repita este proceso para o
subarrays esquerda e á dereita do pivote.

72
00:03:15,650 --> 00:03:18,700
Xa que a última sub-disposición é só un
elemento longo, sabemos que xa está

73
00:03:18,700 --> 00:03:22,480
ordenada, porque como pode estar fóra de
solicitar se é só un elemento?

74
00:03:22,480 --> 00:03:28,860
Para o lado dereito da sub-disposición, temos
ver que o pivote é 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 actual tamén
comeza como o 6.

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

78
00:03:36,200 --> 00:03:38,590
Nós deixar onde está a
lado dereito da pantalla.

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

80
00:03:41,060 --> 00:03:44,160
Entón imos cambiar isto co primeiro elemento
logo á dereita da pantalla.

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

82
00:03:47,944 --> 00:03:50,750
Agora, me mudei a parede ata un.

83
00:03:50,750 --> 00:03:53,010
Agora, pasar á 8.

84
00:03:53,010 --> 00:03:56,480
8 é maior que 5,
e por iso deixar.

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

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 proceso no
lados da matriz da esquerda e da dereita. nós

91
00:04:13,670 --> 00:04:17,010
escoller un pivote e facer as comparacións
e crear outro nivel de esquerda e

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

93
00:04:18,240 --> 00:04:21,500
Esta chamada recursiva continuará ata
chegamos ao final cando temos

94
00:04:21,500 --> 00:04:25,290
dividido a matriz global en
só subarrays de lonxitude 1.

95
00:04:25,290 --> 00:04:28,060
De alí, sabemos que a matriz é clasificada
xa que cada elemento ten, polo

96
00:04:28,060 --> 00:04:29,330
nalgún momento, foi un pivote.

97
00:04:29,330 --> 00:04:32,720
Noutras palabras, para cada elemento, todos
os números á esquerda son menores

98
00:04:32,720 --> 00:04:36,420
valores e todos os números ao
dereito teñen maiores valores.

99
00:04:36,420 --> 00:04:38,980
>> Este método funciona moi ben se o
valor do pivote é escollido

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

101
00:04:41,930 --> 00:04:45,630
Isto significaría que, despois de pasarmos
elementos ao redor, hai preto de tantas

102
00:04:45,630 --> 00:04:48,390
elementos á esquerda do eixe de rotación
como hai á dereita.

103
00:04:48,390 --> 00:04:52,380
E a natureza divide e conquista de
Algoritmo Quicksort é entón levado

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

105
00:04:53,850 --> 00:04:57,500
Isto xera un tempo de execución de O (n log n,)
o n porque temos que facer n menos 1

106
00:04:57,500 --> 00:05:01,640
comparacións en cada xeración e rexistro
n porque temos que dividir a lista

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

108
00:05:03,210 --> 00:05:06,160
Con todo, no peor dos casos, este
algoritmo realmente pode ser o (n

109
00:05:06,160 --> 00:05:09,850
cadrado.) Supoña en cada xeración,
o pivote só acontece a ser o

110
00:05:09,850 --> 00:05:12,520
menor ou o máis grande dos
números que estamos clasificación.

111
00:05:12,520 --> 00:05:15,870
Isto significaría romper a lista
n veces e toma n menos 1

112
00:05:15,870 --> 00:05:17,690
comparacións en cada momento.

113
00:05:17,690 --> 00:05:20,490
Así, o de n ao cadrado.

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

115
00:05:22,000 --> 00:05:25,100
Unha boa forma de mellorar o método é
para reducir a probabilidade de que

116
00:05:25,100 --> 00:05:28,150
o tempo de execución é sempre certo
o de n ao cadrado.

117
00:05:28,150 --> 00:05:31,860
Teña en conta que diso peor, peor escenario
só pode ocorrer cando o

118
00:05:31,860 --> 00:05:35,320
pivote elixido é sempre a máis
ou menor valor na matriz.

119
00:05:35,320 --> 00:05:38,630
Para garantir isto é menos probable de ocorrer,
podemos atopar o pivote por

120
00:05:38,630 --> 00:05:42,610
escoller varios elementos e
tomando o valor mediano.

121
00:05:42,610 --> 00:05:44,650
>> O 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, imos supor que os
cousas son só números enteiros, pero

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
Sentímolo.

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

128
00:06:02,000 --> 00:06:03,200
>> COLUMNA 1: Serio?

129
00:06:03,200 --> 00:06:04,850
>> COLUMNA 2: Non deixa por aí.

130
00:06:04,850 --> 00:06:06,100
>> COLUMNA 1: Serio?

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