1
00:00:00,000 --> 00:00:02,826
>> [Muzika]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG Lloyd: Pra futje lloj është një tjetër
Algorithm ne mund të përdorim për të zgjidhur një grup.

4
00:00:09,370 --> 00:00:12,350
Ideja prapa këtij algoritmi
është për të ndërtuar rrjet të renditura

5
00:00:12,350 --> 00:00:19,670
në vend, duke i shtyrë elemente nga
mënyra si ju shkoni, që të bëjë vend.

6
00:00:19,670 --> 00:00:22,240
Kjo është pak më ndryshe
nga lloji përzgjedhjes ose flluskë

7
00:00:22,240 --> 00:00:25,460
lloj, për shembull, ku
ne jemi duke rregulluar vende,

8
00:00:25,460 --> 00:00:26,910
ku ne jemi duke bërë këmbime.

9
00:00:26,910 --> 00:00:29,760
>> Në këtë rast ajo që ne jemi në fakt
bërë është elemente rrëshqitje

10
00:00:29,760 --> 00:00:31,390
mbi, nga rruga.

11
00:00:31,390 --> 00:00:34,030
Si e bën këtë algorithm
punojnë në pseudokod?

12
00:00:34,030 --> 00:00:37,646
E pra le të vetëm në mënyrë arbitrare të them se
Elementi i parë i vargut është e renditura.

13
00:00:37,646 --> 00:00:38,770
Ne jemi duke ndërtuar atë në vend.

14
00:00:38,770 --> 00:00:42,660
>> Ne jemi gonna të shkojnë një element në një kohë dhe
ndërtuar atë, dhe kështu që gjëja e parë që ne shohim

15
00:00:42,660 --> 00:00:43,890
është një koleksion një element.

16
00:00:43,890 --> 00:00:47,720
Dhe me përkufizim, një
element array është e renditura.

17
00:00:47,720 --> 00:00:50,850
>> Pastaj ne do të përsëris këtë proces until--
ne do të përsëris procesin në vijim

18
00:00:50,850 --> 00:00:52,900
deri sa të gjitha elementet janë të renditura.

19
00:00:52,900 --> 00:00:57,770
Shikoni në elementin e ardhshëm Unsorted dhe
futur atë në pjesën e renditura,

20
00:00:57,770 --> 00:01:01,209
duke zhvendosur numrin e kërkuar
e elementeve nga rruga.

21
00:01:01,209 --> 00:01:03,750
Shpresojmë se kjo vizualizimi
do t'ju ndihmojë të shihni saktësisht se çfarë është

22
00:01:03,750 --> 00:01:05,980
ndodh me futje lloji.

23
00:01:05,980 --> 00:01:08,010
>> Pra, përsëri, këtu është tonë
Gjithë grup Unsorted,

24
00:01:08,010 --> 00:01:10,970
të gjithë elementet tregohet në të kuqe.

25
00:01:10,970 --> 00:01:13,320
Dhe le të ndjekim
Hapat e pseudokod sonë.

26
00:01:13,320 --> 00:01:16,970
Gjëja e parë që ne bëjmë, është që ne e quajmë
Elementi i parë i vargut, të renditura.

27
00:01:16,970 --> 00:01:20,920
Pra, ne jemi vetëm gonna të themi
pesë, ju jeni të renditura tani.

28
00:01:20,920 --> 00:01:24,570
>> Atëherë ne shikojmë në të ardhshëm
element unsorted e vektorit

29
00:01:24,570 --> 00:01:27,610
dhe ne duam të futur që
në pjesën e renditura,

30
00:01:27,610 --> 00:01:29,750
duke zhvendosur mbi elemente.

31
00:01:29,750 --> 00:01:33,470
Pra dy është tjetër Unsorted
element i vektorit.

32
00:01:33,470 --> 00:01:36,250
Është e qartë se kjo i takon para se të
pesë, kështu që ajo që ne jemi gonna të bëjmë

33
00:01:36,250 --> 00:01:41,580
është lloj i mbajë dy mënjanë për një të dytë,
zhvendoset pesë mbi, dhe pastaj futur dy

34
00:01:41,580 --> 00:01:43,210
para pesë, ku të duhet të shkoni.

35
00:01:43,210 --> 00:01:45,280
Dhe tani ne mund të themi se dy është e renditura.

36
00:01:45,280 --> 00:01:48,400
>> Kështu si ju mund të shihni, ne kemi vetëm deri më tani
shikuar në dy elemente të vektorit.

37
00:01:48,400 --> 00:01:50,600
Ne nuk kemi shikuar në nivel
pushoni në të gjitha, por ne kemi

38
00:01:50,600 --> 00:01:54,582
mori këto dy elemente të renditura nga
Mënyra e mekanizmit zhvendosur.

39
00:01:54,582 --> 00:01:56,410
>> Pra, ne përsëris procesin përsëri.

40
00:01:56,410 --> 00:01:58,850
Shikoni në tjetër Unsorted
element, kjo është një.

41
00:01:58,850 --> 00:02:04,010
Le të thonë se mënjanë për një të dytë,
zhvendoset gjithçka mbi, dhe të vënë një

42
00:02:04,010 --> 00:02:05,570
ku duhet të shkoni.

43
00:02:05,570 --> 00:02:08,110
>> Përsëri, ende, ne kemi vetëm ndonjëherë
shikuar në një, dy dhe pesë.

44
00:02:08,110 --> 00:02:12,480
Ne nuk e dimë se çfarë tjetër po vjen,
por ne kemi renditur këto tre elemente.

45
00:02:12,480 --> 00:02:16,030
>> Elementi tjetër është unsorted
tre, kështu që ne do të vënë atë mënjanë.

46
00:02:16,030 --> 00:02:18,200
Ne do të zhvendoset mbi atë që ne
nevojë për të cilën, kësaj radhe

47
00:02:18,200 --> 00:02:21,820
nuk është gjithçka si në mëparshme
dy raste, kjo është vetëm pesë.

48
00:02:21,820 --> 00:02:25,440
Dhe pastaj ne do të rrinë tre në,
në mes të dy dhe pesë.

49
00:02:25,440 --> 00:02:27,849
>> Gjashtë është tjetër Unsorted
element të vektorit.

50
00:02:27,849 --> 00:02:31,140
Dhe në faktin gjashtë është më e madhe se pese, kështu
ne as nuk duhet të bëjë ndonjë shkëmbejnë.

51
00:02:31,140 --> 00:02:35,710
Ne vetëm mund të litar gjashtë drejtë në të
fundi i pjesës renditura.

52
00:02:35,710 --> 00:02:38,270
>> Së fundi, katër është
Elementi i fundit unsorted.

53
00:02:38,270 --> 00:02:42,060
Pra, ne do të vënë atë mënjanë, ndryshim mbi
elementet ne duhet të zhvendoset mbi,

54
00:02:42,060 --> 00:02:43,780
dhe pastaj të vënë katër ku i takon.

55
00:02:43,780 --> 00:02:46,400
Dhe tani shikoni, ne kemi lloj
të gjithë elementeve.

56
00:02:46,400 --> 00:02:48,150
Vini re me futje
lloj, ne nuk kemi

57
00:02:48,150 --> 00:02:50,240
për të shkuar mbrapa dhe me radhë nëpër rrjet.

58
00:02:50,240 --> 00:02:54,720
Ne vetëm shkoi nëpër rrjet
një herë, dhe ne u zhvendos gjëra

59
00:02:54,720 --> 00:02:59,870
se ne do hasur tashmë, në mënyrë
për të bërë vend për elemente të reja.

60
00:02:59,870 --> 00:03:02,820
>> Pra, çfarë është rasti më i keq
Skenari me futje lloj?

61
00:03:02,820 --> 00:03:05,090
Në rastin më të keq,
array është në mënyrë të kundërt.

62
00:03:05,090 --> 00:03:11,180
Ju duhet të zhvendoset secilin prej elementeve n
deri në pozicione n, çdo herë kemi të vetme

63
00:03:11,180 --> 00:03:12,880
të bëjë një futje.

64
00:03:12,880 --> 00:03:15,720
Kjo është një shumë të zhvendosur.

65
00:03:15,720 --> 00:03:18,014
>> Në rastin më të mirë, The
grup është renditur në mënyrë të përkryer.

66
00:03:18,014 --> 00:03:20,680
Dhe lloj si ajo që ka ndodhur
me pesë dhe gjashtë në shembull,

67
00:03:20,680 --> 00:03:23,779
ku ne mund vetëm litar atë në
pa pasur nevojë të bëni ndonjë zhvendosur,

68
00:03:23,779 --> 00:03:24,820
ne do të bëjmë që në thelb.

69
00:03:24,820 --> 00:03:27,560
>> Nëse ju imagjinoni se tonë
array ishte një me gjashtë,

70
00:03:27,560 --> 00:03:29,900
ne do të nisem nga
deklaruar një të tillë është e renditura.

71
00:03:29,900 --> 00:03:33,300
Dy vjen pas një kështu që ne mund vetëm
them, OK, mirë një dhe dy janë të renditura.

72
00:03:33,300 --> 00:03:36,190
Tre vjen pas dy kështu, OK,
një dhe dy dhe tre janë të renditura.

73
00:03:36,190 --> 00:03:39,590
>> Ne nuk jemi duke bërë ndonjë këmbime, ne jemi
vetëm duke lëvizur këtë linjë arbitrare

74
00:03:39,590 --> 00:03:42,460
në mes të renditura dhe Unsorted si të shkojmë.

75
00:03:42,460 --> 00:03:46,646
Si në mënyrë efektive si ne e bëmë në shembull,
kthyer elemente blu, si ne të vazhdojë.

76
00:03:46,646 --> 00:03:48,270
Pra, çfarë është rast Runtime të keq, atëherë?

77
00:03:48,270 --> 00:03:51,854
Mos harroni, në qoftë se ne duhet të zhvendoset secilit prej
elementet n ndoshta pozicionet n,

78
00:03:51,854 --> 00:03:54,020
shpresojmë që ju jep
një ide se rasti më i keq

79
00:03:54,020 --> 00:03:57,770
Runtime është Big O i n katror.

80
00:03:57,770 --> 00:04:00,220
>> Nëse array është krejtësisht
të renditura, të gjithë ne duhet të bëjmë

81
00:04:00,220 --> 00:04:04,480
është të shikoni në çdo element të vetme
herë, dhe pastaj ne jemi duke bërë.

82
00:04:04,480 --> 00:04:08,440
Pra, në rastin më të mirë, është e omega e n.

83
00:04:08,440 --> 00:04:09,490
>> Unë jam Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Kjo është CS50.

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