Kuna algoriti kadhaa za msingi za kutatua tatizo la kupanga safu. Moja ya maarufu zaidi kati yao ni aina ya kuingizwa. Kutokana na uwazi wake na unyenyekevu, lakini ufanisi mdogo, njia hii hutumiwa hasa katika kufundisha programu. Inakuruhusu kuelewa mbinu msingi za kupanga.
Maelezo ya kanuni
Kiini cha algoriti ya kupanga ni kwamba sehemu iliyopangwa vizuri huundwa ndani ya safu ya awali. Kila kipengele kinalinganishwa moja kwa moja na sehemu iliyoangaliwa na kuingizwa mahali pazuri. Kwa hivyo, baada ya kurudia vipengele vyote, hujipanga kwa mpangilio sahihi.
Mpangilio wa kuchagua vipengele vinaweza kuwa vyovyote, vinaweza kuchaguliwa kiholela au kulingana na algoriti fulani. Mara nyingi, hesabu za kufuatana hutumiwa kutoka mwanzo wa safu, ambapo sehemu iliyopangwa huundwa.
Mwanzo wa kupanga unaweza kuonekana hivi:
- Chukua kipengele cha kwanza cha safu.
- Kwa kuwa hakuna kitu cha kukilinganisha nacho, chukua kipengele chenyewe jinsi ulivyoagizamlolongo.
- Nenda kwenye kipengee cha pili.
- Ilinganishe na ya kwanza kulingana na kanuni ya kupanga.
- Ikihitajika, badilisha vipengele katika maeneo.
- Chukua vipengele viwili vya kwanza kama mfuatano uliopangwa.
- Nenda kwenye kipengee cha tatu.
- Linganisha na ya pili, badilisha inapohitajika.
- Ikiwa kibadilishaji kimefanywa, linganisha na cha kwanza.
- Chukua vipengele vitatu kama mfuatano uliopangwa.
Na kadhalika hadi mwisho wa safu asili.
Aina ya uwekaji wa maisha halisi
Kwa uwazi, inafaa kutoa mfano wa jinsi utaratibu huu wa kupanga unavyotumika katika maisha ya kila siku.
Chukua, kwa mfano, pochi. Noti mia, mia tano na elfu ziko katika hali ya mchafuko katika sehemu ya noti. Hii ni fujo, katika hodgepodge vile ni vigumu kupata mara moja kipande cha karatasi sahihi. Mkusanyiko wa noti lazima zipangwa.
Ya kwanza kabisa ni noti ya rubles 1000, na mara baada yake - 100. Tunachukua mia moja na kuiweka mbele. Ya tatu mfululizo ni rubles 500, mahali panapofaa ni kati ya mia moja na elfu.
Vile vile tunapanga kadi zilizopokewa tunapocheza "Fool" ili kurahisisha kuzielekeza.
Vitendaji na vitendaji vya msaidizi
Njia ya kupanga ya uwekaji inachukua kama ingizo la safu ya awali ya kupangwa, chaguo la kukokotoa la kulinganisha, na, ikihitajika, chaguo la kukokotoa ambalo huamua kanuni ya vipengele vya kuhesabu. Mara nyingi hutumiwa badala yaketaarifa ya kawaida ya kitanzi.
Kipengele cha kwanza chenyewe ni seti iliyopangwa, kwa hivyo ulinganisho unaanza kutoka kwa pili.
Algoriti mara nyingi hutumia kitendakazi kisaidizi kubadilishana thamani mbili (kubadilishana). Inatumia kigezo cha ziada cha muda, ambacho hutumia kumbukumbu na kupunguza kasi ya msimbo kidogo.
Mbadala ni kuhamisha kikundi cha vipengee kwa wingi na kisha kuingiza cha sasa kwenye nafasi iliyo huru. Katika hali hii, mpito kwa kipengele kinachofuata hutokea wakati ulinganisho ulitoa matokeo chanya, ambayo yanaonyesha mpangilio sahihi.
Mifano ya utekelezaji
Utekelezaji mahususi kwa kiasi kikubwa unategemea lugha ya programu inayotumiwa, sintaksia yake na miundo.
Utekelezaji wa C wa kawaida kwa kutumia kigezo cha muda kubadilisha thamani:
int i, j, temp; kwa (i=1; i =0; j--) {ikiwa (safu[j] < temp) kuvunja; safu[j + 1]=safu[j]; safu[j]=joto; } }
Utekelezaji PHP:
function insertion_sort(&$a) { kwa ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Hapa, kwanza, vipengee vyote ambavyo havilingani na hali ya kupanga vinahamishwa hadi kulia, kisha kipengele cha sasa kinawekwa kwenye nafasi iliyo huru.
Msimbo wa Java ukitumia wakati kitanzi:
uwekaji utupu wa tuli wa ummaPanga(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Maana ya jumla ya msimbo bado haijabadilika: kila kipengele cha safu hulinganishwa kwa mpangilio na zile za awali na hubadilishwa navyo inapohitajika.
Kadirio la muda wa utekelezaji
Ni wazi, katika hali bora zaidi, ingizo la algoriti litakuwa ni safu ambayo tayari imepangwa kwa njia sahihi. Katika hali hii, algorithm italazimika kuangalia kila kipengele ili kuhakikisha kuwa iko mahali pazuri bila kubadilishana. Kwa hivyo, muda wa kukimbia utategemea moja kwa moja urefu wa safu asili O(n).
Ingizo la hali mbaya zaidi ni safu iliyopangwa kwa mpangilio wa kinyume. Hii itahitaji idadi kubwa ya viidhinisho, utendakazi wa wakati wa utekelezaji utategemea idadi ya vipengele vilivyowekwa mraba.
Nambari kamili ya vibali vya safu isiyopangwa kabisa inaweza kuhesabiwa kwa kutumia fomula:
n(n-1)/2
ambapo n ni urefu wa safu asili. Kwa hivyo, ingechukua vibali 4950 ili kupanga vipengele 100 kwa mpangilio sahihi.
Njia ya uwekaji ni bora sana kwa kupanga safu ndogo au zilizopangwa kwa kiasi. Hata hivyo, haipendekezwi kuitumia kila mahali kutokana na uchangamano wa juu wa hesabu.
Algoriti hutumika kama nyenzo kisaidizi katika mbinu nyingine nyingi changamano za kupanga.
Panga thamani sawa
Algoriti ya uwekaji ni ya zile zinazoitwa aina thabiti. Inamaanisha,kwamba haibadilishi vipengele vinavyofanana, lakini huhifadhi mpangilio wao wa asili. Faharasa ya uthabiti katika hali nyingi ni muhimu kwa uagizaji sahihi.
Iliyo hapo juu ni mfano mzuri wa taswira wa aina ya kuingizwa kwenye dansi.
