InsertionSort është një algoritëm shumë popullor dhe i lehtë për t'u mësuar. Në këtë artikull do të mësoni rreth veçorive të InsertionSort dhe si të zbatoni algoritmin e renditjes në gjuhë të ndryshme programimi. Unë do t'ju shpjegoj kodin dhe shumë më tepër.

Kënaqu duke lexuar!

Prezantimi

Për t'ju shpjeguar InsertionSort në një mënyrë bazë, ne do të përdorim një shembull karte. Le të imagjinojmë një kuvertë letrash, ku letrat kanë numra nga 1 deri në 10. Tani duam të renditim kuvertën e përzier të letrave me ndihmën e InsertionSort.

Në njërën dorë kemi letrat tashmë të renditura dhe në anën tjetër kemi kuvertën e pazgjedhur. Ne e konsiderojmë kartën e parë të kuvertës së pazgjedhur si të renditur, do ta shihni pse së shpejti.

Pasi ta bëjmë këtë, ne marrim kartën tjetër të kuvertës së pazgjidhur dhe e vendosim në vendin e duhur në kuvertën e renditur. Ne e përsërisim këtë, derisa kuverta jonë e pazgjidhur të jetë bosh.

Vetitë

Le të fillojmë me një pronë shumë të lehtë. InsertionSort është një algoritëm klasifikimi që është i qëndrueshëm. Kjo do të thotë që nëse një grup ka dy numra që janë të njëjtë, renditja e dy numrave në raport me njëri-tjetrin mbetet e njëjtë në një algoritëm të qëndrueshëm. Në një algoritëm të paqëndrueshëm, kjo nuk është gjithmonë rasti.

Një tjetër veçori shumë e thjeshtë për t'u kuptuar është ekzekutimi në vend. Kjo do të thotë, se sado i madh të jetë grupi, nuk kemi nevojë për variabla shtesë. E thënë thjesht: Hapësira shtesë në memorie e nevojshme nuk varet nga sa i madh është grupi. InsertionSort është një algoritëm në vend. Vetia e kundërt ka MergeSort, nuk është një algoritëm në vend. Mund të mësoni më shumë rreth tij "këtu".

Le të diskutojmë kompleksitetin e kohës, dhe këtu bëhet pak më e ndërlikuar. Për shkak se unë dua të krijoj një artikull, që është shumë miqësor për fillestarët, nuk do të shpjegoj se si llogaritet kompleksiteti kohor, por sigurisht do t'ju tregoj se cili është kompleksiteti kohor i InsertionSort dhe çfarë do të thotë kjo. Nëse dëshironi të dini më shumë rreth matematikës pas kompleksitetit kohor të InsertionSort, kam gjetur një artikull të mrekullueshëm që e shpjegon atë "këtu".

Rasti më i mirë i InsertionSort është O(n). Kjo do të thotë se koha e nevojshme rritet lineare me numrin e elementeve në grup (ne e quajmë këtë n).

Kompleksiteti mesatar i rastit dhe i rastit më të keq është i njëjtë, është O(n²). Kjo do të thotë se koha e nevojshme rritet në mënyrë eksponenciale në lidhje me elementët në grup (n).

Efikasiteti në krahasim me algoritmet e tjera të renditjes

InsertionSort është një lloj algoritmi i ngadaltë. Por krahasuar me BubbleSort (rasti më i mirë: O(n), mesatarja dhe rasti më i keq O(n²)). Por tani po pyesni veten, pse BubbleSort është më i ngadalshëm, nëse ka të njëjtin kompleksitet kohor? Epo, sepse në O-Notation, ne nuk shikojmë faktorin që qëndron përpara n. Ne tani do të faktorizonim nëse do të kishim bërë llogaritjet.

Tani ndoshta po mendoni, auau, kjo është mirë, InsertionSort është shumë i shpejtë. Jo, është ende një algoritëm i ngadaltë në krahasim me algoritmet e renditjes si MergeSort. MergeSort ka një kompleksitet kohor prej O(n log n) dhe është shumë më i shpejtë se InsertionSort.

Zbatimi i InsertionSort

Tani duam të implementojmë InsertionSort në gjuhë të ndryshme programimi. Fillimisht do të shpjegoj konceptin e përgjithshëm se si do ta bëjmë këtë dhe më pas do t'ju tregoj një zbatim në python dhe një zbatim në dart. Do të shtoj gjithashtu disa lidhje për gjuhë të tjera programimi si JavaScript.

Gjithashtu zbatoni InsertionSort në një gjuhë programimi, ju përsërisni nëpër grup me një lak. Në një ndërveprim ju krahasoni elementin aktual me atë të mëparshëm. Kur ai i mëparshmi është më i madh se elementi aktual që po shikojmë, të dy elementët do të ndërrohen. Kjo do të përsëritet derisa elementi aktual të jetë në vendin e duhur. Pra, mund të themi, se elementi aktual ecën poshtë grupit tashmë të renditur derisa të jetë në vendin e duhur. Kjo zbatohet gjithashtu në një cikli, që numëron mbrapsht nga pozicioni origjinal në një dhe ndalon, nëse nuk është bërë shkëmbim.

Është e rëndësishme të përmendet se me çdo përsëritje, zona e renditur bëhet më e madhe me një element dhe zona e pazgjedhur zvogëlohet me një element.

Tani do të shikojmë implementimet. Zbatimin e parë e kam shkruar gjatë në një "punim kërkimor" gjatë klasës së 9-të dhe të dytin e kam shkruar për argëtim :).

Implementimi i Python:

Zbatimi i shigjetës:

Nëse keni nevojë për zbatime për gjuhë të tjera, mund të gjeni disa këtu (C++, C, Java, C#, PHP, Javascript)..,

konkluzioni

Në këtë postim ne kemi parë se si funksionon InsertionSort dhe si mund të zbatoni algoritmin e renditjes në Dart & Python.

Shpresoj se keni qenë në gjendje të mësoni diçka dhe të keni shijuar! Nëse po, do të isha shumë i lumtur nëse i jepni këtij postimi disa duartrokitje.

Oh, dhe para se të harroj ta përmend: do të prezantoj disa algoritme të tjera renditjeje në Dart dhe gjuhë të tjera në të ardhmen e afërt. Nëse nuk doni ta humbisni atë, duhet patjetër më ndiqni!

Kalofshi një ditë të mbarë dhe faleminderit shumë që lexuat!