Lisäyslajittelualgoritmi C:llä, C++, Java, Python Esimerkit

Mikä on lisäyslajittelu?

Lisäyslajittelu on yksi vertailulajittelualgoritmeista, joita käytetään elementtien lajittelemiseen iteroimalla yksi elementti kerrallaan ja sijoittamalla elementti oikeaan paikkaan jo järjestetyssä alueessa.

Jokainen alkio lisätään peräkkäin jo lajiteltuun listaan. Jo lajitellun listan koko on aluksi yksi. Lisäyslajittelualgoritmi varmistaa, että ensimmäiset k alkiota lajitellaan ulomman silmukan k:nnen iteraation jälkeen.

Koska lisäyslajittelu rakentaa tuloksen inkrementaalisesti, se on intuitiivinen opettaa, helppo debugata ja vahva perusta hyvin pienille syötteille, joihin monimutkaisemmat algoritmit lisäisivät työmäärää ilman mitattavia hyötyjä.

Lisäyslajittelualgoritmin ominaisuudet

Lisäyslajittelun algoritmilla on seuraavat tärkeät ominaisuudet, jotka selittävät sen käyttäytymistä todellisissa työkuormissa:

• Se on vakaa lajittelutekniikka, joten se ei muuta yhtäläisten elementtien suhteellista järjestystä.
• Se on tehokas pienemmille tietojoukoille, mutta ei suuremmille listoille, joissa neliöllinen kasvu on vallitsevaa.
• Lisäyslajittelu on mukautuva, mikä vähentää vaiheiden kokonaismäärää, jos syöte on osittain lajiteltu. Ryhmä on syötteenä sen tehokkuuden takaamiseksi, koska satunnaiskäyttö mahdollistaa vakioaikaiset siirtymät sisemmän silmukan aikana.
• Se on paikallisesti toimiva algoritmi, joten se ei vaadi syötteen kokoon suhteutettua lisämuistia.

Nämä ominaisuudet mielessä pitäen seuraavassa osiossa selitetään algoritmin jokaista läpikulkua ohjaava ydinlisäysoperaatio.

Miten Insert Operatyöhön?

Lisäyslajittelualgoritmissa lisäysoperaatiota käytetään lajittelemattomien elementtien lajitteluun. Se auttaa lisäämään uuden elementin jo lajiteltuun luetteloon säilyttäen samalla lajitellun alueen olemassa olevan järjestyksen.

Lisäysoperaation pseudokoodi:

Tarkastellaan N elementin listaa A.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

Yllä olevassa esimerkissä uusi elementti 6 lisätään jo lajiteltuun listaan. Seuraavat vaiheet trace sisemmän silmukan, kun uusi elementti siirtyy vasemmalle kohti oikeaa sijaintiaan.

Vaihe 1) Verrattuna A[5]:n vasempaan viereiseen elementtiin 9 > 6, vaihdamme 9:n ja 6:n paikkaa. Nyt elementti 6 on siirretty kohtaan A[4].

Vaihe 2) Nyt vertaamme A[4]:ää ja A[3]:aa, ja huomaamme, että A[3] > A[4], joten vaihdamme jälleen lukujen 6 ja 8 paikat.

Vaihe 3) Vertaa nyt lukuja A[3] ja A[2]. Koska A[2] > A[3], vaihdamme lukujen 7 ja 6 paikat keskenään.

Vaihe 4) Vertaamme lukuja A[1] ja A[2]. Koska A[1] < A[2], vasemmalla oleva viereinen alkio ei ole enää suurempi. Päädymme siihen, että luku 6 on lisätty oikein, ja lopetamme sisemmän silmukan tähän.

Kuinka lisäyslajittelu toimii

Yllä käsitelty lisäysoperaatio on lisäyslajittelun selkäranka. Lisäysproseduuri suoritetaan jokaiselle elementille, ja lopulta saamme lajitellun listan lajitellun alueen kasvaessa yhdellä elementillä jokaisella ulommalla kierroksella.

Yllä oleva kuva havainnollistaa lisäyslajittelun toimintaa tietorakenteessa. Aluksi lajitellussa alilistassa on vain yksi alkio, eli 4. Kun A[1] on lisätty, eli 3, lajitellun alilistan koko kasvaa 2:een, ja algoritmi jatkaa tätä kaavaa, kunnes kaikki alkiot on sijoitettu.

Kun käsitteellinen kulku on valmis, seuraavat osiot esittelevät konkreettisia toteutuksia C++, C ja Python joten voit vertailla silmukkarakenteita eri kielillä.

C++ Ohjelma lisäyslajitteluun

C++ Alla olevassa toteutuksessa käytetään kahta sisäkkäistä silmukkaa: ulompi silmukka valitsee seuraavan lajittelemattoman elementin ja sisempi silmukka siirtää sitä vasemmalle, kunnes oikea sijainti löytyy.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

lähtö:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code lisäyslajittelua varten

Sama logiikka pätee suoraan C-kieleen. Standardi printf kutsut korvaavat virran tulosteen, mutta sisemmän silmukan sisällä oleva vaihtokuvio on identtinen C++ versio.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

lähtö:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Ohjelma lisäyslajitteluun

Python tukee tuple swapiaping yhdessä lausekkeessa, joten sisempi silmukka on kompaktimpi kuin sen C ja C++ vastineita säilyttäen samalla saman algoritmisen käyttäytymisen.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

lähtö:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Lisäyslajittelun ominaisuudet

Tässä on lisäyslajittelun tärkeitä ominaisuuksia, jotka auttavat sinua päättämään, milloin se on oikea työkalu:

• Online: Lisäyslajittelu voi lajitella elementtejä sitä mukaa, kun se vastaanottaa ne. Jos olemme jo lajitelleet elementtiluettelon ja lisäämme siihen lisää elementtejä, meidän ei tarvitse suorittaa koko lajitteluprosessia uudelleen. Sen sijaan iteroimme vain äskettäin lisätyt elementit.
• Paikallaan: Lisäyslajittelualgoritmin tilakompleksisuus on vakio eikä vaadi lisätilaa. Tämä algoritmi lajittelee elementit paikoilleen.
• Vakaa: Lisäyslajittelussa elementtejä ei vaihdeta, jos niiden arvot ovat samat. Esimerkiksi jos kaksi elementtiä, x ja y, ovat samat ja x esiintyy lajittelemattomassa listassa ennen y:tä, niin lajitellussa listassa x esiintyy edelleen ennen y:tä. Tämä tekee lisäyslajittelusta vakaan.
• Mukautuva: A lajittelualgoritmi on adaptiivinen, jos se vie vähemmän aikaa, kun syöttöalkiot tai osa alkioista on jo lajiteltu. Kuten edellä käsiteltiin, lisäyslajittelun paras suoritusaika on O(N) ja huonoin suoritusaika on O(N^2). Lisäyslajittelu on yksi adaptiivisista lajittelualgoritmeista.

Lisäyslajittelun monimutkaisuus

Alla oleva monimutkaisuuskeskustelu kattaa sekä muistin käytön että suoritusajan, joten voit asettaa lisäyslajittelun vaihtoehtoja vastaan, kuten Bubble Lajittele ja Nopea lajittelu.

Avaruuden monimutkaisuus

Lisäyslajittelu ei vaadi lisätilaa elementtien lajitteluun. Tilakompleksisuus on vakio eli O(1), koska käytetään vain muutamia väliaikaisia ​​muuttujia syötteen koosta riippumatta.

Ajan monimutkaisuus

Koska lisäyslajittelu iteroi yhden elementin kerrallaan, se vaatii N-1 lajittelukertaa N elementin lajittelemiseen. Jokaisella kierroksella se saattaa tehdä nolla vaihtoa, jos elementit on jo lajiteltu, tai se voi tarvita useita vaihtoja, jos elementit on järjestetty laskevaan järjestykseen.

• Passissa 1 vaaditut vähimmäisswapit ovat nolla ja vaadittujen vaihtojen enimmäismäärä on 1.
• Passissa 2 vaaditut vähimmäisswapit ovat nolla ja vaadittujen vaihtojen enimmäismäärä on 2.
• Passissa N vaadittu vähimmäisvaihto on nolla ja vaadittujen vaihtojen enimmäismäärä on N.
• Vähimmäisvaihto on nolla, joten paras aikakompleksisuus on O(N) N:n kierroksen iterointiin.
• Vaihtojen kokonaismäärä on enintään (1+2+3+4+…+N) eli N(N+1)/2, joten huonoin aikakompleksisuus on O(N^2).

Tässä on lisäyslajittelun tärkeä aikavaativuus:

• Pahimman tapauksen monimutkaisuus: O(n^2): Taulukon lajittelu laskevaan järjestykseen, kun sen vaaditaan olevan nouseva, on pahin mahdollinen skenaario.
• Paras tapauksen monimutkaisuus: O(n): Paras tapaus on, kun taulukko on jo lajiteltu; ulompi silmukka suoritetaan n kertaa, kun taas sisempi silmukka ei toimi ollenkaan. Vertailuja on vain n, joten monimutkaisuus on lineaarinen.
• Keskimääräinen tapauksen monimutkaisuus: O(n^2): Tämä tapahtuu, kun taulukon alkiot esiintyvät sekaisessa järjestyksessä, joka ei ole nouseva eikä laskeva.

UKK