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

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Ciao, sono Marco
Grozen-Smith, e questo è Quicksort.

3
00:00:10,390 --> 00:00:13,520
Proprio come insertion sort e bubble
ordinamento, Quicksort è un algoritmo per

4
00:00:13,520 --> 00:00:15,720
l'ordinamento di un elenco o una serie di cose.

5
00:00:15,720 --> 00:00:19,080
Per semplicità, supponiamo che i
le cose sono solo numeri interi, ma

6
00:00:19,080 --> 00:00:22,060
sa che Quicksort lavora per
più che semplici numeri.

7
00:00:22,060 --> 00:00:24,720
Quickstart è un po 'più complicato
di inserimento o bolla, ma è

8
00:00:24,720 --> 00:00:27,560
anche molto più efficiente
nella maggior parte dei casi.

9
00:00:27,560 --> 00:00:28,150
Aspetta un secondo.

10
00:00:28,150 --> 00:00:30,760
Ha appena detto "più
casi ", non" tutti "?

11
00:00:30,760 --> 00:00:31,710
È interessante notare, no.

12
00:00:31,710 --> 00:00:33,560
Non tutti i casi sono uguali.

13
00:00:33,560 --> 00:00:36,650
Non preoccupatevi di questo dettaglio, se si
non hanno ancora visto la notazione O grande, ma

14
00:00:36,650 --> 00:00:39,730
Quicksort è un'operazione O (n al quadrato) algoritmo
nel peggiore dei casi, proprio come

15
00:00:39,730 --> 00:00:41,430
inserimento o bubble sort.

16
00:00:41,430 --> 00:00:44,950
Tuttavia, tipicamente agisce molto più
come un vecchio m algoritmo analogico.

17
00:00:44,950 --> 00:00:45,750
Perché?

18
00:00:45,750 --> 00:00:46,810
Torneremo più tardi.

19
00:00:46,810 --> 00:00:49,610
Ma per ora, facciamo solo imparare
come funziona Quicksort.

20
00:00:49,610 --> 00:00:53,080
>> Quindi cerchiamo di camminare attraverso Quicksorting questo
array di interi dal più piccolo

21
00:00:53,080 --> 00:00:54,260
al più grande.

22
00:00:54,260 --> 00:01:00,110
Qui abbiamo i numeri interi 6,
5, 1, 3, 8, 4, 7, 9, e 2.

23
00:01:00,110 --> 00:01:03,480
In primo luogo, prendiamo l'elemento finale del
questo array - in questo caso, due -

24
00:01:03,480 --> 00:01:06,870
e chiamare il "pivot". Successivamente, abbiamo
cominciare a guardare due cose -

25
00:01:06,870 --> 00:01:10,220
uno, il più basso indice, che mi riferirò
come stare a destra del

26
00:01:10,220 --> 00:01:13,970
la parete, e, due, il più a sinistra
elemento, che io chiamo la "corrente

27
00:01:13,970 --> 00:01:17,260
Elemento. "Quello che stiamo andando a fare è
guardare tutti gli altri elementi, altri

28
00:01:17,260 --> 00:01:20,930
del pivot, e mettere tutti gli elementi
minore del perno al

29
00:01:20,930 --> 00:01:24,140
sinistra del muro e tutti coloro
maggiore del perno al

30
00:01:24,140 --> 00:01:25,570
destro della parete.

31
00:01:25,570 --> 00:01:29,560
Poi, finalmente, faremo cadere il perno
proprio su quel muro per metterlo tra

32
00:01:29,560 --> 00:01:32,970
tutti i numeri inferiori a essa
e tutti i numeri più grandi.

33
00:01:32,970 --> 00:01:34,460
>> Allora facciamolo.

34
00:01:34,460 --> 00:01:38,540
Sollevare il 2, mettere la parete di
inizio, e chiamare il 6 la "corrente

35
00:01:38,540 --> 00:01:41,590
Elemento. "Allora vogliamo guardare
il nostro elemento corrente, il 6.

36
00:01:41,590 --> 00:01:44,200
E poiché è più grande della
2, lasciamo lì a

37
00:01:44,200 --> 00:01:45,610
destro della parete.

38
00:01:45,610 --> 00:01:48,980
Poi, si passa a guardare il 5 come il nostro
elemento corrente e vedere che questo

39
00:01:48,980 --> 00:01:51,840
è, di nuovo, più grande del pivot, quindi abbiamo
lasciarla dove è sulla destra

40
00:01:51,840 --> 00:01:53,190
lato del muro.

41
00:01:53,190 --> 00:01:53,880
Ci muoviamo su.

42
00:01:53,880 --> 00:01:56,750
Il nostro elemento corrente è
1 ora, e - oh.

43
00:01:56,750 --> 00:01:58,030
Questo è diverso ora.

44
00:01:58,030 --> 00:02:00,890
L'elemento corrente è ora più piccolo
il pivot, quindi vogliamo mettere

45
00:02:00,890 --> 00:02:02,570
a fianco della parete.

46
00:02:02,570 --> 00:02:06,555
Per fare questo, diciamo solo passare l'
elemento corrente con l'indice più basso

47
00:02:06,555 --> 00:02:07,970
seduta appena a destra della parete.

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

49
00:02:14,050 --> 00:02:17,570
Ora, passiamo il muro alto un indice
così l'1 è a sinistra

50
00:02:17,570 --> 00:02:19,750
lato del muro ora.

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

52
00:02:20,310 --> 00:02:23,450
Ho solo confuso gli elementi sulla
lato destro del muro, no?

53
00:02:23,450 --> 00:02:23,890
Non ti preoccupare.

54
00:02:23,890 --> 00:02:24,930
Va bene.

55
00:02:24,930 --> 00:02:27,570
L'unica cosa che ci interessa per ora
è che tutti questi elementi alla

56
00:02:27,570 --> 00:02:29,570
destra della parete sono più grandi
del pivot.

57
00:02:29,570 --> 00:02:31,760
Nessun ordine reale è ancora assunta.

58
00:02:31,760 --> 00:02:33,200
>> Ora, tornando alla cernita.

59
00:02:33,200 --> 00:02:35,840
Così continuiamo a guardare
il resto degli elementi.

60
00:02:35,840 --> 00:02:39,075
E in questo caso, si nota che ci sono
altri elementi inferiore al

61
00:02:39,075 --> 00:02:42,100
pivot, così noi tutti lasciamo sulla
il lato destro della parete.

62
00:02:42,100 --> 00:02:45,980
Infine, si arriva a l'elemento corrente
e vedere che è il perno.

63
00:02:45,980 --> 00:02:48,830
Ora, ciò significa che abbiamo due
sezioni della matrice, il primo essere

64
00:02:48,830 --> 00:02:51,820
piccola sul perno e sul lato sinistro
della parete, e il secondo essere

65
00:02:51,820 --> 00:02:54,500
maggiore del perno al
lato destro della parete.

66
00:02:54,500 --> 00:02:57,040
Vogliamo mettere l'elemento di cerniera tra
i due, e poi sapremo

67
00:02:57,040 --> 00:03:01,000
che il perno è nella sua destra
posto ordinato finale.

68
00:03:01,000 --> 00:03:04,980
Così passiamo il primo elemento sul
lato destro della parete con il perno,

69
00:03:04,980 --> 00:03:06,410
e sappiamo che il perno
nella sua posizione corretta.

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

71
00:03:11,130 --> 00:03:15,650
>> Abbiamo poi ripetere questo processo per l'
subarrays a sinistra ea destra del pivot.

72
00:03:15,650 --> 00:03:18,700
Dall'ultima sottomatrice è unico
lungo elemento, sappiamo che è già

73
00:03:18,700 --> 00:03:22,480
ordinato perché come si può essere fuori
ordinare se sei solo elemento?

74
00:03:22,480 --> 00:03:28,860
Per il lato destro della sottomatrice abbiamo
vedere che il perno è 5, e la parete

75
00:03:28,860 --> 00:03:32,250
è appena a sinistra del 6.

76
00:03:32,250 --> 00:03:34,970
E l'elemento corrente anche
inizia come il 6.

77
00:03:34,970 --> 00:03:36,200
Quindi 6 è maggiore di 5.

78
00:03:36,200 --> 00:03:38,590
Lasciamo dove si trova il
lato destro della parete.

79
00:03:38,590 --> 00:03:41,060
Ora, passando, 3 è inferiore a 5.

80
00:03:41,060 --> 00:03:44,160
Quindi passiamo con il primo elemento
appena a destra della parete.

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

82
00:03:47,944 --> 00:03:50,750
Ora, ho spostato il muro alto uno.

83
00:03:50,750 --> 00:03:53,010
Ora, passare al 8.

84
00:03:53,010 --> 00:03:56,480
8 è maggiore di 5,
e così ci lasciamo.

85
00:03:56,480 --> 00:03:58,720
Il 4 è a meno di 5, quindi abbiamo accenderlo.

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

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

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

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

90
00:04:10,190 --> 00:04:13,670
>> Ogni volta che si ripete il processo sul
lati sinistro e destro della matrice. noi

91
00:04:13,670 --> 00:04:17,010
scegliere un perno e fare i confronti
e creare un altro livello di sinistra e

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

93
00:04:18,240 --> 00:04:21,500
Questa chiamata ricorsiva continuerà fino
si arriva alla fine, quando abbiamo

94
00:04:21,500 --> 00:04:25,290
diviso l'array globale in
solo sottoarray di lunghezza 1.

95
00:04:25,290 --> 00:04:28,060
Da lì, sappiamo che l'array è ordinato
perché ogni elemento ha, a

96
00:04:28,060 --> 00:04:29,330
certo punto, passato un perno.

97
00:04:29,330 --> 00:04:32,720
In altre parole, per ogni elemento, tutti
i numeri a sinistra sono minori

98
00:04:32,720 --> 00:04:36,420
valori e tutti i numeri alla
destra hanno valori superiori.

99
00:04:36,420 --> 00:04:38,980
>> Questo metodo funziona molto bene se l'
valore del pivot scelto è

100
00:04:38,980 --> 00:04:41,930
circa a metà
intervallo dei valori della lista.

101
00:04:41,930 --> 00:04:45,630
Ciò significa che, dopo ci muoviamo
elementi intorno, ci sono circa altrettanti

102
00:04:45,630 --> 00:04:48,390
elementi a sinistra del perno
come ci sono a destra.

103
00:04:48,390 --> 00:04:52,380
E la natura divide et impera del
Algoritmo Quicksort viene poi ripreso

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

105
00:04:53,850 --> 00:04:57,500
Questo crea una autonomia di O (n log n,)
il n perché dobbiamo fare n meno 1

106
00:04:57,500 --> 00:05:01,640
confronti di ogni generazione e di registro
n perché dobbiamo dividere la lista

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

108
00:05:03,210 --> 00:05:06,160
Tuttavia, nei casi peggiori, questa
algoritmo può effettivamente essere O (n

109
00:05:06,160 --> 00:05:09,850
squadrato.) Supponiamo su ogni generazione,
il perno così succede di essere il

110
00:05:09,850 --> 00:05:12,520
più piccolo o il più grande dei
numeri stiamo ordinamento.

111
00:05:12,520 --> 00:05:15,870
Ciò significherebbe abbattere l'elenco
n tempi e le decisioni n meno 1

112
00:05:15,870 --> 00:05:17,690
confronti ogni volta.

113
00:05:17,690 --> 00:05:20,490
Quindi, o di n quadrati.

114
00:05:20,490 --> 00:05:22,000
>> Come possiamo migliorare il metodo?

115
00:05:22,000 --> 00:05:25,100
Un buon modo per migliorare il metodo è
per ridurre la probabilità che

116
00:05:25,100 --> 00:05:28,150
il runtime è mai realmente
o di n al quadrato.

117
00:05:28,150 --> 00:05:31,860
Ricordate questo peggiore, peggiore delle ipotesi
può avvenire solo quando la

118
00:05:31,860 --> 00:05:35,320
perno scelto è sempre la massima
o valore più basso nella matrice.

119
00:05:35,320 --> 00:05:38,630
Per garantire questo è meno probabile che accada,
possiamo trovare il perno da

120
00:05:38,630 --> 00:05:42,610
scegliendo più elementi e
prendendo il valore mediano.

121
00:05:42,610 --> 00:05:44,650
>> Il mio nome è Mark Grozen-Smith,
e questo è CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Per semplicità, supponiamo che i
le cose sono solo numeri interi, ma

124
00:05:50,930 --> 00:05:51,970
sapere che Quicksert -

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

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

127
00:05:55,200 --> 00:06:02,000
>> Qui abbiamo i numeri interi
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: Davvero?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: non si fermano qui.

130
00:06:04,850 --> 00:06:06,100
>> SPEAKER 1: Davvero?

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