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

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-Smith: Szia, én vagyok Mark
Grozen-Smith, és ez gyorsrendezés.

3
00:00:10,390 --> 00:00:13,520
Csakúgy, mint a beillesztés sort és a buborék
sort, a gyors-egy algoritmus

4
00:00:13,520 --> 00:00:15,720
rendezés a lista, vagy egy sor dolgot.

5
00:00:15,720 --> 00:00:19,080
Az egyszerűség kedvéért tegyük fel, hogy ezeket a
a dolgok csak egész számok, de

6
00:00:19,080 --> 00:00:22,060
tudják, hogy a gyors dolgozik
több, mint csak számok.

7
00:00:22,060 --> 00:00:24,720
Ez a menüpont egy kicsit bonyolultabb
mint a beillesztés vagy buborék, de

8
00:00:24,720 --> 00:00:27,560
is sokkal hatékonyabb
a legtöbb esetben.

9
00:00:27,560 --> 00:00:28,150
Várj egy percet.

10
00:00:28,150 --> 00:00:30,760
Csak nem azt, hogy "a legtöbb
esetben, a "nem" minden "?

11
00:00:30,760 --> 00:00:31,710
Érdekes módon, nem.

12
00:00:31,710 --> 00:00:33,560
Nem minden esetben azonosak.

13
00:00:33,560 --> 00:00:36,650
Ne aggódj ezt a részletet, ha
Nem láttam a nagy O jelölés még, de

14
00:00:36,650 --> 00:00:39,730
Gyors-O (n négyzetes) algoritmus
a legrosszabb esetben, mint

15
00:00:39,730 --> 00:00:41,430
beillesztés vagy bubble sort.

16
00:00:41,430 --> 00:00:44,950
Azonban ez általában sokkal jár
mint egy régi analóg m algoritmus.

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

18
00:00:45,750 --> 00:00:46,810
Majd menj vissza később.

19
00:00:46,810 --> 00:00:49,610
De most, most csak tanulni
hogyan gyorsrendezés elvét.

20
00:00:49,610 --> 00:00:53,080
>> Szóval séta Quicksorting ezt
tömb egész szám legkisebb

21
00:00:53,080 --> 00:00:54,260
a legnagyobb.

22
00:00:54,260 --> 00:01:00,110
Itt van az egész 6
5, 1, 3, 8, 4, 7, 9 és 2.

23
00:01:00,110 --> 00:01:03,480
Először is, vedd az utolsó eleme
ezt a tömböt - ebben az esetben a két -

24
00:01:03,480 --> 00:01:06,870
és hívja, hogy a "pivot". Következő,
elkezdi nézni két dolgot -

25
00:01:06,870 --> 00:01:10,220
egy, a legkisebb index, amit majd hivatkozni
hogy tartózkodik a jobbra

26
00:01:10,220 --> 00:01:13,970
a fal, és a két, a bal szélső
elem, amely hívom a "jelenlegi

27
00:01:13,970 --> 00:01:17,260
elem. "mit fogunk csinálni a
meg az összes többi elem, egyéb

28
00:01:17,260 --> 00:01:20,930
, mint a pivot, és tegye az összes elemet
kisebb, mint az, hogy az elforduló

29
00:01:20,930 --> 00:01:24,140
balra a fal és minden
nagyobb, mint a pivot a

30
00:01:24,140 --> 00:01:25,570
jobbra a falon.

31
00:01:25,570 --> 00:01:29,560
Aztán végül dobjuk a pivot
közvetlenül a falra, hogy tedd között

32
00:01:29,560 --> 00:01:32,970
összes szám kisebb, mint
és az összes nagyobb számok.

33
00:01:32,970 --> 00:01:34,460
>> Így csináljuk.

34
00:01:34,460 --> 00:01:38,540
Vedd fel a 2., tedd a falra a
elején, és hívja a 6. a "jelenlegi

35
00:01:38,540 --> 00:01:41,590
elem. "Ezért szeretnénk nézni
a jelenlegi elem, a 6..

36
00:01:41,590 --> 00:01:44,200
És mivel ez nagyobb, mint a
2, hagyjuk ott a

37
00:01:44,200 --> 00:01:45,610
jobbra a falon.

38
00:01:45,610 --> 00:01:48,980
Aztán megyünk tovább nézni az 5, mint a mi
aktuális elem, és látom, hogy ez a

39
00:01:48,980 --> 00:01:51,840
van, ismét, nagyobb, mint a pivot, ezért
hagyja, ahol a jobb oldalon

40
00:01:51,840 --> 00:01:53,190
oldalán a fal.

41
00:01:53,190 --> 00:01:53,880
Tovább kell lépnünk.

42
00:01:53,880 --> 00:01:56,750
A jelenlegi elem
Most 1 és - ó.

43
00:01:56,750 --> 00:01:58,030
Ez most más.

44
00:01:58,030 --> 00:02:00,890
Az aktuális elem már kisebb, mint a
A pivot, ezért szeretnénk, hogy azt

45
00:02:00,890 --> 00:02:02,570
a bal oldalon a fal.

46
00:02:02,570 --> 00:02:06,555
Ehhez nézzük csak be kell kapcsolnia a
aktuális elem a legalacsonyabb index

47
00:02:06,555 --> 00:02:07,970
ül csak jobbra a falon.

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

49
00:02:14,050 --> 00:02:17,570
Most megyünk a falnak fel egy index
így az 1 a bal oldalon

50
00:02:17,570 --> 00:02:19,750
oldalán a fal most.

51
00:02:19,750 --> 00:02:20,310
>> Várjon.

52
00:02:20,310 --> 00:02:23,450
Én csak összekeverte az elemeket a
jobb oldalon a fal, nem igaz?

53
00:02:23,450 --> 00:02:23,890
Ne aggódj.

54
00:02:23,890 --> 00:02:24,930
Ez rendben van.

55
00:02:24,930 --> 00:02:27,570
Az egyetlen dolog, amit érdekel most
az, hogy ezeket az elemeket a

56
00:02:27,570 --> 00:02:29,570
a fal jobb nagyobbak
mint a pivot.

57
00:02:29,570 --> 00:02:31,760
Nem aktuális rendelés feltételezzük még.

58
00:02:31,760 --> 00:02:33,200
>> Most vissza a válogatás.

59
00:02:33,200 --> 00:02:35,840
Tehát tovább néztem
a többi elem.

60
00:02:35,840 --> 00:02:39,075
És ebben az esetben, azt látjuk, hogy vannak
más elemeket nem kevesebb, mint a

61
00:02:39,075 --> 00:02:42,100
pivot, így hagyjuk őket a
a jobb oldalán a fal.

62
00:02:42,100 --> 00:02:45,980
Végül eljutunk az aktuális elem
és látom, hogy ez a pivot.

63
00:02:45,980 --> 00:02:48,830
Nos, ez azt jelenti, hogy a két
szakaszok a tömb, az első lény

64
00:02:48,830 --> 00:02:51,820
kicsi a pivot és a bal oldali
a fal, és a második lény

65
00:02:51,820 --> 00:02:54,500
nagyobb, mint a pivot a
jobb oldalán a fal.

66
00:02:54,500 --> 00:02:57,040
Azt szeretnénk, hogy a pivot elem között
A két, és akkor tudjuk, hogy

67
00:02:57,040 --> 00:03:01,000
hogy a pivot annak megfelelő
végső rendezett helyen.

68
00:03:01,000 --> 00:03:04,980
Így kapcsolja az első elem a
jobb oldalán a fal a pivot,

69
00:03:04,980 --> 00:03:06,410
és tudjuk, hogy a pivot a
annak megfelelő pozícióba.

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

71
00:03:11,130 --> 00:03:15,650
>> Ezután ismételje meg ezt a folyamatot a
subarrays bal és jobb a pivot.

72
00:03:15,650 --> 00:03:18,700
Mivel az utolsó csak egy subarray
elem hosszú, tudjuk, hogy ez már

73
00:03:18,700 --> 00:03:22,480
rendezett, mert hogy lehet ki
rendelni, ha csak az egyik eleme?

74
00:03:22,480 --> 00:03:28,860
A jobb oldalon a subarray, mi
látni, hogy a pivot értéke 5, és a fal

75
00:03:28,860 --> 00:03:32,250
csak maradt a 6.

76
00:03:32,250 --> 00:03:34,970
És az aktuális elem is
indul ki, mint a 6.

77
00:03:34,970 --> 00:03:36,200
Tehát 6 nagyobb, mint 5.

78
00:03:36,200 --> 00:03:38,590
Hagyjuk ott, ahol ez a
jobb oldalán a fal.

79
00:03:38,590 --> 00:03:41,060
Most, mozgó, 3 kisebb, mint 5.

80
00:03:41,060 --> 00:03:44,160
Így kapcsolja az első elem
csak jobb a fal.

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

82
00:03:47,944 --> 00:03:50,750
Most költöztem a fal fel egy.

83
00:03:50,750 --> 00:03:53,010
Most mozog a 8.

84
00:03:53,010 --> 00:03:56,480
8 nagyobb, mint 5,
és így hagyjuk.

85
00:03:56,480 --> 00:03:58,720
A 4 kevesebb, mint 5, úgyhogy kapcsolja.

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

87
00:04:02,950 --> 00:04:03,570
És.

88
00:04:03,570 --> 00:04:04,820
És.

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

90
00:04:10,190 --> 00:04:13,670
>> Minden alkalommal, amikor ismételje meg a folyamatot a
bal és jobb oldalán a tömb. mi

91
00:04:13,670 --> 00:04:17,010
válasszon egy pivot, és nem az összehasonlítás
és hozzon létre egy másik szintje a bal-és

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

93
00:04:18,240 --> 00:04:21,500
Ez a rekurzív hívás addig folytatódik, amíg
elérjük a végét, amikor már

94
00:04:21,500 --> 00:04:25,290
felosztották a teljes tömb
csak subarrays hosszúságú 1.

95
00:04:25,290 --> 00:04:28,060
Onnan tudjuk, hogy a tömb rendezve
mert minden elem, a

96
00:04:28,060 --> 00:04:29,330
Valamikor volt a pivot.

97
00:04:29,330 --> 00:04:32,720
Más szóval, minden elem, minden
A számok a bal oldalon kisebb

98
00:04:32,720 --> 00:04:36,420
értékek és a számokat, hogy a
joga van a nagyobb érték.

99
00:04:36,420 --> 00:04:38,980
>> Ez a módszer nagyon jól működik, ha a
értéke a pivot választott

100
00:04:38,980 --> 00:04:41,930
hozzávetőleg a közepén
tartománya a lista értékeket.

101
00:04:41,930 --> 00:04:45,630
Ez azt jelenti, hogy, miután mozgunk
elemek körül, ott körülbelül annyi

102
00:04:45,630 --> 00:04:48,390
elemeket, hogy a bal oldalon a forgócsap
mint ahány jobbra.

103
00:04:48,390 --> 00:04:52,380
És az oszd meg és uralkodj jellege
Gyors-algoritmus ezután venni

104
00:04:52,380 --> 00:04:53,850
teljes mértékben kihasználják.

105
00:04:53,850 --> 00:04:57,500
Ez létrehoz egy futásidejű O (n log n)
n, mert meg kell tennünk n mínusz 1

106
00:04:57,500 --> 00:05:01,640
összehasonlítások minden generáció és log
n mert meg kell osztani a lista

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

108
00:05:03,210 --> 00:05:06,160
Azonban, a legrosszabb esetben ez
algoritmus is lehet O (n

109
00:05:06,160 --> 00:05:09,850
négyzeten.) Tegyük fel, minden nemzedék,
A pivot csak azért történik, hogy a

110
00:05:09,850 --> 00:05:12,520
a legkisebb, illetve a legnagyobb a
számok vagyunk válogatás.

111
00:05:12,520 --> 00:05:15,870
Ez azt jelentené, összeomlanak a listán
n-szer és a döntéshozatalban n mínusz 1

112
00:05:15,870 --> 00:05:17,690
összehasonlítást minden egyes alkalommal.

113
00:05:17,690 --> 00:05:20,490
Így o n a négyzeten.

114
00:05:20,490 --> 00:05:22,000
>> Hogyan lehet javítani a módszer?

115
00:05:22,000 --> 00:05:25,100
Egy jó módja annak, hogy javítsák a módszer
csökkenteni a valószínűségét, hogy

116
00:05:25,100 --> 00:05:28,150
Az üzemidő valaha is
o n a négyzeten.

117
00:05:28,150 --> 00:05:31,860
Ne feledje, ez a legrosszabb, legrosszabb esetben
csak akkor történhet meg, ha a

118
00:05:31,860 --> 00:05:35,320
forgócsap választott mindig a legmagasabb
vagy a legalacsonyabb érték a tömbben.

119
00:05:35,320 --> 00:05:38,630
Annak érdekében, hogy ez a kevésbé valószínű, hogy megtörténjen,
megtaláljuk a pivot a

120
00:05:38,630 --> 00:05:42,610
kiválasztása több elemet és
figyelembe véve a medián értéket.

121
00:05:42,610 --> 00:05:44,650
>> A nevem Mark Grozen-Smith,
és ez a CS50.

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

123
00:05:47,790 --> 00:05:50,930
>> Az egyszerűség kedvéért tegyük fel, hogy ezeket a
a dolgok csak egész számok, de

124
00:05:50,930 --> 00:05:51,970
tudják, hogy Quicksert -

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

126
00:05:53,160 --> 00:05:55,200
Bocsánat.

127
00:05:55,200 --> 00:06:02,000
>> Itt van az egész
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: Tényleg?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: nem állnak meg ott.

130
00:06:04,850 --> 00:06:06,100
>> SPEAKER 1: Tényleg?

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