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

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Hoi, ik ben Mark
Grozen-Smith, en dit is Quicksort.

3
00:00:10,390 --> 00:00:13,520
Net als insertion sort en bubble
sorteren, Quicksort is een algoritme voor het

4
00:00:13,520 --> 00:00:15,720
sorteren van een lijst of een reeks van dingen.

5
00:00:15,720 --> 00:00:19,080
Voor de eenvoud, laten we aannemen dat die
dingen zijn gewoon integers, maar

6
00:00:19,080 --> 00:00:22,060
weten dat Quicksort werkt voor
meer dan getallen.

7
00:00:22,060 --> 00:00:24,720
Snelstart is een beetje ingewikkelder
dan inbrengen of bubble, maar het is

8
00:00:24,720 --> 00:00:27,560
ook veel efficiënter
in de meeste gevallen.

9
00:00:27,560 --> 00:00:28,150
Wacht even.

10
00:00:28,150 --> 00:00:30,760
Zei hij net "meest
gevallen ", niet" alle "?

11
00:00:30,760 --> 00:00:31,710
Interessant, nee.

12
00:00:31,710 --> 00:00:33,560
Niet alle gevallen dezelfde.

13
00:00:33,560 --> 00:00:36,650
Maak je geen zorgen over dit detail als u
hebben grote O notatie nog niet gezien, maar

14
00:00:36,650 --> 00:00:39,730
Quicksort is een O (n kwadraat) algoritme
in het slechtste geval, net als

15
00:00:39,730 --> 00:00:41,430
insertie of bubble sort.

16
00:00:41,430 --> 00:00:44,950
Toch treedt meestal veel meer
als een oude analoge m algoritme.

17
00:00:44,950 --> 00:00:45,750
Waarom?

18
00:00:45,750 --> 00:00:46,810
We komen terug om dat later te krijgen.

19
00:00:46,810 --> 00:00:49,610
Maar voor nu, laten we gewoon leren
hoe Quicksort werkt.

20
00:00:49,610 --> 00:00:53,080
>> Dus laten we lopen door Quicksorting deze
array van integers van klein

21
00:00:53,080 --> 00:00:54,260
naar de grootste.

22
00:00:54,260 --> 00:01:00,110
Hier hebben we de getallen 6,
5, 1, 3, 8, 4, 7, 9, en 2.

23
00:01:00,110 --> 00:01:03,480
Ten eerste, we halen het sluitstuk van
deze array - in dit geval twee -

24
00:01:03,480 --> 00:01:06,870
en noemen dat de "spil." Vervolgens hebben we
beginnen te kijken naar twee dingen -

25
00:01:06,870 --> 00:01:10,220
een, de laagste index, die ik zal verwijzen
als altijd rechts van

26
00:01:10,220 --> 00:01:13,970
de muur, en, twee, de meest linkse
element, dat ik de "huidige bel

27
00:01:13,970 --> 00:01:17,260
element. "Wat we gaan doen is
kijk alle andere elementen, andere

28
00:01:17,260 --> 00:01:20,930
dan de spil, en zet alle elementen
kleiner dan de spil aan de

29
00:01:20,930 --> 00:01:24,140
links van de muur en al die
groter dan de spil aan de

30
00:01:24,140 --> 00:01:25,570
rechts van de muur.

31
00:01:25,570 --> 00:01:29,560
En dan, eindelijk, we zullen de spil te laten vallen
recht op die muur te zetten tussen

32
00:01:29,560 --> 00:01:32,970
alle getallen kleiner dan
en alle getallen groter.

33
00:01:32,970 --> 00:01:34,460
>> Dus laten we dat doen.

34
00:01:34,460 --> 00:01:38,540
Pak de 2, zet de muur aan de
begin, en bel de 6 de "huidige

35
00:01:38,540 --> 00:01:41,590
element. "Zo willen we kijken naar
onze huidige element, de 6.

36
00:01:41,590 --> 00:01:44,200
En omdat het groter is dan de
2, laten we het daar op de

37
00:01:44,200 --> 00:01:45,610
rechts van de muur.

38
00:01:45,610 --> 00:01:48,980
Daarna gaan we verder kijken naar de 5 als onze
huidige element en zie dat deze

39
00:01:48,980 --> 00:01:51,840
is wederom groter dan de spil, dus
laten wanneer het op de juiste

40
00:01:51,840 --> 00:01:53,190
zijde van de wand.

41
00:01:53,190 --> 00:01:53,880
We gaan verder.

42
00:01:53,880 --> 00:01:56,750
Onze huidige element is
nu 1, en - oh.

43
00:01:56,750 --> 00:01:58,030
Dit is nu anders.

44
00:01:58,030 --> 00:02:00,890
De huidige element is nu kleiner dan
de spil, dus we willen het te zetten

45
00:02:00,890 --> 00:02:02,570
links van de wand.

46
00:02:02,570 --> 00:02:06,555
Om dit te doen, laten we gewoon schakelen de
huidige element met de laagste index

47
00:02:06,555 --> 00:02:07,970
zitten net aan de rechterkant van de muur.

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

49
00:02:14,050 --> 00:02:17,570
Nu gaan we de muur op een index
dus de 1 is links

50
00:02:17,570 --> 00:02:19,750
zijde van de wand nu.

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

52
00:02:20,310 --> 00:02:23,450
Ik gemengd de elementen op de
rechterkant van de muur, niet ik?

53
00:02:23,450 --> 00:02:23,890
Maak je geen zorgen.

54
00:02:23,890 --> 00:02:24,930
Dat is prima.

55
00:02:24,930 --> 00:02:27,570
Het enige wat we de zorg over voor nu
is dat al deze elementen in de

56
00:02:27,570 --> 00:02:29,570
rechts van de muur zijn groter
dan de spil.

57
00:02:29,570 --> 00:02:31,760
Geen werkelijke volgorde is nog verondersteld.

58
00:02:31,760 --> 00:02:33,200
>> Nu, terug naar het sorteren.

59
00:02:33,200 --> 00:02:35,840
Dus gaan we op zoek naar
de rest van de elementen.

60
00:02:35,840 --> 00:02:39,075
En in dit geval, zien we dat er
geen andere elementen dan de

61
00:02:39,075 --> 00:02:42,100
pivot, dus laten we ze allemaal op
rechts van de muur.

62
00:02:42,100 --> 00:02:45,980
Tot slot komen we bij de huidige element
en zie dat het is de spil.

63
00:02:45,980 --> 00:02:48,830
Nu, dat betekent dat we twee
secties van de array, waarvan de eerste

64
00:02:48,830 --> 00:02:51,820
klein op de spil en aan de linkerkant
van de muur, en de tweede is

65
00:02:51,820 --> 00:02:54,500
groter dan de spil aan de
rechts van de muur.

66
00:02:54,500 --> 00:02:57,040
We willen de pivot element tussen gezet
de twee, en dan zullen we weten

67
00:02:57,040 --> 00:03:01,000
dat de spil is in haar recht
laatste gesorteerde plaats.

68
00:03:01,000 --> 00:03:04,980
Dus schakelen we dat element de
rechts van de muur met de spil,

69
00:03:04,980 --> 00:03:06,410
en we weten dat de spil van
in zijn juiste positie.

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

71
00:03:11,130 --> 00:03:15,650
>> We herhaal dit proces voor de
subarrays links en rechts van het scharnier.

72
00:03:15,650 --> 00:03:18,700
Sinds de laatste subarray is slechts een
element lang, weten we dat er al

73
00:03:18,700 --> 00:03:22,480
gesorteerde want hoe kun je uit
bestellen als je slechts een element bent?

74
00:03:22,480 --> 00:03:28,860
Voor de rechterkant van de subarray, we
zien dat de spil is 5, en de muur

75
00:03:28,860 --> 00:03:32,250
is net links van de 6.

76
00:03:32,250 --> 00:03:34,970
En het huidige element ook
begint als de 6.

77
00:03:34,970 --> 00:03:36,200
Dus 6 groter is dan 5.

78
00:03:36,200 --> 00:03:38,590
We laten wanneer het op de
rechts van de muur.

79
00:03:38,590 --> 00:03:41,060
Nu, het bewegen, 3 minder dan 5.

80
00:03:41,060 --> 00:03:44,160
Dus schakelen we het met het eerste element
net rechts van de muur.

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

82
00:03:47,944 --> 00:03:50,750
Nu, ik bewoog de muur boven een.

83
00:03:50,750 --> 00:03:53,010
Nu, over te gaan tot de 8.

84
00:03:53,010 --> 00:03:56,480
8 groter is dan 5,
en zo laten we het.

85
00:03:56,480 --> 00:03:58,720
De 4 is minder dan 5, dus we wisselen het.

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

87
00:04:02,950 --> 00:04:03,570
En op.

88
00:04:03,570 --> 00:04:04,820
En op.

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

90
00:04:10,190 --> 00:04:13,670
>> Elke keer dat we herhaal het proces op de
linker-en rechterzijde van de array. we

91
00:04:13,670 --> 00:04:17,010
kiezen voor een draaipunt en doe de vergelijkingen
en een andere mate van linker en

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

93
00:04:18,240 --> 00:04:21,500
Deze recursieve aanroep zal doorgaan tot
we het einde toen we hebben bereikt

94
00:04:21,500 --> 00:04:25,290
verdeelden de totale array naar
net subarrays van lengte 1.

95
00:04:25,290 --> 00:04:28,060
Vanaf daar, we kennen de array wordt gesorteerd
omdat elk element heeft, op

96
00:04:28,060 --> 00:04:29,330
een bepaald punt, is een spil.

97
00:04:29,330 --> 00:04:32,720
Met andere woorden, voor elk element, alle
de getallen aan de linkerkant zijn minder

98
00:04:32,720 --> 00:04:36,420
waarden en alle nummers op de
recht hebben hogere waarden.

99
00:04:36,420 --> 00:04:38,980
>> Deze methode werkt goed als de
waarde van de gekozen spil is

100
00:04:38,980 --> 00:04:41,930
ongeveer in het midden
bereik van de lijst waarden.

101
00:04:41,930 --> 00:04:45,630
Dit zou betekenen dat, nadat we verhuizen
elementen rond, er ongeveer evenveel

102
00:04:45,630 --> 00:04:48,390
elementen links van de spil
aangezien er naar rechts.

103
00:04:48,390 --> 00:04:52,380
En de verdeel-en-heers aard van de
Quicksort algoritme wordt vervolgens

104
00:04:52,380 --> 00:04:53,850
volle te profiteren van.

105
00:04:53,850 --> 00:04:57,500
Dit creëert een looptijd van O (n log n,)
de n omdat we moeten doen n minus 1

106
00:04:57,500 --> 00:05:01,640
vergelijkingen op elke generatie en log
n want we moeten de lijst te verdelen

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

108
00:05:03,210 --> 00:05:06,160
In de ergste gevallen
algoritme kan eigenlijk O (n

109
00:05:06,160 --> 00:05:09,850
kwadraat.) Stel voor elke generatie,
de spil gewoon zo gebeurt te zijn de

110
00:05:09,850 --> 00:05:12,520
kleinste of de grootste van de
nummers we sorteren.

111
00:05:12,520 --> 00:05:15,870
Dit zou betekenen het afbreken van de lijst
n keer en het maken n minus 1

112
00:05:15,870 --> 00:05:17,690
vergelijkingen elke keer weer.

113
00:05:17,690 --> 00:05:20,490
Aldus o n kwadraat.

114
00:05:20,490 --> 00:05:22,000
>> Hoe kunnen we de methode?

115
00:05:22,000 --> 00:05:25,100
Een goede manier om de werkwijze te verbeteren is
om te bezuinigen op de kans dat

116
00:05:25,100 --> 00:05:28,150
de runtime is eigenlijk ooit
o van n kwadraat.

117
00:05:28,150 --> 00:05:31,860
Onthoud dit ergste, worst case scenario
kan alleen gebeuren wanneer de

118
00:05:31,860 --> 00:05:35,320
pivot gekozen is altijd de hoogste
of kleinste waarde in de array.

119
00:05:35,320 --> 00:05:38,630
Om dit minder waarschijnlijk gebeuren,
kunnen we de pivot vinden door

120
00:05:38,630 --> 00:05:42,610
kiezen meerdere elementen en
het nemen van de mediane waarde.

121
00:05:42,610 --> 00:05:44,650
>> Mijn naam is Mark Grozen-Smith,
en dit is CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Voor de eenvoud, laten we aannemen dat die
dingen zijn gewoon integers, maar

124
00:05:50,930 --> 00:05:51,970
weten dat Quicksert -

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

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

127
00:05:55,200 --> 00:06:02,000
>> Hier hebben we de gehele getallen
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> LUIDSPREKER 1: Echt waar?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Laat je daar niet stoppen.

130
00:06:04,850 --> 00:06:06,100
>> LUIDSPREKER 1: Echt waar?

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