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

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

3
00:00:10,390 --> 00:00:13,520
Stejně jako vložení druhu a bubliny
třídění, Quicksort je algoritmus pro

4
00:00:13,520 --> 00:00:15,720
třídění seznamu nebo pole věcí.

5
00:00:15,720 --> 00:00:19,080
Pro jednoduchost předpokládejme, že ti,
věci jsou jen celá čísla, ale

6
00:00:19,080 --> 00:00:22,060
vím, že Quicksort pracuje pro
více než jen čísla.

7
00:00:22,060 --> 00:00:24,720
Rychlý start je trochu složitější
než vložení nebo bublina, ale je to

8
00:00:24,720 --> 00:00:27,560
také mnohem účinnější
ve většině případů.

9
00:00:27,560 --> 00:00:28,150
Počkej chvíli.

10
00:00:28,150 --> 00:00:30,760
Řekl jen říct "nejvíce
případy, "ne" všechno "?

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

12
00:00:31,710 --> 00:00:33,560
Ne všechny případy jsou stejné.

13
00:00:33,560 --> 00:00:36,650
Nebojte se o tomto detailu, pokud vám
Neviděl velký O notace ještě, ale

14
00:00:36,650 --> 00:00:39,730
Quicksort je O (n čtvercový) algoritmus
v nejhorším případě, stejně jako

15
00:00:39,730 --> 00:00:41,430
vložení nebo bublina třídění.

16
00:00:41,430 --> 00:00:44,950
Nicméně, to obvykle působí mnohem více
jako starý analogový m algoritmu.

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

18
00:00:45,750 --> 00:00:46,810
Dostaneme se k tomu vrátit později.

19
00:00:46,810 --> 00:00:49,610
Ale teď, pojďme se jen naučit
jak Quicksort funguje.

20
00:00:49,610 --> 00:00:53,080
>> Takže pojďme projít Quicksorting to
pole celých čísel od nejmenšího

21
00:00:53,080 --> 00:00:54,260
po největší.

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

23
00:01:00,110 --> 00:01:03,480
Za prvé, jsme se vybrat konečný prvek
Toto pole - v tomto případě dva -

24
00:01:03,480 --> 00:01:06,870
a volat, že je "pivot". Dále jsme
začít se dívat na dvě věci -

25
00:01:06,870 --> 00:01:10,220
jeden, nejnižší index, který budu odkazovat
jako zůstat na pravé straně

26
00:01:10,220 --> 00:01:13,970
stěny, a, dva, vlevo
prvek, který zavolám "proud

27
00:01:13,970 --> 00:01:17,260
element. "Co budeme dělat, je
podívejte se všechny ostatní prvky, další

28
00:01:17,260 --> 00:01:20,930
než pivot, a dát všechny prvky
menší než pivot na

29
00:01:20,930 --> 00:01:24,140
vlevo ze zdi a všechny ty,
větší než pivot na

30
00:01:24,140 --> 00:01:25,570
pravé stěny.

31
00:01:25,570 --> 00:01:29,560
Pak se konečně budeme klesat pivot
přímo na té zdi, aby ji mezi

32
00:01:29,560 --> 00:01:32,970
všechna čísla menší, než
a všechna čísla větší.

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

34
00:01:34,460 --> 00:01:38,540
Seberte 2, umístit na stěnu v
začíná, a zavolejte 6 "proud

35
00:01:38,540 --> 00:01:41,590
element. "Takže chceme podívat na
Naše aktuální prvek, 6.

36
00:01:41,590 --> 00:01:44,200
A protože je to větší než
2, jsme ji tam nechat, aby

37
00:01:44,200 --> 00:01:45,610
pravé stěny.

38
00:01:45,610 --> 00:01:48,980
Pak se přesuňte na se podívat na 5, protože naše
aktuální prvek a uvidíte, že to

39
00:01:48,980 --> 00:01:51,840
je opět větší, než je čep, a tak jsme
nechte ji tam, kde je na pravé straně

40
00:01:51,840 --> 00:01:53,190
boční stěny.

41
00:01:53,190 --> 00:01:53,880
Jsme dál.

42
00:01:53,880 --> 00:01:56,750
Naše aktuální prvek je
nyní 1, a - oh.

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

44
00:01:58,030 --> 00:02:00,890
Aktuální prvek je nyní menší než
pivot, tak chceme, aby to

45
00:02:00,890 --> 00:02:02,570
na levé straně stěny.

46
00:02:02,570 --> 00:02:06,555
Chcete-li to provést, pojďme stačí přepnout
aktuální prvek s nejnižším indexem

47
00:02:06,555 --> 00:02:07,970
sedí jen na pravé straně zdi.

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

49
00:02:14,050 --> 00:02:17,570
Nyní se přesuneme na zeď do jednoho indexu
tak 1 je na levé straně

50
00:02:17,570 --> 00:02:19,750
boční stěny nyní.

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

52
00:02:20,310 --> 00:02:23,450
Jen jsem popletl prvky na
na pravé straně zdi, nebo ne?

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

54
00:02:23,890 --> 00:02:24,930
To je v pořádku.

55
00:02:24,930 --> 00:02:27,570
Jediné, co nás zajímá teď
je, že všechny tyto prvky do

56
00:02:27,570 --> 00:02:29,570
pravé stěny jsou větší
než čepu.

57
00:02:29,570 --> 00:02:31,760
Žádné skutečné pořadí se předpokládá ještě.

58
00:02:31,760 --> 00:02:33,200
>> Nyní zpět k třídění.

59
00:02:33,200 --> 00:02:35,840
Takže budeme pokračovat v pohledu na
Zbytek prvků.

60
00:02:35,840 --> 00:02:39,075
A v tomto případě vidíme, že existují
žádné další prvky, méně než

61
00:02:39,075 --> 00:02:42,100
pivot, takže jsme se nechat všechno na
na pravé straně zdi.

62
00:02:42,100 --> 00:02:45,980
Nakonec jsme se dostat do aktuálního prvku
a uvidíte, že to je pivot.

63
00:02:45,980 --> 00:02:48,830
Nyní, to znamená, že máme dvě
části pole, první bytí

64
00:02:48,830 --> 00:02:51,820
malý na čepu a na levé straně
zdi, a na druhé bytosti

65
00:02:51,820 --> 00:02:54,500
větší než pivot na
na pravé straně zdi.

66
00:02:54,500 --> 00:02:57,040
Chceme, aby otočný prvek mezi
dva, a pak budeme vědět,

67
00:02:57,040 --> 00:03:01,000
, že čep je v jeho pravé
konečné tříděné místo.

68
00:03:01,000 --> 00:03:04,980
Tak jsme se objeví první prvek na
na pravé straně zdi s čepem,

69
00:03:04,980 --> 00:03:06,410
a víme, že čep je
ve své správné poloze.

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

71
00:03:11,130 --> 00:03:15,650
>> Tento postup jsme pak opakujte pro
subarrays vlevo a vpravo od čepu.

72
00:03:15,650 --> 00:03:18,700
Od posledního subarray je pouze jeden
prvek dlouho, víme, že je již

73
00:03:18,700 --> 00:03:22,480
tříděné, protože jak můžete být z
objednat, pokud jste jen jeden prvek?

74
00:03:22,480 --> 00:03:28,860
Na pravé straně podsoustavu jsme
vidět, že čep je 5, a The Wall

75
00:03:28,860 --> 00:03:32,250
je právě odešel z 6..

76
00:03:32,250 --> 00:03:34,970
A aktuální prvek i
začíná jako 6..

77
00:03:34,970 --> 00:03:36,200
Takže 6 je větší než 5 mm.

78
00:03:36,200 --> 00:03:38,590
Necháme ho tam, kde je na
na pravé straně zdi.

79
00:03:38,590 --> 00:03:41,060
Nyní, pohybující se na, 3 je méně než 5.

80
00:03:41,060 --> 00:03:44,160
Tak jsme ji přepínat s prvním prvkem
právě stěny.

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

82
00:03:47,944 --> 00:03:50,750
Teď jsem se přestěhoval na zeď do jednoho.

83
00:03:50,750 --> 00:03:53,010
Nyní přejdeme k 8..

84
00:03:53,010 --> 00:03:56,480
8 je větší než 5,
a tak jsme ji opustit.

85
00:03:56,480 --> 00:03:58,720
4 je menší než 5, a tak jsme ji přepínat.

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
>> Pokaždé, když jsme se zopakovat postup na
levé a pravé strany pole. my

91
00:04:13,670 --> 00:04:17,010
vybrat čep a proveďte srovnání
a vytvořit další úroveň levého a

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

93
00:04:18,240 --> 00:04:21,500
Tato rekurzivní volání bude pokračovat až do
dojdeme na konec, když jsme

94
00:04:21,500 --> 00:04:25,290
rozdělil celkové pole do
jen subarrays o délce 1.

95
00:04:25,290 --> 00:04:28,060
Odtamtud, víme, že pole je uvedena
proto, že každý prvek má, při

96
00:04:28,060 --> 00:04:29,330
nějaký bod, byl pivot.

97
00:04:29,330 --> 00:04:32,720
Jinými slovy, pro každý prvek, vše
čísla na levé straně jsou menší

98
00:04:32,720 --> 00:04:36,420
hodnoty a všechna čísla do
právo mít větší hodnotu.

99
00:04:36,420 --> 00:04:38,980
>> Tato metoda funguje velmi dobře, pokud
hodnota zvolené čepu je

100
00:04:38,980 --> 00:04:41,930
přibližně ve středu
Rozsah hodnot seznamu.

101
00:04:41,930 --> 00:04:45,630
To by znamenalo, že poté, co jsme se přesunout
prvky kolem, tam asi tolik

102
00:04:45,630 --> 00:04:48,390
prvky na levé straně čepu
jak tam jsou vpravo.

103
00:04:48,390 --> 00:04:52,380
A rozděl a panuj povaha
Quicksort Algoritmus je pak vzat

104
00:04:52,380 --> 00:04:53,850
plně využívat.

105
00:04:53,850 --> 00:04:57,500
Tím se vytvoří runtime O (n log n,)
n, protože musíme udělat, n minus 1

106
00:04:57,500 --> 00:05:01,640
srovnání na každou generaci a log
n proto, že musíme rozdělit seznam

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

108
00:05:03,210 --> 00:05:06,160
Nicméně, v nejhorším případě, to
Algoritmus může být ve skutečnosti O (n

109
00:05:06,160 --> 00:05:09,850
druhou.) Předpokládejme, že v každé generaci,
pivot jen tak se stane, že je

110
00:05:09,850 --> 00:05:12,520
nejmenší nebo největší
čísla budeme třídění.

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

112
00:05:15,870 --> 00:05:17,690
Srovnání pokaždé.

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

114
00:05:20,490 --> 00:05:22,000
>> Jak můžeme zlepšit způsob?

115
00:05:22,000 --> 00:05:25,100
Jeden dobrý způsob, jak zlepšit způsob je
snížit na pravděpodobnost, že

116
00:05:25,100 --> 00:05:28,150
runtime je někdy skutečně
o n na druhou.

117
00:05:28,150 --> 00:05:31,860
Nezapomeňte tento nejhorší, nejhorší scénář
může dojít pouze, pokud

118
00:05:31,860 --> 00:05:35,320
pivot zvolena vždy nejvyšší
nebo nejnižší hodnoty v poli.

119
00:05:35,320 --> 00:05:38,630
Aby se zajistilo, to je méně pravděpodobné, že se tak stalo,
najdeme čep podle

120
00:05:38,630 --> 00:05:42,610
výběr několika prvků a
přičemž medián.

121
00:05:42,610 --> 00:05:44,650
>> Mé jméno 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
>> Pro jednoduchost předpokládejme, že ti,
věci jsou jen celá čísla, ale

124
00:05:50,930 --> 00:05:51,970
vědět, že Quicksert -

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

126
00:05:53,160 --> 00:05:55,200
Promiňte.

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

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

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Nepřestávejte zde.

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

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