1
00:00:00,000 --> 00:00:02,826
>> [Music kucheza]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Kwa hiyo kuingizwa aina ni mwingine
algorithm tunaweza kutumia aina safu.

4
00:00:09,370 --> 00:00:12,350
Dhana ya algorithm hii
ni kujenga safu yako Iliyopangwa

5
00:00:12,350 --> 00:00:19,670
katika mahali, kuhama mambo ya nje ya
njia kama wewe kwenda, kufanya chumba.

6
00:00:19,670 --> 00:00:22,240
Hii ni tofauti kidogo
kutoka uteuzi aina au Bubble

7
00:00:22,240 --> 00:00:25,460
aina, kwa mfano, ambapo
sisi ni kurekebisha maeneo,

8
00:00:25,460 --> 00:00:26,910
ambapo sisi ni kufanya swaps.

9
00:00:26,910 --> 00:00:29,760
>> Katika kesi hiyo ni nini tuko kweli
kufanya ni sliding mambo

10
00:00:29,760 --> 00:00:31,390
juu, nje ya njia.

11
00:00:31,390 --> 00:00:34,030
Ni kwa jinsi gani hii algorithm
kazi katika pseudocode?

12
00:00:34,030 --> 00:00:37,646
Naam hebu tu kiholela kusema kwamba
sehemu ya kwanza ya safu ni Iliyopangwa.

13
00:00:37,646 --> 00:00:38,770
Sisi ni kujenga katika nafasi.

14
00:00:38,770 --> 00:00:42,660
>> Sisi ni gonna kwenda kipengele moja kwa wakati mmoja na
kujenga, na hivyo jambo la kwanza tunaona

15
00:00:42,660 --> 00:00:43,890
ni moja ya kipengele safu.

16
00:00:43,890 --> 00:00:47,720
Na kwa ufafanuzi, moja
kipengele safu ni Iliyopangwa.

17
00:00:47,720 --> 00:00:50,850
>> Kisha tutaweza kurudia utaratibu huu until--
tutaweza kurudia utaratibu zifuatazo

18
00:00:50,850 --> 00:00:52,900
mpaka wote wa mambo ni vyema.

19
00:00:52,900 --> 00:00:57,770
Angalia ijayo zisizochambuliwa kipengele na
kuingiza ndani ya fungu yamepangwa,

20
00:00:57,770 --> 00:01:01,209
na kuhama idadi required
ya mambo ya nje ya njia.

21
00:01:01,209 --> 00:01:03,750
Hopefully taswira hii
kukusaidia kuona hasa nini

22
00:01:03,750 --> 00:01:05,980
kinachoendelea na kuingizwa aina.

23
00:01:05,980 --> 00:01:08,010
>> Hivyo tena, hapa ni wetu
nzima zisizochambuliwa safu,

24
00:01:08,010 --> 00:01:10,970
wote wa mambo unahitajika katika nyekundu.

25
00:01:10,970 --> 00:01:13,320
Na hebu kufuata
hatua ya pseudocode yetu.

26
00:01:13,320 --> 00:01:16,970
Jambo la kwanza sisi kufanya, ni tunatoa wito
sehemu ya kwanza ya safu, yamepangwa.

27
00:01:16,970 --> 00:01:20,920
Hivyo sisi ni gonna kusema tu
tano, wewe ni sasa yamepangwa.

28
00:01:20,920 --> 00:01:24,570
>> Kisha sisi kuangalia ijayo
zisizochambuliwa kipengele cha safu

29
00:01:24,570 --> 00:01:27,610
na tunataka Insert kwamba
ndani ya fungu yamepangwa,

30
00:01:27,610 --> 00:01:29,750
na kuhama mambo juu.

31
00:01:29,750 --> 00:01:33,470
Hivyo mbili ni karibu zisizochambuliwa
kipengele cha safu.

32
00:01:33,470 --> 00:01:36,250
Ni wazi ni mali kabla
tano, hivyo nini sisi ni gonna kufanya

33
00:01:36,250 --> 00:01:41,580
ni aina ya kushikilia mbili kando kwa ajili ya pili,
kuhama tano juu, na kisha kuingiza mbili

34
00:01:41,580 --> 00:01:43,210
kabla tano, ambapo anatakiwa kwenda.

35
00:01:43,210 --> 00:01:45,280
Na sasa tunaweza kusema kwamba wawili ni Iliyopangwa.

36
00:01:45,280 --> 00:01:48,400
>> Hivyo kama unaweza kuona, tumekuwa tu hadi sasa
inaonekana katika mambo mawili ya safu.

37
00:01:48,400 --> 00:01:50,600
Sisi si inaonekana katika
kupumzika hata kidogo, lakini tumekuwa

38
00:01:50,600 --> 00:01:54,582
got mambo hayo mawili yamepangwa kwa
njia ya utaratibu shifting.

39
00:01:54,582 --> 00:01:56,410
>> Kwa hiyo sisi kurudia utaratibu tena.

40
00:01:56,410 --> 00:01:58,850
Angalia zisizochambuliwa ijayo
kipengele, hiyo ni moja.

41
00:01:58,850 --> 00:02:04,010
Hebu kushikilia kuwa mbali kwa ajili ya pili,
kuhama kila kitu juu, na kuweka moja

42
00:02:04,010 --> 00:02:05,570
ambapo ni lazima kwenda.

43
00:02:05,570 --> 00:02:08,110
>> Tena, bado, tumekuwa milele tu
inaonekana katika moja, mbili, na tano.

44
00:02:08,110 --> 00:02:12,480
Hatujui kile kingine anakuja,
lakini tumekuwa yamepangwa mambo hayo matatu.

45
00:02:12,480 --> 00:02:16,030
>> Ijayo zisizochambuliwa kipengele ni
tatu, hivyo tutaweza kuweka kando.

46
00:02:16,030 --> 00:02:18,200
Tutaweza kuhama juu ya nini sisi
haja ya ambayo, wakati huu

47
00:02:18,200 --> 00:02:21,820
sio kila kitu kama katika uliopita
kesi mbili, ni tu tano.

48
00:02:21,820 --> 00:02:25,440
Na kisha tutaweza fimbo tatu katika,
kati ya mbili na tano.

49
00:02:25,440 --> 00:02:27,849
>> Sita ni ijayo zisizochambuliwa
kipengele kwa safu.

50
00:02:27,849 --> 00:02:31,140
Na kwa kweli sita ni mkubwa kuliko tano, hivyo
hatuna hata haja ya kufanya swapping yoyote.

51
00:02:31,140 --> 00:02:35,710
Tunaweza tu upepo sita haki juu ya
Mwishoni mwa sehemu yamepangwa.

52
00:02:35,710 --> 00:02:38,270
>> Mwisho, ni wanne
mwisho zisizochambuliwa kipengele.

53
00:02:38,270 --> 00:02:42,060
Hivyo tutaweza kuweka kando, kuhama juu ya
mambo tunahitaji kuhama juu,

54
00:02:42,060 --> 00:02:43,780
na kisha kuweka nne ambapo ni mali.

55
00:02:43,780 --> 00:02:46,400
Na sasa tuangalie, tumekuwa aina
ya mambo yote.

56
00:02:46,400 --> 00:02:48,150
Taarifa na kuingizwa
aina, hatukuwa na

57
00:02:48,150 --> 00:02:50,240
kwenda na kurudi katika safu.

58
00:02:50,240 --> 00:02:54,720
Sisi tu alikwenda katika safu
wakati mmoja, na sisi kubadilishwa mambo

59
00:02:54,720 --> 00:02:59,870
kwamba tunatarajia tayari yaliyojitokeza, ili
kufanya chumba kwa ajili ya mambo mapya.

60
00:02:59,870 --> 00:03:02,820
>> Basi nini hali mbaya
mazingira na kuingizwa aina?

61
00:03:02,820 --> 00:03:05,090
Katika hali mbaya zaidi,
safu ni ili reverse.

62
00:03:05,090 --> 00:03:11,180
Una kuhama kila moja ya mambo n
hadi nafasi n, kila moja wakati sisi

63
00:03:11,180 --> 00:03:12,880
kufanya insertion.

64
00:03:12,880 --> 00:03:15,720
Kwamba mengi ya kuhama.

65
00:03:15,720 --> 00:03:18,014
>> Katika kesi bora,
safu kikamilifu yamepangwa.

66
00:03:18,014 --> 00:03:20,680
Na aina ya kama nini kilichotokea
na tano na sita katika mfano,

67
00:03:20,680 --> 00:03:23,779
ambapo tunaweza tu upepo ni juu ya
bila ya kuwa na kufanya shifting wowote,

68
00:03:23,779 --> 00:03:24,820
tunatarajia kimsingi kufanya hivyo.

69
00:03:24,820 --> 00:03:27,560
>> Kama unafikiri kwamba yetu
safu alikuwa mmoja kupitia sita,

70
00:03:27,560 --> 00:03:29,900
tunatarajia kuanza kwa
kutangaza moja ni Iliyopangwa.

71
00:03:29,900 --> 00:03:33,300
Mbili inakuja baada moja ili tuweze tu
kusema, OK, vizuri moja na mbili ni vyema.

72
00:03:33,300 --> 00:03:36,190
Tatu inakuja baada ya wawili hivyo, sawa,
moja na mbili na tatu ni vyema.

73
00:03:36,190 --> 00:03:39,590
>> Sisi siyo kufanya swaps yoyote, tuko
tu kusonga mstari huu holela

74
00:03:39,590 --> 00:03:42,460
kati ya yamepangwa na zisizochambuliwa kama sisi kwenda.

75
00:03:42,460 --> 00:03:46,646
Vizuri kama tulivyofanya katika mfano,
kugeuka mambo bluu, kama sisi kuendelea.

76
00:03:46,646 --> 00:03:48,270
Basi nini kesi mbaya Runtime, basi?

77
00:03:48,270 --> 00:03:51,854
Kumbuka, kama tuna kuhama kila mmoja
n vipengele uwezekano vyeo n,

78
00:03:51,854 --> 00:03:54,020
hopefully kwamba anatoa
wazo kwamba hali mbaya

79
00:03:54,020 --> 00:03:57,770
Runtime ni Big O ya n squared.

80
00:03:57,770 --> 00:04:00,220
>> Kama safu ni kikamilifu
yamepangwa, kila tuna kufanya

81
00:04:00,220 --> 00:04:04,480
ni kuangalia kila kipengele moja
mara moja, na kisha sisi ni kosa.

82
00:04:04,480 --> 00:04:08,440
Hivyo katika kesi bora, ni omega ya n.

83
00:04:08,440 --> 00:04:09,490
>> Mimi nina Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Hii ni CS50.

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