[Music kucheza] 

DOUG LLOYD: Kwa hiyo kuingizwa aina ni mwingine algorithm tunaweza kutumia aina safu. Dhana ya algorithm hii ni kujenga safu yako Iliyopangwa katika mahali, kuhama mambo ya nje ya njia kama wewe kwenda, kufanya chumba. Hii ni tofauti kidogo kutoka uteuzi aina au Bubble aina, kwa mfano, ambapo sisi ni kurekebisha maeneo, ambapo sisi ni kufanya swaps. 

Katika kesi hiyo ni nini tuko kweli kufanya ni sliding mambo juu, nje ya njia. Ni kwa jinsi gani hii algorithm kazi katika pseudocode? Naam hebu tu kiholela kusema kwamba sehemu ya kwanza ya safu ni Iliyopangwa. Sisi ni kujenga katika nafasi. 

Sisi ni gonna kwenda kipengele moja kwa wakati mmoja na kujenga, na hivyo jambo la kwanza tunaona ni moja ya kipengele safu. Na kwa ufafanuzi, moja kipengele safu ni Iliyopangwa. 

Kisha tutaweza kurudia utaratibu huu until-- tutaweza kurudia utaratibu zifuatazo mpaka wote wa mambo ni vyema. Angalia ijayo zisizochambuliwa kipengele na kuingiza ndani ya fungu yamepangwa, na kuhama idadi required ya mambo ya nje ya njia. Hopefully taswira hii kukusaidia kuona hasa nini kinachoendelea na kuingizwa aina. 

Hivyo tena, hapa ni wetu nzima zisizochambuliwa safu, wote wa mambo unahitajika katika nyekundu. Na hebu kufuata hatua ya pseudocode yetu. Jambo la kwanza sisi kufanya, ni tunatoa wito sehemu ya kwanza ya safu, yamepangwa. Hivyo sisi ni gonna kusema tu tano, wewe ni sasa yamepangwa. 

Kisha sisi kuangalia ijayo zisizochambuliwa kipengele cha safu na tunataka Insert kwamba ndani ya fungu yamepangwa, na kuhama mambo juu. Hivyo mbili ni karibu zisizochambuliwa kipengele cha safu. Ni wazi ni mali kabla tano, hivyo nini sisi ni gonna kufanya ni aina ya kushikilia mbili kando kwa ajili ya pili, kuhama tano juu, na kisha kuingiza mbili kabla tano, ambapo anatakiwa kwenda. Na sasa tunaweza kusema kwamba wawili ni Iliyopangwa. 

Hivyo kama unaweza kuona, tumekuwa tu hadi sasa inaonekana katika mambo mawili ya safu. Sisi si inaonekana katika kupumzika hata kidogo, lakini tumekuwa got mambo hayo mawili yamepangwa kwa njia ya utaratibu shifting. 

Kwa hiyo sisi kurudia utaratibu tena. Angalia zisizochambuliwa ijayo kipengele, hiyo ni moja. Hebu kushikilia kuwa mbali kwa ajili ya pili, kuhama kila kitu juu, na kuweka moja ambapo ni lazima kwenda. 

Tena, bado, tumekuwa milele tu inaonekana katika moja, mbili, na tano. Hatujui kile kingine anakuja, lakini tumekuwa yamepangwa mambo hayo matatu. 

Ijayo zisizochambuliwa kipengele ni tatu, hivyo tutaweza kuweka kando. Tutaweza kuhama juu ya nini sisi haja ya ambayo, wakati huu sio kila kitu kama katika uliopita kesi mbili, ni tu tano. Na kisha tutaweza fimbo tatu katika, kati ya mbili na tano. 

Sita ni ijayo zisizochambuliwa kipengele kwa safu. Na kwa kweli sita ni mkubwa kuliko tano, hivyo hatuna hata haja ya kufanya swapping yoyote. Tunaweza tu upepo sita haki juu ya Mwishoni mwa sehemu yamepangwa. 

Mwisho, ni wanne mwisho zisizochambuliwa kipengele. Hivyo tutaweza kuweka kando, kuhama juu ya mambo tunahitaji kuhama juu, na kisha kuweka nne ambapo ni mali. Na sasa tuangalie, tumekuwa aina ya mambo yote. Taarifa na kuingizwa aina, hatukuwa na kwenda na kurudi katika safu. Sisi tu alikwenda katika safu wakati mmoja, na sisi kubadilishwa mambo kwamba tunatarajia tayari yaliyojitokeza, ili kufanya chumba kwa ajili ya mambo mapya. 

Basi nini hali mbaya mazingira na kuingizwa aina? Katika hali mbaya zaidi, safu ni ili reverse. Una kuhama kila moja ya mambo n hadi nafasi n, kila moja wakati sisi kufanya insertion. Kwamba mengi ya kuhama. 

Katika kesi bora, safu kikamilifu yamepangwa. Na aina ya kama nini kilichotokea na tano na sita katika mfano, ambapo tunaweza tu upepo ni juu ya bila ya kuwa na kufanya shifting wowote, tunatarajia kimsingi kufanya hivyo. 

Kama unafikiri kwamba yetu safu alikuwa mmoja kupitia sita, tunatarajia kuanza kwa kutangaza moja ni Iliyopangwa. Mbili inakuja baada moja ili tuweze tu kusema, OK, vizuri moja na mbili ni vyema. Tatu inakuja baada ya wawili hivyo, sawa, moja na mbili na tatu ni vyema. 

Sisi siyo kufanya swaps yoyote, tuko tu kusonga mstari huu holela kati ya yamepangwa na zisizochambuliwa kama sisi kwenda. Vizuri kama tulivyofanya katika mfano, kugeuka mambo bluu, kama sisi kuendelea. Basi nini kesi mbaya Runtime, basi? Kumbuka, kama tuna kuhama kila mmoja n vipengele uwezekano vyeo n, hopefully kwamba anatoa wazo kwamba hali mbaya Runtime ni Big O ya n squared. 

Kama safu ni kikamilifu yamepangwa, kila tuna kufanya ni kuangalia kila kipengele moja mara moja, na kisha sisi ni kosa. Hivyo katika kesi bora, ni omega ya n. 

Mimi nina Doug Lloyd. Hii ni CS50.