1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Vessünk egy pillantást a kiválasztási sort az algoritmus

2
00:00:09,980 --> 00:00:12,800
meghozatalának számok listájának és rendezési őket.

3
00:00:12,800 --> 00:00:15,750
Egy algoritmus, emlékszem, egyszerűen lépésről-lépésre

4
00:00:15,750 --> 00:00:18,370
eljárás egy feladatra.

5
00:00:18,370 --> 00:00:21,470
Az alapötlet mögött kiválasztási rendezés osztani

6
00:00:21,470 --> 00:00:23,390
A lista két részre -

7
00:00:23,390 --> 00:00:26,810
rendezett rész és egy válogatott részt.

8
00:00:26,810 --> 00:00:30,200
Minden lépésnél a algoritmus, egy szám mozog-ból a

9
00:00:30,200 --> 00:00:33,800
osztályozatlan része a rendezett részét, amíg végül a

10
00:00:33,800 --> 00:00:35,880
teljes lista rendezésre.

11
00:00:35,880 --> 00:00:38,510
Tehát itt van egy lista a hat szám -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, és 15.

13
00:00:44,010 --> 00:00:47,680
Most a teljes lista tekinthető rendezetlen.

14
00:00:47,680 --> 00:00:51,770
Annak ellenére, hogy több, mint a május 16 már annak helyes

15
00:00:51,770 --> 00:00:56,040
location, algoritmusunk nem tudhatja, hogy mindaddig, amíg a

16
00:00:56,040 --> 00:00:57,980
teljes lista rendezésre.

17
00:00:57,980 --> 00:01:01,355
Tehát mi úgy minden számot rendezetlen, amíg rendezni

18
00:01:01,355 --> 00:01:03,800
magunk.

19
00:01:03,800 --> 00:01:06,890
Tudjuk, hogy szeretnénk a listát, hogy növekvő sorrendben.

20
00:01:06,890 --> 00:01:10,200
Tehát mi szeretnénk felépíteni a rendezett része a mi lista

21
00:01:10,200 --> 00:01:13,280
balról jobbra, a legkisebbtől a legnagyobbig.

22
00:01:13,280 --> 00:01:17,970
Ehhez, akkor meg kell találni a legkisebb rendezetlen elem

23
00:01:17,970 --> 00:01:21,350
és tegye a végén a rendezett rész.

24
00:01:21,350 --> 00:01:25,370
Mivel ez a lista nincs rendezve, az egyetlen módja, hogy az, hogy

25
00:01:25,370 --> 00:01:29,330
nézd meg minden egyes elemet a rendezetlen rész, emlékezve

26
00:01:29,330 --> 00:01:32,010
melyik eleme a legalacsonyabb és összehasonlítása

27
00:01:32,010 --> 00:01:33,770
minden elem e.

28
00:01:33,770 --> 00:01:36,150
Tehát akkor először nézd meg a 23.

29
00:01:36,150 --> 00:01:38,650
Ez az első elem, láttuk, így emlékezni fogunk

30
00:01:38,650 --> 00:01:40,050
rá, mint a minimális.

31
00:01:40,050 --> 00:01:42,320
Ezután megnézzük, 42.

32
00:01:42,320 --> 00:01:46,720
42 nagyobb, mint 23, így a 23 még mindig a minimális.

33
00:01:46,720 --> 00:01:51,210
Ezután a 4, ami kevesebb, mint 23, ezért fogunk emlékezni 4

34
00:01:51,210 --> 00:01:52,880
az új minimum.

35
00:01:52,880 --> 00:01:56,380
Következő 16, amely nagyobb, mint 4, SO 4-

36
00:01:56,380 --> 00:01:57,980
még mindig a minimális.

37
00:01:57,980 --> 00:02:03,670
8 nagyobb, mint 4, és 15 nagyobb, mint 4, SO 4-kell

38
00:02:03,670 --> 00:02:05,980
a legkisebb rendezetlen elem.

39
00:02:05,980 --> 00:02:09,350
Tehát annak ellenére, hogy, mint az emberek akkor rögtön láthatjuk, hogy a 4.

40
00:02:09,350 --> 00:02:12,300
a legkisebb elem, a mi algoritmus kell nézni

41
00:02:12,300 --> 00:02:15,710
minden rendezetlen elem, még azután is, hogy megtalálta a 4 - a

42
00:02:15,710 --> 00:02:16,860
minimum elem.

43
00:02:16,860 --> 00:02:19,900
Tehát most, hogy megtaláltuk a legkisebb elem, 4, akkor szeretnénk

44
00:02:19,900 --> 00:02:23,410
hogy helyezze át a rendezett része a listán.

45
00:02:23,410 --> 00:02:27,320
Mivel ez az első lépés, ez azt jelenti, akarjuk helyezni 4-es

46
00:02:27,320 --> 00:02:29,680
A lista elején.

47
00:02:29,680 --> 00:02:33,040
Most a 23. elején a lista, így a

48
00:02:33,040 --> 00:02:36,080
nézzük cserélni a 4 és a 23.

49
00:02:36,080 --> 00:02:38,870
Tehát most A lista így néz ki.

50
00:02:38,870 --> 00:02:42,710
Tudjuk, hogy a 4-ben kell, hogy legyen a végleges helyére, mert

51
00:02:42,710 --> 00:02:45,890
mind a legkisebb elem és az elem elején

52
00:02:45,890 --> 00:02:46,960
a lista.

53
00:02:46,960 --> 00:02:50,650
Tehát ez azt jelenti, hogy mi soha nem kell mozgatni újra.

54
00:02:50,650 --> 00:02:53,910
Szóval ismételje meg ezt a folyamatot, hogy egy újabb elemet a

55
00:02:53,910 --> 00:02:55,910
rendezett része a listán.

56
00:02:55,910 --> 00:02:58,950
Tudjuk, hogy nem kell, hogy nézd meg a 4, mert

57
00:02:58,950 --> 00:03:00,000
már rendezve.

58
00:03:00,000 --> 00:03:03,540
Így tudjuk kezdeni a 42, amit majd emlékezni, mint a

59
00:03:03,540 --> 00:03:05,290
minimum elem.

60
00:03:05,290 --> 00:03:08,700
Így a következő fogjuk nézni a 23, ami kisebb, mint 42, így

61
00:03:08,700 --> 00:03:11,620
emlékszem 23 az új minimum.

62
00:03:11,620 --> 00:03:14,870
Azután látjuk a 16, amely nem kisebb, mint 23, így

63
00:03:14,870 --> 00:03:16,800
16 az új minimum.

64
00:03:16,800 --> 00:03:19,720
Most nézd meg a 8, amely kevesebb, mint 16, így

65
00:03:19,720 --> 00:03:21,130
8 az új minimum.

66
00:03:21,130 --> 00:03:25,900
És végül 8 kisebb, mint 15, így tudjuk, hogy a 8. egy minimum

67
00:03:25,900 --> 00:03:27,780
rendezetlen elem.

68
00:03:27,780 --> 00:03:30,660
Tehát ez azt jelenti, hogy meg kell csatolnia a 8 rendezve

69
00:03:30,660 --> 00:03:32,450
részét a lista.

70
00:03:32,450 --> 00:03:35,990
Most 4 az egyetlen rendezett elem, ezért szeretnénk helyezni

71
00:03:35,990 --> 00:03:38,410
a 8 mellett a 4.

72
00:03:38,410 --> 00:03:41,920
Mivel a 42 az első elem a rendezetlen része a

73
00:03:41,920 --> 00:03:47,260
listában, akkor szeretnénk cserélni a 42 és a 8.

74
00:03:47,260 --> 00:03:49,680
Tehát most A lista így néz ki.

75
00:03:49,680 --> 00:03:53,830
4. és 8. képviseli a rendezett részét a jegyzék, és a

76
00:03:53,830 --> 00:03:56,440
fennmaradó számok a rendezetlen

77
00:03:56,440 --> 00:03:58,260
részét a lista.

78
00:03:58,260 --> 00:04:00,630
Szóval továbbra is egy másik iteráció.

79
00:04:00,630 --> 00:04:03,850
Kezdjük 23 ebben az időben, hiszen nem kell nézni

80
00:04:03,850 --> 00:04:05,770
a 4 és a 8 többé, mert már

81
00:04:05,770 --> 00:04:07,660
már rendezve.

82
00:04:07,660 --> 00:04:10,270
16 kevesebb, mint 23, ezért fogunk emlékezni

83
00:04:10,270 --> 00:04:12,070
16 az új minimum.

84
00:04:12,070 --> 00:04:18,149
16 kisebb, mint 42, de 15 kevesebb, mint 16, így 15 kell, hogy legyen

85
00:04:18,149 --> 00:04:20,480
a minimális rendezetlen elem.

86
00:04:20,480 --> 00:04:24,580
Tehát most szeretnénk cserélni a 15 és az 23-

87
00:04:24,580 --> 00:04:26,310
nekünk ezt a listát.

88
00:04:26,310 --> 00:04:30,500
A rendezett része a csoportba tartoznak az a 4., 8. és 15., valamint

89
00:04:30,500 --> 00:04:33,210
ezek az elemek még mindig rendezetlen.

90
00:04:33,210 --> 00:04:36,900
De ez csak azért történik, hogy a következő rendezetlen elem, 16,

91
00:04:36,900 --> 00:04:38,480
már rendezve.

92
00:04:38,480 --> 00:04:42,060
Azonban nincs mód a mi algoritmus tudni, hogy a 16

93
00:04:42,060 --> 00:04:45,230
már a megfelelő helyen, ezért kell még

94
00:04:45,230 --> 00:04:47,870
ismételje meg pontosan ugyanazt a folyamatot.

95
00:04:47,870 --> 00:04:53,750
Látjuk tehát, hogy a 16. kisebb, mint 42, és 16 kisebb, mint 23, így

96
00:04:53,750 --> 00:04:56,230
16 kell, hogy legyen a minimum elem.

97
00:04:56,230 --> 00:04:59,010
Lehetetlen, hogy ezt az elemet cserélni önmagával, így tudjuk

98
00:04:59,010 --> 00:05:01,780
egyszerűen hagyja ezt a helyet.

99
00:05:01,780 --> 00:05:04,660
Tehát szükség van egy több lépéses a mi algoritmus.

100
00:05:04,660 --> 00:05:09,370
A 42 23-nál nagyobb, tehát 23 kell, hogy legyen a

101
00:05:09,370 --> 00:05:10,970
minimum rendezetlen elem.

102
00:05:10,970 --> 00:05:17,410
Amint cserélni a 23 és a 42, akkor a végén a mi végső

103
00:05:17,410 --> 00:05:18,530
rendezett lista -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Tudjuk, hogy 42 kell a megfelelő helyre, mivel ez a

106
00:05:26,830 --> 00:05:30,210
egyetlen eleme maradt, és ez kiválasztás sort.

107
00:05:30,210 --> 00:05:32,100
Nézzük most hivatalossá algoritmusunk néhány

108
00:05:32,100 --> 00:05:34,540
pszeudokód.

109
00:05:34,540 --> 00:05:37,760
On line on, azt látjuk, hogy meg kell integrálni felett

110
00:05:37,760 --> 00:05:39,530
minden eleme a listán.

111
00:05:39,530 --> 00:05:42,150
Kivéve az utolsó elem, mivel az 1 elem

112
00:05:42,150 --> 00:05:44,230
lista már rendezve.

113
00:05:44,230 --> 00:05:48,100
On line kettő, úgy véljük, az első eleme a válogatott

114
00:05:48,100 --> 00:05:51,080
része a listát, hogy a minimum, mint mi a mi

115
00:05:51,080 --> 00:05:53,750
Például, így van valami összehasonlítani.

116
00:05:53,750 --> 00:05:57,260
Vonal 3 kezdődik a második kör, melyben iterációkhoz

117
00:05:57,260 --> 00:05:59,170
egyes rendezetlen elem.

118
00:05:59,170 --> 00:06:02,150
Tudjuk, hogy miután én iteráció, a rendezett rész

119
00:06:02,150 --> 00:06:05,330
Az A lista kell i elemek, mióta minden lépésben

120
00:06:05,330 --> 00:06:06,890
rendezések egyik eleme.

121
00:06:06,890 --> 00:06:11,770
Tehát az első válogatott elemnek kell lennie helyzetben i plusz 1.

122
00:06:11,770 --> 00:06:15,440
On line négy, összehasonlítjuk az aktuális elem a minimum

123
00:06:15,440 --> 00:06:17,750
elem, amit eddig láttunk.

124
00:06:17,750 --> 00:06:20,560
Ha az aktuális elem kisebb, mint a minimális

125
00:06:20,560 --> 00:06:23,870
elem, akkor emlékezni az aktuális elem, mint az új

126
00:06:23,870 --> 00:06:26,250
minimum on line öt.

127
00:06:26,250 --> 00:06:29,900
Végül, a vonalakon hat és hét, akkor cserélje ki a minimum

128
00:06:29,900 --> 00:06:33,080
elem az első szelektálatlan elem, ezáltal

129
00:06:33,080 --> 00:06:36,990
hozzátéve, hogy a rendezett része a listán.

130
00:06:36,990 --> 00:06:40,030
Ha van egy algoritmus, egy fontos kérdést feltenni

131
00:06:40,030 --> 00:06:43,370
magunkat, mint programozó is, hogy mennyi ideig volt, hogy az el?

132
00:06:43,370 --> 00:06:46,970
Majd 1. tennünk a kérdést, hogy mennyi ideig tart, ezt a

133
00:06:46,970 --> 00:06:50,070
algoritmus fut a legrosszabb esetben?

134
00:06:50,070 --> 00:06:51,640
Recall általunk képviselt ez futás

135
00:06:51,640 --> 00:06:55,060
idő nagy O jelölést.

136
00:06:55,060 --> 00:06:58,650
Annak megállapítása érdekében, a minimális rendezetlen elem, mi

137
00:06:58,650 --> 00:07:01,880
lényegében kellett összehasonlítani egyes elem a listán

138
00:07:01,880 --> 00:07:04,040
minden más elem a listában.

139
00:07:04,040 --> 00:07:08,430
Intuitíve, ez úgy hangzik, mint egy O n négyzetes működését.

140
00:07:08,430 --> 00:07:12,050
Keresi a mi pszeudokód, mi is van egy loop beágyazva

141
00:07:12,050 --> 00:07:14,420
egy hurok, ami valóban úgy hangzik, mint egy O

142
00:07:14,420 --> 00:07:16,480
n négyzet működését.

143
00:07:16,480 --> 00:07:19,250
Azonban ne feledjük, hogy nem kell, hogy nézd át a

144
00:07:19,250 --> 00:07:23,460
teljes lista meghatározása során minimum rendezetlen elem?

145
00:07:23,460 --> 00:07:26,600
Miután tudta, hogy a 4-es rendezett, például, hogy nem

146
00:07:26,600 --> 00:07:28,170
kell, hogy nézd meg újra.

147
00:07:28,170 --> 00:07:31,020
Így működik ez alacsonyabb a működési idő?

148
00:07:31,020 --> 00:07:34,510
A mi listáját hossza 6, mi szükséges ahhoz, hogy 5

149
00:07:34,510 --> 00:07:37,990
összehasonlítást az első elem, négy összehasonlítások

150
00:07:37,990 --> 00:07:40,750
A második elem, és így tovább.

151
00:07:40,750 --> 00:07:44,690
Ez azt jelenti, hogy a lépcsőfokok számát az összege

152
00:07:44,690 --> 00:07:49,160
az egész szám 1-től a hossza a jegyzék mínusz 1.

153
00:07:49,160 --> 00:07:51,005
Mi lehet képviseli ezt a összegzésben.

154
00:07:57,980 --> 00:07:59,910
Nem fogunk belemenni összegzések itt.

155
00:07:59,910 --> 00:08:04,900
De kiderült, hogy ez az összegzési egyenlő n-szer

156
00:08:04,900 --> 00:08:07,540
n mínusz 1 több mint 2.

157
00:08:07,540 --> 00:08:14,220
Vagy azzal egyenértékű, n kockás több mint 2 mínusz n több mint 2.

158
00:08:14,220 --> 00:08:18,860
Amikor beszélünk, aszimptotikus futási e n kockás kifejezés

159
00:08:18,860 --> 00:08:22,070
fogja uralni ezt a n kifejezést.

160
00:08:22,070 --> 00:08:27,850
Szóval kiválasztás rendezés O n négyzeten.

161
00:08:27,850 --> 00:08:31,460
Emlékezzünk vissza, hogy a mi példánkban, a kiválasztási sorrend továbbra is szükség van

162
00:08:31,460 --> 00:08:33,850
ellenőrizheti, hogy egy számot már rendezve

163
00:08:33,850 --> 00:08:35,450
kellett mozgatni.

164
00:08:35,450 --> 00:08:38,929
Tehát ez azt jelenti, hogy ha mi futott kiválasztás sort felett már

165
00:08:38,929 --> 00:08:43,070
rendezett lista, szükség lenne az azonos lépések számát, mivel

166
00:08:43,070 --> 00:08:46,340
lenne, ha fut egy teljesen rendezetlen listát.

167
00:08:46,340 --> 00:08:51,470
Szóval kiválasztás sort egy legjobb esetben teljesítményt n négyzetes,

168
00:08:51,470 --> 00:08:56,820
amit képviselnek, azzal omega n négyzeten.

169
00:08:56,820 --> 00:08:58,600
És ez a fajta kiválasztás.

170
00:08:58,600 --> 00:09:00,630
Csak egy a sok algoritmusok tudunk

171
00:09:00,630 --> 00:09:02,390
használja, hogy rendezni egy listát.

172
00:09:02,390 --> 00:09:05,910
A nevem Tommy, és ez CS50.