Lisäyslajittelu: Algoritmi C, C++, Java, Python Esimerkit

Mikä on lisäyslajittelu?

Lisäyslajittelu on yksi vertailulajittelualgoritmeista, joita käytetään elementtien lajitteluun iteroimalla yhtä elementtiä kerrallaan ja sijoittamalla elementti oikeaan paikkaan.

Jokainen elementti lisätään peräkkäin jo lajiteltuun luetteloon. Jo järjestetyn listan koko on aluksi yksi. Lisäyslajittelualgoritmi varmistaa, että ensimmäiset k elementtiä lajitellaan k:nnen iteraation jälkeen.

Lisäyslajittelualgoritmin ominaisuudet

Lisäyslajittelun algoritmilla on seuraavat tärkeät ominaisuudet:

• Se on vakaa lajittelutekniikka, joten se ei muuta yhtäläisten elementtien suhteellista järjestystä.
• Se on tehokas pienille tietojoukoille, mutta ei tehokas suuremmille luetteloille.
• Lisäyslajittelu on mukautuva, mikä vähentää sen vaiheiden kokonaismäärää, jos se on osittain lajiteltu. Ryhmä tarjotaan syötteenä sen tehostamiseksi.

Miten Insert Operatyöhön?

Insertion Sort -algoritmissa lisäystoimintoa käytetään lajittelemattomien elementtien lajitteluun. Se auttaa lisäämään uuden elementin jo lajiteltuun luetteloon.

Lisäämistoiminnon pseudokoodi:

Tarkastellaan N elementin listaa A.

A[N-1] is the element to be inserted in the 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 on lisättävä jo lajiteltuun luetteloon.

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], ja huomaamme, että A[3] > A[4], vaihdamme jälleen 6:n ja 8:n paikkaa.

Vaihe 3) Vertaa nyt A[3] ja A[2], koska A[2] > A[3] vaihtavat 7:n ja 6:n paikan.

Vaihe 4) Vertaamme A[1] ja A[2], ja kun A[1] < A[2], eli vasen viereinen elementti ei ole enää suurempi. Nyt päätämme, että 6 on lisätty oikein, ja lopetamme algoritmin tähän.

Kuinka lisäyslajittelu toimii

Yllä käsitelty lisäystoiminto on lisäyslajittelun selkäranka. Lisäystoimenpide suoritetaan jokaiselle elementille, ja lopulta saamme lajitellun luettelon.

Yllä oleva esimerkkikuva havainnollistaa lisäyslajittelun toimintaa tietorakenteessa. Aluksi lajitetussa aliluettelossa on vain yksi elementti eli 4. Kun A[1] eli 3 on lisätty, lajitellun aliluettelon koko kasvaa 2:ksi.

C++ Ohjelma lisäyslajitteluun

#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 Koodi lisäyslajittelulle

#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

#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ä ovat lisäyslajittelun tärkeät ominaisuudet:

• Online: Lisäyslajittelu voi lajitella elementtejä vastaanottaessaan. Eli jos olemme jo lajitelleet elementtiluettelon ja lisänneet luetteloihin lisää elementtejä, meidän ei tarvitse suorittaa koko lajitteluprosessia uudelleen. Sen sijaan meidän on toistettava vain äskettäin lisätyt elementit.
• Paikallaan: Lisäyslajittelualgoritmin tilamonimutkaisuus on vakio eikä vaadi ylimääräistä tilaa. Tämä algoritmi lajittelee elementit paikoilleen.
• Vakaa: Lisäyslajittelussa emme vaihda elementtejä, jos niiden arvot ovat samat. Esimerkiksi kaksi elementtiä, x ja y, ovat yhtä suuret, ja x näkyy ennen y:tä lajittelemattomissa luetteloissa, sitten lajitetussa luettelossa x näkyy ennen y:tä. Tämä tekee lisäyslajittelusta vakaan.
• Mukautuva: A lajittelualgoritmi on mukautuva, jos se vie vähemmän aikaa, jos syöteelementit tai elementtien osajoukko on jo lajiteltu. Kuten yllä käsittelimme, lisäyslajittelun paras käyntiaika on O(N) ja huonoin käyntiaika on O(N^2). Lisäyslajittelu on yksi mukautuvista lajittelualgoritmeista.

Lisäyslajittelun monimutkaisuus

Avaruuden monimutkaisuus

Lisäyslajittelu ei vaadi ylimääräistä tilaa elementtien lajitteluun, tilan monimutkaisuus on vakio, eli O(1).

Ajan monimutkaisuus

Koska lisäyslajittelu iteroi jokaista elementtiä samanaikaisesti, N-elementin lajitteleminen vaatii N-1 läpimenoa. Jokaisella siirrolla se voi tehdä nollan vaihtoja, jos elementit on jo lajiteltu, tai vaihtaa, 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.
• Vaihtosopimusten enimmäismäärä on (1+2+3+4+..+N) i. N(N+1)/2, huonoin aikakompleksisuus on O(N^2).

Tässä on lisäyslajittelun tärkeä aika monimutkaisuus:

• Pahimman tapauksen monimutkaisuus: O(n2): Matriisin lajittelu laskevaan järjestykseen, kun se on nousevassa järjestyksessä, on pahin skenaario.
• Paras tapauksen monimutkaisuus: O(n): Parhaan tapauksen monimutkaisuus ilmenee, kun taulukko on jo lajiteltu, ulompi silmukka suoritetaan n kertaa, kun taas sisempi silmukka ei toimi ollenkaan. Vertailuja on vain n. Joten tässä tapauksessa monimutkaisuus on lineaarinen.
• Keskimääräinen tapauksen monimutkaisuus: O(n2): Se tapahtuu, kun taulukon elementit esiintyvät sekaisin järjestyksessä, joka ei ole nouseva eikä laskeva.

Yhteenveto

• Lisäyslajittelu on lajittelualgoritmimenetelmä, joka perustuu vertailuun.
• Se on vakaa lajittelutekniikka, joten se ei muuta yhtäläisten elementtien suhteellista järjestystä.
• Jokaisessa elementissä lisäystoimintoa käytetään elementin lisäämiseen lajiteltuun aliluetteloon.
• Lisäyslajittelu on paikallaan tapahtuva lajittelualgoritmi.
• Lisäyslajittelun huonoin ja keskimääräinen aikakompleksisuus on neliöllinen, eli O(N^2).
• Lisäyslajittelu ei vaadi aputilaa.