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

2
00:00:07,270 --> 00:00:10,390
>> MARK Grozen-SMITH: Ahoj, ja som Mark
Grozen-Smith, a to je Quicksort.

3
00:00:10,390 --> 00:00:13,520
Rovnako ako vloženie druhu a bubliny
triedenie, Quicksort je algoritmus pre

4
00:00:13,520 --> 00:00:15,720
triedenie zoznamu alebo poľa vecí.

5
00:00:15,720 --> 00:00:19,080
Pre jednoduchosť predpokladajme, že tí,
veci sú len celé čísla, ale

6
00:00:19,080 --> 00:00:22,060
viem, že Quicksort pracuje pre
viac než len čísla.

7
00:00:22,060 --> 00:00:24,720
Rýchly štart je trochu zložitejšie
ako vloženie alebo bublina, ale je to

8
00:00:24,720 --> 00:00:27,560
tiež oveľa účinnejšie
vo väčšine prípadov.

9
00:00:27,560 --> 00:00:28,150
Počkaj chvíľu.

10
00:00:28,150 --> 00:00:30,760
Povedal len povedať "najviac
prípady, "nie" všetko "?

11
00:00:30,760 --> 00:00:31,710
Zaujímavé je, že nie.

12
00:00:31,710 --> 00:00:33,560
Nie všetky prípady sú rovnaké.

13
00:00:33,560 --> 00:00:36,650
Nebojte sa o tomto detaile, ak vám
Nevidel veľký O notácie ešte, ale

14
00:00:36,650 --> 00:00:39,730
Quicksort je O (n štvorcový) algoritmus
v najhoršom prípade, rovnako ako

15
00:00:39,730 --> 00:00:41,430
vloženie alebo bublina triedenie.

16
00:00:41,430 --> 00:00:44,950
Avšak, to zvyčajne pôsobí oveľa viac
ako starý analógový m algoritmu.

17
00:00:44,950 --> 00:00:45,750
Prečo?

18
00:00:45,750 --> 00:00:46,810
Dostaneme sa k tomu vrátiť neskôr.

19
00:00:46,810 --> 00:00:49,610
Ale teraz, poďme sa len naučiť
ako Quicksort funguje.

20
00:00:49,610 --> 00:00:53,080
>> Takže poďme prejsť Quicksorting to
pole celých čísel od najmenšieho

21
00:00:53,080 --> 00:00:54,260
po najväčšie.

22
00:00:54,260 --> 00:01:00,110
Tu máme celé čísla 6,
5, 1, 3, 8, 4, 7, 9, a 2..

23
00:01:00,110 --> 00:01:03,480
Po prvé, sme sa vybrať konečný prvok
Toto pole - v tomto prípade dva -

24
00:01:03,480 --> 00:01:06,870
a volať, že je "pivot". Ďalej sme
začať sa pozerať na dve veci -

25
00:01:06,870 --> 00:01:10,220
jeden, najnižší index, ktorý budem odkazovať
ako zostať na pravej strane

26
00:01:10,220 --> 00:01:13,970
steny, a, dva, vľavo
prvok, ktorý zavolám "prúd

27
00:01:13,970 --> 00:01:17,260
element. "Čo budeme robiť, je
pozrite sa všetky ostatné prvky, ďalšie

28
00:01:17,260 --> 00:01:20,930
ako pivot, a dať všetky prvky
menšie ako pivot na

29
00:01:20,930 --> 00:01:24,140
vľavo zo steny a všetky tie,
väčšie ako pivot na

30
00:01:24,140 --> 00:01:25,570
priamo na stenu.

31
00:01:25,570 --> 00:01:29,560
Potom sa konečne budeme klesať pivot
priamo na tej stene, aby ju medzi

32
00:01:29,560 --> 00:01:32,970
všetky čísla menšie, než
a všetky čísla väčšie.

33
00:01:32,970 --> 00:01:34,460
>> Tak poďme na to.

34
00:01:34,460 --> 00:01:38,540
Zoberte 2, dať na stenu na
začína, a zavolajte 6 "prúd

35
00:01:38,540 --> 00:01:41,590
element. "Takže chceme pozrieť na
Naše aktuálne prvok, 6.

36
00:01:41,590 --> 00:01:44,200
A pretože je to väčšie ako
2, sme ju tam nechať, aby

37
00:01:44,200 --> 00:01:45,610
pravej steny.

38
00:01:45,610 --> 00:01:48,980
Potom sa presuňte na sa pozrieť na 5, pretože naše
aktuálny prvok a uvidíte, že to

39
00:01:48,980 --> 00:01:51,840
je opäť väčšia, ako je čap, a tak sme
nechajte ju tam, kde je na pravej strane

40
00:01:51,840 --> 00:01:53,190
bočné steny.

41
00:01:53,190 --> 00:01:53,880
Sme ďalej.

42
00:01:53,880 --> 00:01:56,750
Naše aktuálne prvok je
teraz 1, a - oh.

43
00:01:56,750 --> 00:01:58,030
To je iná.

44
00:01:58,030 --> 00:02:00,890
Aktuálny prvok je teraz menšia než
pivot, tak chceme, aby to

45
00:02:00,890 --> 00:02:02,570
na ľavej strane steny.

46
00:02:02,570 --> 00:02:06,555
Ak to chcete vykonať, poďme stačí prepnúť
aktuálny prvok s najnižším indexom

47
00:02:06,555 --> 00:02:07,970
sedí len na pravej strane múru.

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

49
00:02:14,050 --> 00:02:17,570
Teraz sa presunieme na stenu jedného indexu
tak 1 je na ľavej strane

50
00:02:17,570 --> 00:02:19,750
bočné steny súčasnosti.

51
00:02:19,750 --> 00:02:20,310
>> Počkajte.

52
00:02:20,310 --> 00:02:23,450
Len som poplietol prvky na
na pravej strane múru, alebo nie?

53
00:02:23,450 --> 00:02:23,890
Nebojte sa.

54
00:02:23,890 --> 00:02:24,930
To je v poriadku.

55
00:02:24,930 --> 00:02:27,570
Jediné, čo nás zaujíma teraz
je, že všetky tieto prvky do

56
00:02:27,570 --> 00:02:29,570
pravej steny sú väčšie
než čapu.

57
00:02:29,570 --> 00:02:31,760
Žiadne skutočné poradí sa predpokladá ešte.

58
00:02:31,760 --> 00:02:33,200
>> Teraz späť k triedenia.

59
00:02:33,200 --> 00:02:35,840
Takže budeme pokračovať v pohľade na
Zvyšok prvkov.

60
00:02:35,840 --> 00:02:39,075
A v tomto prípade vidíme, že existujú
žiadne ďalšie prvky, menej ako

61
00:02:39,075 --> 00:02:42,100
pivot, takže sme sa nechať všetko na
na pravej strane múru.

62
00:02:42,100 --> 00:02:45,980
Nakoniec sme sa dostať do aktuálneho prvku
a uvidíte, že to je pivot.

63
00:02:45,980 --> 00:02:48,830
Teraz, to znamená, že máme dve
časti poľa, prvý bytia

64
00:02:48,830 --> 00:02:51,820
malý na čapu a na ľavej strane
múru, a na druhej bytosti

65
00:02:51,820 --> 00:02:54,500
väčšie ako pivot na
na pravej strane múru.

66
00:02:54,500 --> 00:02:57,040
Chceme, aby otočný prvok medzi
dva, a potom budeme vedieť,

67
00:02:57,040 --> 00:03:01,000
, Že čap je v jeho pravej
konečné triedené miesto.

68
00:03:01,000 --> 00:03:04,980
Tak sme sa objavia prvé prvok na
na pravej strane múru s čapom,

69
00:03:04,980 --> 00:03:06,410
a vieme, že čap je
vo svojej správnej polohe.

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

71
00:03:11,130 --> 00:03:15,650
>> Tento postup sme potom opakujte pre
subarrays vľavo a vpravo od čapu.

72
00:03:15,650 --> 00:03:18,700
Od posledného subarray je len jeden
prvok dlho, vieme, že to už

73
00:03:18,700 --> 00:03:22,480
triedené, pretože ako môžete byť z
objednať, ak ste len jeden prvok?

74
00:03:22,480 --> 00:03:28,860
Na pravej strane podsieť sme
vidieť, že čap je 5, a The Wall

75
00:03:28,860 --> 00:03:32,250
je len vľavo od 6.

76
00:03:32,250 --> 00:03:34,970
A aktuálne prvok aj
začína ako 6..

77
00:03:34,970 --> 00:03:36,200
Takže 6 je väčšia ako 5 mm.

78
00:03:36,200 --> 00:03:38,590
Necháme ho tam, kde je na
na pravej strane múru.

79
00:03:38,590 --> 00:03:41,060
Teraz, pohybujúce sa na, 3 je menej ako 5.

80
00:03:41,060 --> 00:03:44,160
Tak sme ju prepínať s prvým prvkom
práve steny.

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

82
00:03:47,944 --> 00:03:50,750
Teraz som sa presťahoval na stenu do jedného.

83
00:03:50,750 --> 00:03:53,010
Teraz prejdeme k 8..

84
00:03:53,010 --> 00:03:56,480
8 je väčšia ako 5,
a tak sme ju opustiť.

85
00:03:56,480 --> 00:03:58,720
4 je menšia než 5, a tak sme ju prepínať.

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

87
00:04:02,950 --> 00:04:03,570
A na.

88
00:04:03,570 --> 00:04:04,820
A na.

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

90
00:04:10,190 --> 00:04:13,670
>> Zakaždým, keď sme sa zopakovať postup na
ľavej a pravej strany poľa. my

91
00:04:13,670 --> 00:04:17,010
vybrať čap a vykonajte porovnanie
a vytvoriť ďalšiu úroveň ľavého a

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

93
00:04:18,240 --> 00:04:21,500
Táto rekurzívne volanie bude pokračovať až do
dôjdeme na koniec, keď sme

94
00:04:21,500 --> 00:04:25,290
rozdelil celkovej poľa do
len subarrays o dĺžke 1.

95
00:04:25,290 --> 00:04:28,060
Odtiaľ vieme, že pole je radený
preto, že každý prvok má, pri

96
00:04:28,060 --> 00:04:29,330
nejaký bod, bol pivot.

97
00:04:29,330 --> 00:04:32,720
Inými slovami, pre každý prvok, všetko
čísla na ľavej strane sú menšie

98
00:04:32,720 --> 00:04:36,420
hodnoty a všetky čísla do
právo mať väčšiu hodnotu.

99
00:04:36,420 --> 00:04:38,980
>> Táto metóda funguje veľmi dobre, ak
hodnota zvolenej čapu je

100
00:04:38,980 --> 00:04:41,930
približne v strede
Rozsah hodnôt zoznamu.

101
00:04:41,930 --> 00:04:45,630
To by znamenalo, že po tom, čo sme sa presunúť
prvky okolo, tam asi toľko

102
00:04:45,630 --> 00:04:48,390
prvky na ľavej strane čapu
ako tam sú vpravo.

103
00:04:48,390 --> 00:04:52,380
A rozdeľ a panuj povaha
Quicksort algoritmus sa potom vyberie

104
00:04:52,380 --> 00:04:53,850
plná výhoda.

105
00:04:53,850 --> 00:04:57,500
Tým sa vytvorí runtime O (n log n)
n, pretože musíme urobiť, n mínus 1

106
00:04:57,500 --> 00:05:01,640
porovnanie na každú generáciu a log
n preto, že musíme rozdeliť zoznam

107
00:05:01,640 --> 00:05:03,210
log n krát.

108
00:05:03,210 --> 00:05:06,160
Avšak, v najhoršom prípade, to
Algoritmus sa môže v skutočnosti O (n

109
00:05:06,160 --> 00:05:09,850
druhú.) Predpokladajme, že v každej generácii,
pivot len ​​tak sa stane, že je

110
00:05:09,850 --> 00:05:12,520
najmenší alebo najväčší
čísla budeme triedenie.

111
00:05:12,520 --> 00:05:15,870
To by znamenalo, poškodí zoznam
n krát a výroba n mínus 1

112
00:05:15,870 --> 00:05:17,690
Porovnanie zakaždým.

113
00:05:17,690 --> 00:05:20,490
Tak, o n na druhú.

114
00:05:20,490 --> 00:05:22,000
>> Ako môžeme zlepšiť spôsob?

115
00:05:22,000 --> 00:05:25,100
Jeden dobrý spôsob, ako zlepšiť spôsob je
znížiť na pravdepodobnosť, že

116
00:05:25,100 --> 00:05:28,150
runtime je niekedy skutočne
o n na druhú.

117
00:05:28,150 --> 00:05:31,860
Nezabudnite tento najhorší, najhorší scenár
môže dôjsť len, ak

118
00:05:31,860 --> 00:05:35,320
pivot zvolená vždy najvyššiu
alebo najnižšie hodnoty v poli.

119
00:05:35,320 --> 00:05:38,630
Aby sa zabezpečilo, to je menej pravdepodobné, že sa tak stalo,
nájdeme čap podľa

120
00:05:38,630 --> 00:05:42,610
výber viac prvkov a
pričom medián.

121
00:05:42,610 --> 00:05:44,650
>> Moje meno je Mark Grozen-Smith,
a to je CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Pre jednoduchosť predpokladajme, že tí,
veci sú len celé čísla, ale

124
00:05:50,930 --> 00:05:51,970
vedieť, že Quicksert -

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

126
00:05:53,160 --> 00:05:55,200
Prepáčte.

127
00:05:55,200 --> 00:06:02,000
>> Tu máme celé čísla
6, 5, 1, 3, 8, 4, 9.

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

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Neprestávajte tu.

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

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