1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Invoeging Sorteer]

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

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

4
00:00:07,290 --> 00:00:13,060
Kom ons neem 'n blik op die invoeging soort, 'n algoritme vir die neem van 'n lys van getalle en sorteer hulle.

5
00:00:13,060 --> 00:00:18,300
'N algoritme, onthou, is eenvoudig 'n stap-vir-stap proses vir die totstandbrenging van 'n taak.

6
00:00:18,300 --> 00:00:23,640
Die basiese idee agter die invoeging soort, is ons lys te verdeel in twee gedeeltes,

7
00:00:23,640 --> 00:00:26,580
'n gesorteer gedeelte en 'n ongesorteerde gedeelte.

8
00:00:26,580 --> 00:00:29,290
>> By elke stap van die algoritme, is 'n aantal verskuif

9
00:00:29,290 --> 00:00:32,439
van die ongesorteerde gedeelte aan die gesorteerde gedeelte

10
00:00:32,439 --> 00:00:35,680
totdat uiteindelik die hele lys is gesorteer.

11
00:00:35,680 --> 00:00:43,340
Hier is die lys van ses ongesorteerde getalle - 23, 42, 4, 16, 8 en 15.

12
00:00:43,340 --> 00:00:47,680
Aangesien hierdie getalle is nie al nie in stygende volgorde, hulle ongesorteerde data.

13
00:00:47,680 --> 00:00:53,890
Want ons het nie begin sorteer nog nie, sal ons al ses elemente oorweeg ons ongesorteerde gedeelte.

14
00:00:53,890 --> 00:00:59,270
>> Sodra ons begin sorteer, sal ons hierdie gesorteer nommers aan die linkerkant van hierdie.

15
00:00:59,270 --> 00:01:03,600
So, laat ons begin met 23, die eerste element in ons lys.

16
00:01:03,600 --> 00:01:06,930
Ons het nie enige elemente in ons gesorteer gedeelte nie,

17
00:01:06,930 --> 00:01:12,460
so laat ons oorweeg net 23 aan die begin en einde van ons gesorteer gedeelte.

18
00:01:12,460 --> 00:01:16,510
Nou, ons gesorteer gedeelte het 'n nommer 23,

19
00:01:16,510 --> 00:01:20,260
en ons ongesorteerde gedeelte het hierdie vyf getalle.

20
00:01:20,260 --> 00:01:27,320
Kom ons plaas die volgende getal in ons ongesorteerde gedeelte, 42, in die gesorteerde gedeelte.

21
00:01:27,320 --> 00:01:35,930
>> Om dit te doen, sal ons nodig het om die 42 te vergelyk aan die 23 - tot dusver die enigste element in ons gesorteer gedeelte.

22
00:01:35,930 --> 00:01:41,980
Twee-en-veertig is groter as 23 is, sodat ons kan net 42 te heg aan die einde

23
00:01:41,980 --> 00:01:45,420
van die gesorteerde gedeelte van die lys. Great!

24
00:01:45,420 --> 00:01:51,850
Nou ons gesorteer gedeelte het twee elemente, en ons ongesorteerde gedeelte het vier elemente.

25
00:01:51,850 --> 00:01:57,200
So, laat ons beweeg nou na die 4, die volgende element in die ongesorteerde gedeelte.

26
00:01:57,200 --> 00:02:00,230
So, waar moet dit geplaas word in die gesorteerde gedeelte?

27
00:02:00,230 --> 00:02:04,220
>> Onthou, ons wil hierdie nommer te plaas in gesorteer einde

28
00:02:04,220 --> 00:02:08,680
sodat ons gesorteer gedeelte bly korrek gesorteer ten alle tye.

29
00:02:08,680 --> 00:02:14,380
As ons plaas die 4 aan die regterkant van die 42, dan sal ons lys uit van orde.

30
00:02:14,380 --> 00:02:18,380
So, laat ons voortgaan om regs na links te beweeg in ons soort gedeelte.

31
00:02:18,380 --> 00:02:23,260
Soos ons beweeg, laat ons skuif elke nommer 'n plek af om plek te maak vir die nuwe nommer.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 is ook minder as 23, so ons kan nie plaas dit hier nie.

33
00:02:31,740 --> 00:02:34,480
Kom ons beweeg die 23 regte een plek.

34
00:02:36,500 --> 00:02:43,120
>> Dit beteken dat ons wil die 4 in die eerste slot in die gesorteerde gedeelte te plaas.

35
00:02:43,120 --> 00:02:46,300
Let op hoe hierdie ruimte in die lys wat reeds leeg was,

36
00:02:46,300 --> 00:02:51,120
want ons het beweeg gesorteer elemente as ons teëgekom het.

37
00:02:51,120 --> 00:02:52,740
Alles reg. So, ons is halfpad daar.

38
00:02:52,740 --> 00:02:57,990
Laat ons voortgaan om ons algoritme deur die invoeging van die 16 in die gesorteerde gedeelte.

39
00:02:59,260 --> 00:03:03,820
Sestien minder as 42 is, so laat ons skuif die 42 aan die regterkant.

40
00:03:05,700 --> 00:03:10,190
Sestien is ook minder as 23, so laat ons ook daardie element verskuif.

41
00:03:11,790 --> 00:03:20,820
>> Nou, 16 is groter as 4. So, dit lyk asof ons wil die 16 in te voeg tussen die 4 en die 23.

42
00:03:20,820 --> 00:03:24,620
Terwyl dit beweeg deur middel van die gesorteerde gedeelte van die lys van regs na links,

43
00:03:24,620 --> 00:03:29,160
4 is die eerste getal wat ons gesien het wat kleiner is as die aantal

44
00:03:29,160 --> 00:03:31,540
ons probeer om in te voeg.

45
00:03:31,540 --> 00:03:35,820
So, nou het ons kan die 16 voeg in hierdie leë slot,

46
00:03:35,820 --> 00:03:40,520
wat onthou, het ons geskep deur bewegende elemente in die soort gedeelte oor

47
00:03:40,520 --> 00:03:43,340
as ons teëgekom het.

48
00:03:43,340 --> 00:03:47,900
>> Alles reg. Nou, ons het vier gesorteer elemente en twee ongesorteerde elemente.

49
00:03:47,900 --> 00:03:51,600
So, laat ons skuif die 8 in die gesorteerde gedeelte.

50
00:03:51,600 --> 00:03:55,010
Agt is minder as 42.

51
00:03:55,010 --> 00:03:56,940
Agt is minder as 23.

52
00:03:56,940 --> 00:04:00,230
En 8 is minder as 16.

53
00:04:00,230 --> 00:04:03,110
Maar 8 is groter as 4.

54
00:04:03,110 --> 00:04:07,280
So, wil ons graag die 8 tussen die 4 en die 16 in te voeg.

55
00:04:09,070 --> 00:04:13,650
En nou, ons het net een element meer links te sorteer - 15.

56
00:04:13,950 --> 00:04:16,589
Vyftien is minder as 42,

57
00:04:16,589 --> 00:04:19,130
Vyftien is minder as 23.

58
00:04:19,130 --> 00:04:21,750
En 15 is minder as 16.

59
00:04:21,750 --> 00:04:24,810
Maar 15 is groter as 8.

60
00:04:24,810 --> 00:04:27,440
>> So, hier is waar ons wil ons finale invoeging te maak.

61
00:04:28,770 --> 00:04:30,330
En ons klaar is.

62
00:04:30,330 --> 00:04:33,540
Ons het nie meer elemente in die ongesorteerde gedeelte,

63
00:04:33,540 --> 00:04:36,670
en ons gesorteer gedeelte is in die korrekte volgorde.

64
00:04:36,670 --> 00:04:40,270
Die getalle bestel word van die kleinste tot die grootste.

65
00:04:40,270 --> 00:04:44,330
So, kom ons neem 'n blik op sommige pseudokode wat beskryf die stappe wat ons net uitgevoer.

66
00:04:46,760 --> 00:04:51,740
>> Op lyn 1, kan ons sien dat ons nodig het om te itereer oor elke element in die lys

67
00:04:51,740 --> 00:04:57,060
behalwe die eerste, sal net sedert die eerste element in die ongesorteerde gedeelte

68
00:04:57,060 --> 00:05:00,220
die eerste element in die gesorteerde gedeelte.

69
00:05:00,220 --> 00:05:06,320
Op die lyne 2 en 3, is ons die dop van ons huidige plek in die ongesorteerde gedeelte.

70
00:05:06,320 --> 00:05:10,450
Element verteenwoordig die aantal wat ons tans in die gesorteerde gedeelte beweeg,

71
00:05:10,450 --> 00:05:15,600
en j verteenwoordig die indeks in die ongesorteerde gedeelte.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, ons iterating deur die gesorteerde gedeelte van regs na links.

73
00:05:20,980 --> 00:05:26,010
Ons wil om te stop iterating sodra die element aan die linkerkant van ons huidige posisie

74
00:05:26,010 --> 00:05:30,050
minder is as die element wat ons probeer om te plaas.

75
00:05:30,050 --> 00:05:35,600
On line 5, ons elke element wat ons teëkom een ​​spasie aan die regterkant te skuif.

76
00:05:35,600 --> 00:05:40,950
Op dié manier, sal ons 'n duidelike ruimte in te voeg in wanneer ons die eerste element

77
00:05:40,950 --> 00:05:44,080
minder as die element wat ons beweeg.

78
00:05:44,080 --> 00:05:50,800
On line 6, werk ons ​​counter om voort te gaan om te beweeg links deur die gesorteerde gedeelte.

79
00:05:50,800 --> 00:05:56,860
Ten slotte, on line 7, ons invoeging van die element in die gesorteerde gedeelte van die lys.

80
00:05:56,860 --> 00:06:00,020
>> Ons weet dat dit is okay om te voeg in posisie j,

81
00:06:00,020 --> 00:06:05,360
want ons het reeds die element wat gebruik word om daar te wees een spasie aan die regterkant beweeg.

82
00:06:05,360 --> 00:06:09,460
Onthou, ons beweeg deur middel van die gesorteerde gedeelte van regs na links,

83
00:06:09,460 --> 00:06:13,960
maar ons is deur die ongesorteerde gedeelte van links na regs beweeg.

84
00:06:13,960 --> 00:06:19,090
Alles reg. Kom ons neem 'n blik op hoe lank loop dat die algoritme het.

85
00:06:19,090 --> 00:06:25,300
Ons sal eers die vraag vra hoe lank neem dit vir hierdie algoritme uit te voer in die ergste geval.

86
00:06:25,300 --> 00:06:29,040
Onthou dat ons hierdie tyd met Big O notasie verteenwoordig.

87
00:06:32,530 --> 00:06:38,500
Ten einde ons lys te sorteer, moes ons itereer oor die elemente in die ongesorteerde gedeelte,

88
00:06:38,500 --> 00:06:43,430
en vir elk van hierdie elemente, potensieel oor al die elemente in die gesorteerde gedeelte.

89
00:06:43,430 --> 00:06:47,950
Intuïtief, dit klink soos 'n O (n ^ 2) werking.

90
00:06:47,950 --> 00:06:51,840
>> Soek by ons pseudokode, ons het 'n geneste lus in 'n ander lus,

91
00:06:51,840 --> 00:06:55,290
wat, inderdaad, klink soos 'n O (n ^ 2) werking.

92
00:06:55,290 --> 00:07:01,590
Het egter die gesorteer gedeelte van die lys bevat nie die hele lys tot die bitter einde.

93
00:07:01,590 --> 00:07:06,920
Tog, ons kan potensieel voeg 'n nuwe element by die begin van die gesorteerde gedeelte

94
00:07:06,920 --> 00:07:09,320
op elke iterasie van die algoritme,

95
00:07:09,320 --> 00:07:14,500
wat beteken dat ons wil hê om te kyk na elke element in die gesorteerde gedeelte.

96
00:07:14,500 --> 00:07:20,090
So, wat beteken dat ons moontlik kan maak 'n vergelyking vir die tweede element,

97
00:07:20,090 --> 00:07:24,660
twee vergelykings vir die derde element, en so aan.

98
00:07:24,660 --> 00:07:32,480
So, die totale getal van die stappe is die som van die heelgetalle van 1 tot die lengte van die lys minus 1.

99
00:07:32,480 --> 00:07:35,240
Ons kan verteenwoordig hierdie met 'n opsomming.

100
00:07:41,170 --> 00:07:47,270
>> Ons sal nie gaan in die opsommings hier, maar dit blyk dat hierdie opsomming is gelyk aan

101
00:07:47,270 --> 00:07:57,900
N (n - 1) oor 2, wat gelykstaande is n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Wanneer praat oor die asimptotiese runtime,

103
00:08:00,800 --> 00:08:05,170
hierdie n ^ 2 termyn gaan hierdie n term te oorheers.

104
00:08:05,170 --> 00:08:11,430
So, invoeging soort Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Wat gebeur as ons hardloop die invoeging soort op 'n reeds gesorteerde lys.

106
00:08:16,150 --> 00:08:20,960
In daardie geval, ons wil net die opbou van die gesorteerde gedeelte van links na regs.

107
00:08:20,960 --> 00:08:25,050
So, ons sal net op die einde van n stappe nodig.

108
00:08:25,050 --> 00:08:29,740
>> Dit beteken dat die invoeging soort het 'n beste-geval prestasie van n,

109
00:08:29,740 --> 00:08:34,130
wat ons met Ω (n).

110
00:08:34,130 --> 00:08:36,190
En dit is die vir invoeging soort,

111
00:08:36,190 --> 00:08:40,429
net een van die vele algoritmes wat ons kan gebruik om 'n lys te sorteer.

112
00:08:40,429 --> 00:08:43,210
My naam is Tommy, en dit is CS50.

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

114
00:08:46,110 --> 00:08:49,230
O, jy kan net nie ophou dat wanneer dit begin.

115
00:09:01,620 --> 00:09:04,760
O, ons het dit gedoen - >> Boom!