1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Beillesztés Sort]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard Egyetem]

3
00:00:04,240 --> 00:00:07,290
[Ez CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Vessünk egy pillantást a beszúrási sort, egy algoritmus vesz egy listát a számok és rendezési őket.

5
00:00:13,060 --> 00:00:18,300
Egy algoritmus, emlékszem, egyszerűen lépésről-lépésre eljárást egy feladatra.

6
00:00:18,300 --> 00:00:23,640
Az alapötlet mögött helyezés sort, hogy ossza meg a lista két részre,

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

8
00:00:26,580 --> 00:00:29,290
>> Minden lépésnél a algoritmus, egy szám mozog

9
00:00:29,290 --> 00:00:32,439
A rendezetlen részletben a rendezett rész

10
00:00:32,439 --> 00:00:35,680
míg végül a teljes lista rendezésre.

11
00:00:35,680 --> 00:00:43,340
Itt látható a lista a hat szelektálatlan szám - 23, 42, 4, 16, 8, és 15.

12
00:00:43,340 --> 00:00:47,680
Mivel ezek a számok nem minden emelkedő sorrendben, ők rendezetlen.

13
00:00:47,680 --> 00:00:53,890
Mivel még nem kezdődött válogatás még, akkor figyelembe mind a hat elemet a rendezetlen részét.

14
00:00:53,890 --> 00:00:59,270
>> Ha egyszer elkezdünk válogatás fogjuk, hogy ezeket a számokat rendezve balra ezeket.

15
00:00:59,270 --> 00:01:03,600
Nos, kezdjük a 23, az első eleme a listában.

16
00:01:03,600 --> 00:01:06,930
Jelenleg nincs olyan eleme a mi rendezett részén még

17
00:01:06,930 --> 00:01:12,460
úgyhogy csak úgy 23, hogy a kezdetét és végét a sorrendje részét.

18
00:01:12,460 --> 00:01:16,510
Most, a rész szerint rendezve van egy szám, 23,

19
00:01:16,510 --> 00:01:20,260
és a válogatott része van az öt számot.

20
00:01:20,260 --> 00:01:27,320
Nézzük most, illessze be a következő számot a mi rendezetlen rész, 42, a rendezett rész.

21
00:01:27,320 --> 00:01:35,930
>> Ehhez szükségünk lesz összehasonlítani a 42 a 23 - az egyetlen eleme a rendezett rész eddig.

22
00:01:35,930 --> 00:01:41,980
Negyvenkét nagyobb, mint 23, így egyszerűen fűzze 42 a vége

23
00:01:41,980 --> 00:01:45,420
A rendezett részének a listán. Nagyszerű!

24
00:01:45,420 --> 00:01:51,850
Most a válogatott rész két eleme, és a válogatott rész négy elemet.

25
00:01:51,850 --> 00:01:57,200
Szóval, most már mozog a 4, a következő elem a rendezetlen rész.

26
00:01:57,200 --> 00:02:00,230
Szóval, hol kell ezt helyezni a rendezett rész?

27
00:02:00,230 --> 00:02:04,220
>> Ne feledje, hogy szeretnénk helyezni ezt a számot rendezetten

28
00:02:04,220 --> 00:02:08,680
így a válogatott része továbbra is helyes sorrendje minden alkalommal.

29
00:02:08,680 --> 00:02:14,380
Ha helyezzük a 4 jobbra a 42, akkor a lista lesz elromlott.

30
00:02:14,380 --> 00:02:18,380
Nos, nézzük tovább halad jobbról balra a mi rendezési részletben.

31
00:02:18,380 --> 00:02:23,260
Ahogy haladunk, menjünk műszak minden szám le a helyet, hogy helyet csináljon az új számot.

32
00:02:25,440 --> 00:02:31,740
Oké, 4 is kevesebb, mint 23, így nem tudunk elhelyezni itt sem.

33
00:02:31,740 --> 00:02:34,480
Menjünk a 23 megfelelő egy helyen.

34
00:02:36,500 --> 00:02:43,120
>> Ez azt jelenti, hogy szeretné helyezni a 4 az első slot a rendezett rész.

35
00:02:43,120 --> 00:02:46,300
Figyeljük meg, hogy ezt a helyet a listán már üres,

36
00:02:46,300 --> 00:02:51,120
mert mi már mozgó elemek sorrendje meghatározott, ahogy már találkozott velük.

37
00:02:51,120 --> 00:02:52,740
Rendben van. Szóval, mi vagyunk félúton.

38
00:02:52,740 --> 00:02:57,990
Folytassuk algoritmusunk behelyezésével a 16 a rendezett rész.

39
00:02:59,260 --> 00:03:03,820
Tizenhat kisebb, mint 42, úgyhogy váltani a 42 jobbra.

40
00:03:05,700 --> 00:03:10,190
Tizenhat is kevesebb, mint 23, úgyhogy azt is váltani ezt az elemet.

41
00:03:11,790 --> 00:03:20,820
>> Most, 16 4-nél nagyobb. Szóval, úgy néz ki, szeretnénk beszúrni a 16 között, a 4 és a 23.

42
00:03:20,820 --> 00:03:24,620
Amíg mozog a rendezett részén a lista jobbról balra,

43
00:03:24,620 --> 00:03:29,160
4 az első szám Láttuk, hogy a kisebb, mint a

44
00:03:29,160 --> 00:03:31,540
próbálunk beszúrni.

45
00:03:31,540 --> 00:03:35,820
Szóval, most már be a 16-ba az üres nyílásba,

46
00:03:35,820 --> 00:03:40,520
amely ne feledd, most már létrehozott mozgó elemek a rendezési rész felett

47
00:03:40,520 --> 00:03:43,340
ahogy már találkozott velük.

48
00:03:43,340 --> 00:03:47,900
>> Rendben van. Most már négy sorrendje elemet és két válogatott elemeket.

49
00:03:47,900 --> 00:03:51,600
Szóval, menjünk a 8 a rendezett rész.

50
00:03:51,600 --> 00:03:55,010
Nyolc kisebb, mint 42.

51
00:03:55,010 --> 00:03:56,940
Nyolc nem kevesebb, mint 23.

52
00:03:56,940 --> 00:04:00,230
És 8 nem kevesebb, mint 16.

53
00:04:00,230 --> 00:04:03,110
De 8 4-nél nagyobb.

54
00:04:03,110 --> 00:04:07,280
Szóval, szeretnénk beszúrni a 8 között, a 4 és a 16.

55
00:04:09,070 --> 00:04:13,650
És most már csak egy újabb elem maradt rendezni - a 15.

56
00:04:13,950 --> 00:04:16,589
Tizenöt kisebb, mint 42,

57
00:04:16,589 --> 00:04:19,130
Tizenöt nem kevesebb, mint 23.

58
00:04:19,130 --> 00:04:21,750
És 15 kisebb, mint 16.

59
00:04:21,750 --> 00:04:24,810
Azonban 15 nagyobb, mint 8.

60
00:04:24,810 --> 00:04:27,440
>> Szóval, itt van, ha azt akarjuk, hogy a végső helyezés.

61
00:04:28,770 --> 00:04:30,330
És mi történt.

62
00:04:30,330 --> 00:04:33,540
Jelenleg nincs több elem a rendezetlen rész,

63
00:04:33,540 --> 00:04:36,670
és a rendezett adag a helyes sorrendben.

64
00:04:36,670 --> 00:04:40,270
A számok sorrendben a legkisebbtől a legnagyobbig.

65
00:04:40,270 --> 00:04:44,330
Nos, vessünk egy pillantást néhány pszeudokód, amely leírja a lépéseket, már csak végre.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, akkor láthatjuk, hogy mi kell megismételni az egyes elem a listán

67
00:04:51,740 --> 00:04:57,060
kivéve az első, hiszen az első elem a rendezetlen rész egyszerűen válik

68
00:04:57,060 --> 00:05:00,220
az első elem a rendezett rész.

69
00:05:00,220 --> 00:05:06,320
A vonalak 2 és 3, mi követi nyomon a jelenlegi helyét a rendezetlen rész.

70
00:05:06,320 --> 00:05:10,450
Element számát jelenti, mi jelenleg költözik a rendezett része,

71
00:05:10,450 --> 00:05:15,600
és j jelentése az index a rendezetlen rész.

72
00:05:15,600 --> 00:05:20,980
>> A 4-es vonal, mi iterációjával a válogatott rész jobbról balra.

73
00:05:20,980 --> 00:05:26,010
Azt akarjuk, hogy hagyja abba iterációjával egyszer az elemet balra aktuális pozíció

74
00:05:26,010 --> 00:05:30,050
kevesebb, mint az elemet próbálunk beszúrni.

75
00:05:30,050 --> 00:05:35,600
On line 5, mi változik az egyes elemek találkozunk egy hellyel jobbra.

76
00:05:35,600 --> 00:05:40,950
Így lesz egy üres hely beilleszteni, ha megtaláljuk az első elem

77
00:05:40,950 --> 00:05:44,080
kevesebb, mint az elem haladunk.

78
00:05:44,080 --> 00:05:50,800
On line 6, mi frissítjük ellentétes, hogy továbbra is mozogni balra a rendezett rész.

79
00:05:50,800 --> 00:05:56,860
Végül, 7. sor, mi az elem behelyezésekor a rendezett része a listán.

80
00:05:56,860 --> 00:06:00,020
>> Tudjuk, hogy nem baj, hogy helyezze be a helyére j,

81
00:06:00,020 --> 00:06:05,360
mert már át az elemet, hogy a használt, hogy ott egy hellyel jobbra.

82
00:06:05,360 --> 00:06:09,460
Ne feledje, hogy haladunk a válogatott rész jobbról balra,

83
00:06:09,460 --> 00:06:13,960
de haladunk át osztályozatlan részén balról jobbra.

84
00:06:13,960 --> 00:06:19,090
Rendben van. Nézzük most nézd meg, hogy mennyi ideig fut, algoritmus volt.

85
00:06:19,090 --> 00:06:25,300
Majd 1. tennünk a kérdést, hogy mennyi ideig tart, ez az algoritmus futtatásához a legrosszabb esetben.

86
00:06:25,300 --> 00:06:29,040
Emlékezzünk arra, hogy az általunk képviselt ez működési időt Big O jelölést.

87
00:06:32,530 --> 00:06:38,500
Annak érdekében, hogy rendezze a listát, azt kellett navigálhat az elemek rendezetlen rész,

88
00:06:38,500 --> 00:06:43,430
és az egyes elemei potenciálisan az összes elem a rendezett rész.

89
00:06:43,430 --> 00:06:47,950
Intuitíve, ez úgy hangzik, mint egy O (n ^ 2) működését.

90
00:06:47,950 --> 00:06:51,840
>> Keresi a mi pszeudokód, hogy van egy loop beágyazva egy hurok,

91
00:06:51,840 --> 00:06:55,290
amely valóban úgy hangzik, mint egy O (n ^ 2) működését.

92
00:06:55,290 --> 00:07:01,590
Azonban a rendezett része lista nem tartalmazza a teljes lista, egészen a végéig.

93
00:07:01,590 --> 00:07:06,920
Mégis, mi esetleg be egy új elemet legelején a rendezett rész

94
00:07:06,920 --> 00:07:09,320
minden iteráció a algoritmus,

95
00:07:09,320 --> 00:07:14,500
ami azt jelenti, hogy azt kell nézni minden egyes eleme jelenleg a rendezett rész.

96
00:07:14,500 --> 00:07:20,090
Tehát ez azt jelenti, hogy az egyik esetleg összehasonlítás a második elem,

97
00:07:20,090 --> 00:07:24,660
két összehasonlítást a harmadik elem, és így tovább.

98
00:07:24,660 --> 00:07:32,480
Így, a lépcsőfokok számát az összege az egész számok 1 és a hossza a jegyzék mínusz 1.

99
00:07:32,480 --> 00:07:35,240
Mi lehet képviseli ezt a összegzésben.

100
00:07:41,170 --> 00:07:47,270
>> Nem fogunk belemenni összegzések van, de kiderült, hogy ez a összegzési egyenlő

101
00:07:47,270 --> 00:07:57,900
n (n - 1) több mint 2, ami megegyezik n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Amikor beszélünk, aszimptotikus futási,

103
00:08:00,800 --> 00:08:05,170
ez n ^ 2 kifejezést fogja uralni ezt a n kifejezést.

104
00:08:05,170 --> 00:08:11,430
Szóval, helyezés rendezés Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Mi lenne, ha futott helyezés sort egy már rendezett listát.

106
00:08:16,150 --> 00:08:20,960
Ebben az esetben mi lenne egyszerűen felépíteni a rendezett rész balról jobbra.

107
00:08:20,960 --> 00:08:25,050
Szóval, akkor csak be kell a sorrendben az n lépéseket.

108
00:08:25,050 --> 00:08:29,740
>> Ez azt jelenti, hogy a beszúrási sort egy best-case teljesítése n,

109
00:08:29,740 --> 00:08:34,130
amit képviselnek, azzal Ω (n).

110
00:08:34,130 --> 00:08:36,190
És ez azt helyezés sort,

111
00:08:36,190 --> 00:08:40,429
Csak egy a sok algoritmusok tudjuk használni, hogy rendezni egy listát.

112
00:08:40,429 --> 00:08:43,210
A nevem Tommy, és ez CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, csak nem tudja megállítani, hogy ha egyszer elindul.

115
00:09:01,620 --> 00:09:04,760
Ó, mi volt, hogy - >> Boom!