Sisestamise sortimise algoritm C-ga, C++, Java, Python Näited

Mis on sisestamise sortimine?

Lisamissortimine on üks võrdlussortimise algoritme, mida kasutatakse elementide sortimiseks, itereerides ühte elementi korraga ja asetades elemendi õigesse kohta juba järjestatud piirkonnas.

Iga element lisatakse järjestikku juba sorteeritud loendisse. Juba sorteeritud loendi suurus on algselt üks. Lisamissortimise algoritm tagab, et esimesed k elementi sorteeritakse pärast välimise tsükli k-ndat iteratsiooni.

Kuna sisestussortimine loob tulemuse järk-järgult, on seda intuitiivne õpetada, seda on lihtne siluda ning see on tugev baas väga väikeste sisendite jaoks, kus keerukamad algoritmid lisaksid üldkulu ilma mõõdetava kasuta.

Sisestussortimise algoritmi omadused

Lisamissortimise algoritmil on järgmised olulised omadused, mis selgitavad selle käitumist reaalsetes töökoormustes:

• See on stabiilne sortimistehnika, mistõttu see ei muuda võrdsete elementide suhtelist järjestust.
• See on efektiivne väiksemate andmekogumite puhul, kuid mitte efektiivselt suuremate loendite puhul, kus domineerib ruutkasv.
• Sisestussortimine on adaptiivne, mis vähendab sammude koguarvu, kui sisend on osaliselt sorteeritud. Array on sisendiks, et muuta see tõhusaks, kuna juhuslik juurdepääs võimaldab sisemise tsükli ajal konstantse aja nihkeid.
• See on kohapealne algoritm, seega ei vaja see sisendi suurusega proportsionaalset abimälu.

Neid omadusi silmas pidades selgitab järgmine osa põhilist sisestamise operatsiooni, mis annab jõudu algoritmi igale läbimisele.

Kuidas sisestada Operatööd?

Lisamissortimise algoritmis kasutatakse lisamisoperatsiooni sortimata elementide sortimiseks. See aitab lisada uue elemendi juba sorteeritud loendisse, säilitades samal ajal sorteeritud piirkonna olemasoleva järjestuse.

Sisestusoperatsiooni pseudokood:

Vaatleme N elemendi loendit 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

Ülaltoodud näites lisatakse juba sorteeritud loendisse uus element 6. Järgmised sammud trace sisemist tsüklit, kui uus element liigub vasakule oma õige positsiooni suunas.

Step 1) Võrreldes A[5] vasakpoolse külgneva elemendiga 9 > 6, vahetame 9 ja 6 positsiooni. Nüüd liigutatakse element 6 positsiooni A[4].

Step 2) Nüüd võrdleme A[4] ja A[3] ning leiame, et A[3] > A[4], seega vahetame taas arvude 6 ja 8 asukoha.

Step 3) Nüüd võrdle A[3] ja A[2]. Kuna A[2] > A[3], siis vahetame arvude 7 ja 6 asukoha.

Step 4) Me võrdleme A[1] ja A[2]. Kuna A[1] < A[2], siis vasakpoolne külgnev element ei ole enam suurem. Järeldame, et 6 on õigesti lisatud ja peatame sisemise tsükli siin.

Kuidas sisestussortimine töötab

Ülalpool käsitletud lisamisoperatsioon on lisamissortimise selgroog. Lisamisprotseduur käivitatakse iga elemendi puhul ja lõpuks saame sorteeritud loendi, kuna sorteeritud piirkond kasvab iga välimise läbimisega ühe elemendi võrra.

Ülaltoodud joonis demonstreerib lisamissortimise toimimist andmestruktuuris. Algselt on sorteeritud alamloendis ainult üks element, st 4. Pärast A[1] sisestamist, st 3, kasvab sorteeritud alamloendi suurus 2-ni ja algoritm jätkab seda mustrit, kuni kõik elemendid on paigutatud.

Kui kontseptuaalne voog on paigas, näitavad järgmised osad konkreetseid rakendusi C++, C ja Python nii et saate võrrelda tsüklite struktuure eri keeltes.

C++ Programm sisestuse sortimiseks

. C++ Allolev implementatsioon kasutab kahte pesastatud tsüklit: välimine tsükkel valib järgmise sortimata elemendi ja sisemine tsükkel nihutab seda vasakule, kuni õige positsioon on leitud.

#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;
}

Väljund:

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

C Code sisestamise sortimise jaoks

Sama loogika on otse ülekantav ka C keelde. Standardne printf kõned asendavad voo väljundit, kuid sisemise tsükli vahetusmuster on identne C++ versiooni.

#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;
}

Väljund:

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

Python Programm sisestuse sortimiseks

Python toetab tuple vahetustping ühes avaldises, seega on sisemine tsükkel kompaktsem kui selle C ja C++ analoogid, säilitades samal ajal sama algoritmilise käitumise.

#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=" ")

Väljund:

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

Sisestussortimise omadused

Siin on lisamissortimise olulised omadused, mis aitavad teil otsustada, millal on see õige tööriist:

• Online: Lisamissortimine saab elemente sortida nende saabumisel. Kui oleme elementide loendi juba sortinud ja lisame loendisse veel elemente, ei pea me kogu sortimisprotseduuri uuesti käivitama. Selle asemel itereerime ainult äsja lisatud elementide kallal.
• Kohapeal: Lisamissortimise algoritmi ruumi keerukus on konstantne ega vaja lisaruumi. See algoritm sorteerib elemente kohapeal.
• Stabiilne: Lisamissortimise puhul ei vahetata elemente, kui nende väärtused on võrdsed. Näiteks kui kaks elementi, x ja y, on võrdsed ja x asub sortimata loendis enne y-d, siis sorteeritud loendis asub x ikkagi enne y-d. See muudab lisamissortimise stabiilseks.
• Kohanduv: A sortimisalgoritm on adaptiivne, kui see võtab vähem aega, kui sisendelemendid või elementide alamhulk on juba sorteeritud. Nagu me eespool arutlesime, on lisamissortimise parim jooksuaeg O(N) ja halvim jooksuaeg O(N^2). Lisamissortimine on üks adaptiivsetest sortimisalgoritmidest.

Sisestussortimise keerukus

Allolev keerukuse arutelu hõlmab nii mälukasutust kui ka käitusaega, nii et saate paigutada sisestussortimise alternatiivide, näiteks Bubble Sorteeri ja Kiire sortimine.

Ruumi keerukus

Lisamissortimine ei vaja elementide sortimiseks lisaruumi. Ruumi keerukus on konstantne, st O(1), kuna sisendi suurusest olenemata kasutatakse ainult mõnda ajutist muutujat.

Aja keerukus

Kuna lisamissortimine itereerib ühte elementi korraga, nõuab see N elemendi sortimiseks N-1 käiku. Iga käiguga ei pruugi see teha vahetusi, kui elemendid on juba sorteeritud, või palju vahetusi, kui elemendid on paigutatud kahanevas järjekorras.

• 1. passi puhul on minimaalsed nõutavad vahetustehingud null ja maksimaalne nõutav vahetustehing on 1.
• 2. passi puhul on minimaalsed nõutavad vahetustehingud null ja maksimaalne nõutav vahetustehing on 2.
• N passi puhul on minimaalne nõutav vahetustehing null ja maksimaalne nõutav vahetus on N.
• Minimaalne vahetus on null, seega on parim ajaline keerukus O(N) N korda itereerimiseks.
• Maksimaalne vahetuste arv on (1+2+3+4+…+N), st N(N+1)/2, seega on halvim ajaline keerukus O(N^2).

Siin on sisestamise sortimise oluline ajaline keerukus:

• Halvima juhtumi keerukus: O(n^2): Massiivi sortimine kahanevas järjekorras, kui see peab olema kasvavas järjekorras, on halvim stsenaarium.
• Parima juhtumi keerukus: O(n): Parim juhtum on siis, kui massiiv on juba sorteeritud; välimine tsükkel töötab n korda, samas kui sisemine tsükkel ei tööta üldse. Võrdlusi on ainult n, seega on keerukus lineaarne.
• Juhtumi keskmine keerukus: O(n^2): See juhtub siis, kui massiivi elemendid esinevad segases järjekorras, mis ei ole ei kasvav ega kahanev.

KKK