1
00:00:00,000 --> 00:00:02,826
>> [TÓNLIST spila]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Svo er innsetning konar annar
algrím við getum notað til að raða fylki.

4
00:00:09,370 --> 00:00:12,350
Hugmyndin á bak við þetta reiknirit
er að byggja flokkaður array þinn

5
00:00:12,350 --> 00:00:19,670
í stað, breytast þætti úr
hvernig sem þú ferð, til að gera pláss.

6
00:00:19,670 --> 00:00:22,240
Þetta er aðeins öðruvísi
frá vali tegund eða kúla

7
00:00:22,240 --> 00:00:25,460
tegund, til dæmis, þar
við erum að stilla stöðum,

8
00:00:25,460 --> 00:00:26,910
þar sem við erum að gera skiptasamninga.

9
00:00:26,910 --> 00:00:29,760
>> Í þessu tilfelli sem við erum í raun og veru
að gera er að renna þættir

10
00:00:29,760 --> 00:00:31,390
yfir, út af the vegur.

11
00:00:31,390 --> 00:00:34,030
Hvernig virkar þetta reiknirit
vinna í sauðakóða?

12
00:00:34,030 --> 00:00:37,646
Jæja við skulum bara geðþótta segja að
Fyrsti þátturinn í fylkinu er flokkaður.

13
00:00:37,646 --> 00:00:38,770
Við erum að byggja það í stað.

14
00:00:38,770 --> 00:00:42,660
>> Við ætlum að fara einn þáttur í einu og
byggja það, og svo the fyrstur hlutur sem við sjáum

15
00:00:42,660 --> 00:00:43,890
er einn þáttur array.

16
00:00:43,890 --> 00:00:47,720
Og skilgreiningu, einn
þáttur array er raðað.

17
00:00:47,720 --> 00:00:50,850
>> Þá munum við endurtaka þetta ferli until--
við munum endurtaka eftirfarandi ferli

18
00:00:50,850 --> 00:00:52,900
þar alla þá þætti eru flokkuð.

19
00:00:52,900 --> 00:00:57,770
Horfðu á næstu óflokkuðu frumefni og
setja það inn í raðaða hluta,

20
00:00:57,770 --> 00:01:01,209
með því að færa þarf fjölda
þætti út af the vegur.

21
00:01:01,209 --> 00:01:03,750
Vonandi þetta visualization
mun hjálpa þér að sjá nákvæmlega hvað er

22
00:01:03,750 --> 00:01:05,980
fara á með innsetningu tagi.

23
00:01:05,980 --> 00:01:08,010
>> Svo aftur, hér er okkar
allt Óflokkaður array,

24
00:01:08,010 --> 00:01:10,970
alla þá þætti fram í rauðu.

25
00:01:10,970 --> 00:01:13,320
Og við skulum fylgja
skref sauðakóðanum.

26
00:01:13,320 --> 00:01:16,970
The fyrstur hlutur sem við gerum, er við köllum
Fyrsti þátturinn í fylkinu, raðað.

27
00:01:16,970 --> 00:01:20,920
Þannig að við erum bara að segja
fimm, þú ert nú flokkaður.

28
00:01:20,920 --> 00:01:24,570
>> Þá við skoðum næst
Óflokkaður þáttur í fylkinu

29
00:01:24,570 --> 00:01:27,610
og við viljum að setja sem
í raðaða hluta,

30
00:01:27,610 --> 00:01:29,750
með því að færa þætti yfir.

31
00:01:29,750 --> 00:01:33,470
Svo er tveir næsta Óflokkaður
þáttur í fylkinu.

32
00:01:33,470 --> 00:01:36,250
Ljóst tilheyrir það áður en
fimm, svo hvað við ætlum að gera

33
00:01:36,250 --> 00:01:41,580
er tegund af halda tvær hliðar fyrir annað,
skipta fimm yfir, og þá setja tvo

34
00:01:41,580 --> 00:01:43,210
áður fimm, hvar á að ætti að fara.

35
00:01:43,210 --> 00:01:45,280
Og nú getum við sagt að tvö er raðað.

36
00:01:45,280 --> 00:01:48,400
>> Svo eins og þú geta sjá, höfum við bara svo langt
horfði á tvo þætti fylkisins.

37
00:01:48,400 --> 00:01:50,600
Við höfum ekki litið á það
hvíla á öllum, en við höfum

38
00:01:50,600 --> 00:01:54,582
fékk þessir tveir þættir raðað eftir
Vegur breytast vélbúnaður.

39
00:01:54,582 --> 00:01:56,410
>> Þannig að við endurtaka ferlið aftur.

40
00:01:56,410 --> 00:01:58,850
Horfðu á næstu Óflokkaður
þáttur, sem er eitt.

41
00:01:58,850 --> 00:02:04,010
Skulum halda að hliðar fyrir annað,
skipta öllu yfir, og setja einn

42
00:02:04,010 --> 00:02:05,570
þar sem það ætti að fara.

43
00:02:05,570 --> 00:02:08,110
>> Aftur, enn, höfum við bara alltaf
horfði á einn, tveir og fimm.

44
00:02:08,110 --> 00:02:12,480
Við vitum ekki hvað er að koma,
en við höfum raðað þeim þremur þáttum.

45
00:02:12,480 --> 00:02:16,030
>> Næsta Óflokkaður þátturinn er
þrír, þannig að við munum setja það til hliðar.

46
00:02:16,030 --> 00:02:18,200
Við munum skipta yfir það sem við
þarf sem, í þetta sinn

47
00:02:18,200 --> 00:02:21,820
er ekki allt eins og í fyrri
tvö tilvik, það er bara fimm.

48
00:02:21,820 --> 00:02:25,440
Og þá munum við standa þrjú í,
milli tveggja og fimm.

49
00:02:25,440 --> 00:02:27,849
>> Six er næsta Óflokkaður
þáttur til fylkisins.

50
00:02:27,849 --> 00:02:31,140
Og í raun sex er meiri en fimm, svo
við gerum ekki einu sinni þurfa að gera allir swap.

51
00:02:31,140 --> 00:02:35,710
Við getum bara tittur sex rétt á að
the endir af the flokkuð hluta.

52
00:02:35,710 --> 00:02:38,270
>> Loks, fjórir er
Síðast Óflokkaður þáttur.

53
00:02:38,270 --> 00:02:42,060
Þannig að við munum setja það til hliðar, skipta yfir
þætti sem við þurfum að skipta yfir,

54
00:02:42,060 --> 00:02:43,780
og þá setja fjögur þar sem það tilheyrir.

55
00:02:43,780 --> 00:02:46,400
Og nú líta, að við höfum svona
af öllum þeim þáttum.

56
00:02:46,400 --> 00:02:48,150
Tilkynning með innsetningu
raða, höfum vér ekki

57
00:02:48,150 --> 00:02:50,240
að fara fram og til baka yfir í fylkinu.

58
00:02:50,240 --> 00:02:54,720
Við fórum aðeins yfir fjölda
einu sinni, og við færst hluti

59
00:02:54,720 --> 00:02:59,870
að við myndum nú þegar komið upp, í því skyni
til að gera pláss fyrir nýja þætti.

60
00:02:59,870 --> 00:03:02,820
>> Svo er það versta
dæmi með innsetningu tagi?

61
00:03:02,820 --> 00:03:05,090
Í versta tilfelli,
array er í öfugri röð.

62
00:03:05,090 --> 00:03:11,180
Þú verður að skipta hvert N þætti
upp á móti n stöðum, hvert einasta skipti sem við

63
00:03:11,180 --> 00:03:12,880
gera innsetningu.

64
00:03:12,880 --> 00:03:15,720
Það er mikið breytast.

65
00:03:15,720 --> 00:03:18,014
>> Í besta tilfelli,
array er fullkomlega raðað.

66
00:03:18,014 --> 00:03:20,680
Og svoleiðis eins og það sem gerðist
með fimm og sex í dæminu,

67
00:03:20,680 --> 00:03:23,779
þar sem við gátum bara tittur það á
án þess að þurfa að gera allir breytast,

68
00:03:23,779 --> 00:03:24,820
við myndum í raun gert það.

69
00:03:24,820 --> 00:03:27,560
>> Ef þú ímynda sér að okkar
array var einn til sex,

70
00:03:27,560 --> 00:03:29,900
við myndum byrja á því að
lýsa einn er flokkaður.

71
00:03:29,900 --> 00:03:33,300
Two kemur eftir einn svo við getum bara
segja, OK, vel einn og tveir eru flokkuð.

72
00:03:33,300 --> 00:03:36,190
Þrír kemur eftir tvö svo, OK,
einn og tveir og þrír eru flokkuð.

73
00:03:36,190 --> 00:03:39,590
>> Við erum ekki að gera neinar skiptasamninga, við erum
bara að færa þessa handahófskennt línu

74
00:03:39,590 --> 00:03:42,460
milli flokka og óflokkaðar sem við förum.

75
00:03:42,460 --> 00:03:46,646
Eins og í raun eins og við gerðum í dæminu,
beygja þætti blár, eins og við halda áfram.

76
00:03:46,646 --> 00:03:48,270
Svo er það versta afturkreistingur, þá?

77
00:03:48,270 --> 00:03:51,854
Mundu, ef við þurfum að skipta hvert
sem n þættir hugsanlega n stöðu,

78
00:03:51,854 --> 00:03:54,020
vonandi sem gefur þér
hugmynd sem versta

79
00:03:54,020 --> 00:03:57,770
afturkreistingur er Big O n veldi.

80
00:03:57,770 --> 00:04:00,220
>> Ef array er fullkomlega
raðað, allt sem við höfum til að gera

81
00:04:00,220 --> 00:04:04,480
er að líta á hvert einasta þáttur
einu sinni, og þá erum við að gera.

82
00:04:04,480 --> 00:04:08,440
Svo í besta tilfelli, það er ómega n.

83
00:04:08,440 --> 00:04:09,490
>> Ég er Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Þetta er CS50.

85
00:04:11,760 --> 00:04:13,119