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

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-Smith: Hi, Unë jam Mark
Grozen-Smith, dhe kjo është Quicksort.

3
00:00:10,390 --> 00:00:13,520
Ashtu si lloj e hyrjes dhe flluskë
lloj, Quicksort është një algoritmi për

4
00:00:13,520 --> 00:00:15,720
sorting një listë ose një grup të gjëra.

5
00:00:15,720 --> 00:00:19,080
Për thjeshtësi, le të supozojmë se ata
gjërat janë vetëm numra të plotë, por

6
00:00:19,080 --> 00:00:22,060
e di se Quicksort punon për
më shumë se vetëm numra.

7
00:00:22,060 --> 00:00:24,720
QuickStart është pak më e komplikuar
se futje ose flluskë, por është e

8
00:00:24,720 --> 00:00:27,560
edhe shumë më të efektshme
në shumicën e rasteve.

9
00:00:27,560 --> 00:00:28,150
Prisni një të dytë.

10
00:00:28,150 --> 00:00:30,760
Deshi të thotë ai "më të
raste, "jo" të gjitha "?

11
00:00:30,760 --> 00:00:31,710
Interesante, nr.

12
00:00:31,710 --> 00:00:33,560
Jo të gjitha rastet janë të njëjta.

13
00:00:33,560 --> 00:00:36,650
Mos u shqetësoni për këtë hollësi nëse ju
nuk e kanë parë o simbol të madh, por

14
00:00:36,650 --> 00:00:39,730
Quicksort është O (n katror) algorithm
në më të keq, ashtu si

15
00:00:39,730 --> 00:00:41,430
futje ose flluskë lloj.

16
00:00:41,430 --> 00:00:44,950
Megjithatë, ai zakonisht vepron shumë më tepër
si një analog m algoritmi të vjetër.

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

18
00:00:45,750 --> 00:00:46,810
Ne do të kthehen në atë më vonë.

19
00:00:46,810 --> 00:00:49,610
Por tani për tani, le të vetëm të mësojnë
se si funksionon Quicksort.

20
00:00:49,610 --> 00:00:53,080
>> Pra, le të ecin nëpër këtë Quicksorting
grup i integers nga më të vogël

21
00:00:53,080 --> 00:00:54,260
të më e madhe.

22
00:00:54,260 --> 00:01:00,110
Këtu kemi integers 6,
5, 1, 3, 8, 4, 7, 9, dhe 2.

23
00:01:00,110 --> 00:01:03,480
Së pari, ne kemi marr elementin final të
kjo array - në këtë rast, dy -

24
00:01:03,480 --> 00:01:06,870
dhe thirrje që të "strumbullar." Tjetra, ne
fillojnë të shikojnë në dy gjëra -

25
00:01:06,870 --> 00:01:10,220
një, indeksi të ulët, të cilën unë do të referohen
si për të qëndruar në të djathtë të

26
00:01:10,220 --> 00:01:13,970
mur, dhe, dy të, i pari nga e majta
element, që unë do të thërrasë "e tanishme

27
00:01:13,970 --> 00:01:17,260
element. "Ajo që ne jemi duke shkuar për të bërë është
shikoni të gjitha elementet e tjera, të tjera

28
00:01:17,260 --> 00:01:20,930
se bosht, dhe të vënë të gjitha elementet
vogël se boshti sa më

29
00:01:20,930 --> 00:01:24,140
majtë të murit dhe të gjithë ata
mëdha se boshti te

30
00:01:24,140 --> 00:01:25,570
drejtën e murit.

31
00:01:25,570 --> 00:01:29,560
Pastaj, më në fund, ne do të heqin të strumbullar
të drejtë në atë mur ta vënë atë në mes të

32
00:01:29,560 --> 00:01:32,970
të gjitha numrat më të vogla se sa ajo
dhe të gjitha numrat më të mëdha.

33
00:01:32,970 --> 00:01:34,460
>> Pra, le ta bëjmë atë.

34
00:01:34,460 --> 00:01:38,540
Marr 2, vënë në mur
duke filluar, dhe thirrjen e 6 e "aktuale

35
00:01:38,540 --> 00:01:41,590
element. "Pra, ne duam të shohim në
Elementi ynë aktual, 6.

36
00:01:41,590 --> 00:01:44,200
Dhe që kjo është më e madhe se
2, ne të lënë aty për të

37
00:01:44,200 --> 00:01:45,610
drejtën e murit.

38
00:01:45,610 --> 00:01:48,980
Pastaj, ne shkojmë për të parë në 5 tonë si
element i tanishëm dhe të shohim se ky

39
00:01:48,980 --> 00:01:51,840
është, perseri, e madhe se boshti, kështu ne
lënë atë aty ku është në të djathtë

40
00:01:51,840 --> 00:01:53,190
anë e murit.

41
00:01:53,190 --> 00:01:53,880
Ne lëvizë.

42
00:01:53,880 --> 00:01:56,750
Element jonë e tanishme është
tani 1, dhe - oh.

43
00:01:56,750 --> 00:01:58,030
Kjo është e ndryshme tani.

44
00:01:58,030 --> 00:02:00,890
Elementi i tanishëm tani është më i vogël se
strumbullar, kështu që ne duam të vënë atë

45
00:02:00,890 --> 00:02:02,570
majtas te murit.

46
00:02:02,570 --> 00:02:06,555
Për ta bërë këtë, le të vetëm kaloni
element i tanishëm me indeksin më të ulët

47
00:02:06,555 --> 00:02:07,970
ulur vetëm në të djathtë të murit.

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

49
00:02:14,050 --> 00:02:17,570
Tani, ne shkojmë muret lart një indeks
ashtu 1 është majtas

50
00:02:17,570 --> 00:02:19,750
anë e murit tani.

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

52
00:02:20,310 --> 00:02:23,450
Unë vetëm të përziera elementet në
anën e djathtë të murit, apo jo?

53
00:02:23,450 --> 00:02:23,890
Mos u shqetësoni.

54
00:02:23,890 --> 00:02:24,930
Kjo është në rregull.

55
00:02:24,930 --> 00:02:27,570
E vetmja gjë ne lidhje me kujdes për tani
është se të gjitha këto elemente të

56
00:02:27,570 --> 00:02:29,570
drejta e murit janë më të mëdha
se boshti.

57
00:02:29,570 --> 00:02:31,760
Nuk ka mënyrë aktuale supozohet ende.

58
00:02:31,760 --> 00:02:33,200
>> Tani, përsëri në klasifikim.

59
00:02:33,200 --> 00:02:35,840
Pra, ne të vazhdojmë në kërkim në
tjetër e elementeve.

60
00:02:35,840 --> 00:02:39,075
Dhe në këtë rast, ne shohim se ka
ka elemente të tjerë më pak se

61
00:02:39,075 --> 00:02:42,100
strumbullar, kështu që ne të lënë ata të gjithë në
anën e djathtë të murit.

62
00:02:42,100 --> 00:02:45,980
Së fundi, ne kemi marrë në elementin e tanishëm
dhe të shohim se ajo është strumbullar.

63
00:02:45,980 --> 00:02:48,830
Tani, kjo do të thotë se ne kemi dy
seksionet e array, qenien e parë

64
00:02:48,830 --> 00:02:51,820
vogël në aks dhe në anën e majtë
të murit, dhe të dytë që

65
00:02:51,820 --> 00:02:54,500
mëdha se boshti te
anën e djathtë të murit.

66
00:02:54,500 --> 00:02:57,040
Ne duam të vënë elementin strumbullar mes
dy, dhe pastaj ne do të dini

67
00:02:57,040 --> 00:03:01,000
se strumbullar është në të drejtën e
vendi përfundimtar renditura.

68
00:03:01,000 --> 00:03:04,980
Pra, ne të kaloni elementin e parë mbi
anën e djathtë të murit me strumbullar,

69
00:03:04,980 --> 00:03:06,410
dhe ne e dimë strumbullar-së
në pozitën e saj të drejtë.

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

71
00:03:11,130 --> 00:03:15,650
>> Ne pastaj të përsëritur këtë proces për
subarrays majtë dhe të djathtë të strumbullar.

72
00:03:15,650 --> 00:03:18,700
Që subarray fundit është vetëm një
element të gjatë, ne e dimë se tashmë

73
00:03:18,700 --> 00:03:22,480
Renditur sepse si mund të jetë jashtë
urdhërojë qoftë se ju jeni vetëm një element?

74
00:03:22,480 --> 00:03:28,860
Për anën e djathtë të subarray, ne
shohim se boshti është 5, dhe muri

75
00:03:28,860 --> 00:03:32,250
ka mbetur vetëm të 6.

76
00:03:32,250 --> 00:03:34,970
Dhe element aktuale gjithashtu
fillon nga sa 6.

77
00:03:34,970 --> 00:03:36,200
6 është kaq e madhe se 5.

78
00:03:36,200 --> 00:03:38,590
Ne e lënë atë aty ku është në
anën e djathtë të murit.

79
00:03:38,590 --> 00:03:41,060
Tani, duke lëvizur on, 3 është më pak se 5.

80
00:03:41,060 --> 00:03:44,160
Kështu ne kaluar me elementin e parë
vetëm e drejtë të murit.

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

82
00:03:47,944 --> 00:03:50,750
Tani, unë u zhvendos murin deri një.

83
00:03:50,750 --> 00:03:53,010
Tani, të lëvizin për në 8.

84
00:03:53,010 --> 00:03:56,480
8 është më i madh se 5,
dhe kështu që ne të lënë atë.

85
00:03:56,480 --> 00:03:58,720
4 është më pak se 5, ne mënyrë të kaluar atë.

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

87
00:04:02,950 --> 00:04:03,570
Dhe në.

88
00:04:03,570 --> 00:04:04,820
Dhe në.

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

90
00:04:10,190 --> 00:04:13,670
>> Çdo herë që përsëris procesin për
anët majtë dhe të djathtë të vektorit. ne

91
00:04:13,670 --> 00:04:17,010
zgjidhni një strumbullar dhe të bëjë krahasime
dhe për të krijuar një nivel tjetër të majtë dhe të

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

93
00:04:18,240 --> 00:04:21,500
Kjo thirrje rekursive do të vazhdojë deri
kemi arritur në fund, kur ne kemi

94
00:04:21,500 --> 00:04:25,290
ndanë array përgjithshëm në
vetëm subarrays e gjatësisë 1.

95
00:04:25,290 --> 00:04:28,060
Nga atje, ne e dimë array të zgjidhet
sepse çdo element ka, në

96
00:04:28,060 --> 00:04:29,330
disa pika, qenë një strumbullar.

97
00:04:29,330 --> 00:04:32,720
Me fjalë të tjera, për çdo element, të gjithë
numrat në të majtë janë më të vogla

98
00:04:32,720 --> 00:04:36,420
vlerat dhe të gjitha numrat në
drejtë kanë vlera më të mëdha.

99
00:04:36,420 --> 00:04:38,980
>> Kjo metodë punon shumë mirë nëse
vlera e boshtit të zgjedhur është

100
00:04:38,980 --> 00:04:41,930
afërsisht në mes
varg i vlerave të listave.

101
00:04:41,930 --> 00:04:45,630
Kjo do të thotë se, pasi ne shkojmë
elemente rreth, atje rreth sa më shumë

102
00:04:45,630 --> 00:04:48,390
elementet në të majtë të strumbullar
si ka në të djathtë.

103
00:04:48,390 --> 00:04:52,380
Dhe natyra ndarje-dhe-Conquer e
Quicksort algorithm është marrë më pas

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

105
00:04:53,850 --> 00:04:57,500
Kjo krijon një Runtime të O (n log n,)
n sepse ne duhet të bëjmë n minus 1

106
00:04:57,500 --> 00:05:01,640
Krahasimet në çdo brez dhe log
n sepse ne kemi për të ndarë të listës

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

108
00:05:03,210 --> 00:05:06,160
Megjithatë, në rastet më të këqija, kjo
algorithm fakt mund të jetë O (n

109
00:05:06,160 --> 00:05:09,850
në katror.) Supozoni se në çdo brez,
strumbullar ndodh vetëm në mënyrë që të jetë

110
00:05:09,850 --> 00:05:12,520
më të vogël apo më e madhe e
Numrat ne jemi klasifikim.

111
00:05:12,520 --> 00:05:15,870
Kjo do të thotë thyer poshtë në listë
n herë dhe duke e bërë n minus 1

112
00:05:15,870 --> 00:05:17,690
Krahasimet çdo herë të vetme.

113
00:05:17,690 --> 00:05:20,490
Kështu, o të n katror.

114
00:05:20,490 --> 00:05:22,000
>> Si mund të përmirësohet metoda?

115
00:05:22,000 --> 00:05:25,100
Një mënyrë e mirë për të përmirësuar metodën është
për të shkurtuar në probabilitetin që

116
00:05:25,100 --> 00:05:28,150
runtime është kurrë në të vërtetë
o i N katror.

117
00:05:28,150 --> 00:05:31,860
Mos harroni këtë më të keq, skenarin më të keq
mund të ndodhë vetëm kur

118
00:05:31,860 --> 00:05:35,320
strumbullar zgjedhur është gjithmonë më e larta
ose vlera më e ulët në rrjet.

119
00:05:35,320 --> 00:05:38,630
Për të siguruar këtë është më pak gjasa të ndodhë,
ne mund të gjeni strumbullar nga

120
00:05:38,630 --> 00:05:42,610
duke zgjedhur elemente të shumta dhe
duke marrë vlerën mesatare.

121
00:05:42,610 --> 00:05:44,650
>> Emri im është Mark Grozen-Smith,
dhe kjo është CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Për thjeshtësi, le të supozojmë se ata
gjërat janë vetëm numra të plotë, por

124
00:05:50,930 --> 00:05:51,970
e di se Quicksert -

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

126
00:05:53,160 --> 00:05:55,200
Më vjen keq.

127
00:05:55,200 --> 00:06:02,000
>> Këtu ne kemi numra të plotë
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> Gjuha 1: Really?

129
00:06:03,200 --> 00:06:04,850
>> Gjuha 2: Mos të ndalemi këtu.

130
00:06:04,850 --> 00:06:06,100
>> Gjuha 1: Really?

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