Algoritam sortiranja umetanjem s C-om, C++, Java, Python Primjeri

Što je sortiranje umetanjem?

Sortiranje umetanjem jedan je od algoritama za sortiranje usporedbom koji se koristi za sortiranje elemenata iteracijom jednog elementa istovremeno i postavljanjem elementa na ispravnu poziciju unutar već uređenog područja.

Svaki element se sekvencijalno ubacuje u već sortiranu listu. Veličina već sortirane liste u početku je jedan. Algoritam sortiranja umetanjem osigurava da se prvih k elemenata sortira nakon k-te iteracije vanjske petlje.

Budući da sortiranje umetanjem gradi rezultat postupno, intuitivno ga je naučiti, lako ga je ispraviti i predstavlja snažnu osnovu za vrlo male ulaze gdje bi složeniji algoritmi dodali opterećenje bez mjerljivih dobitaka.

Karakteristike algoritma sortiranja umetanjem

Algoritam za sortiranje umetanjem ima sljedeće važne karakteristike koje objašnjavaju njegovo ponašanje na stvarnim opterećenjima:

• To je stabilna tehnika sortiranja, tako da ne mijenja relativni poredak jednakih elemenata.
• Učinkovit je za manje skupove podataka, ali nije učinkovit za veće popise gdje dominira kvadratni rast.
• Sortiranje umetanjem je adaptivno, što smanjuje ukupan broj koraka ako je ulaz djelomično sortiran. Poredak se daje kao ulaz kako bi bio učinkovit jer slučajni pristup omogućuje pomake u konstantnom vremenu tijekom unutarnje petlje.
• To je algoritam na mjestu, tako da ne zahtijeva pomoćnu pohranu proporcionalnu veličini ulaza.

Imajući na umu ove osobine, sljedeći odjeljak objašnjava osnovnu operaciju umetanja koja pokreće svaki prolaz algoritma.

Kako Insert Operarad?

U algoritmu sortiranja umetanjem, operacija umetanja koristi se za sortiranje nesortiranih elemenata. Pomaže u umetanju novog elementa u već sortirani popis uz očuvanje postojećeg redoslijeda sortiranog područja.

Pseudokod operacije umetanja:

Razmotrimo listu A od N elemenata.

// 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

U gornjem primjeru, novi element 6 umetnut je u već sortiranu listu. Sljedeći koraci tracunutarnju petlju dok se novi element pomiče lijevo prema svojoj ispravnoj poziciji.

Korak 1) U usporedbi s lijevim susjednim elementom od A[5], 9 > 6, mijenjamo položaj 9 i 6. Sada je element 6 premješten u A[4].

Korak 2) Sada uspoređujemo A[4] i A[3] i nalazimo da je A[3] > A[4], pa ponovno mijenjamo pozicije 6 i 8.

Korak 3) Sada usporedimo A[3] i A[2]. Kako je A[2] > A[3], mijenjamo pozicije 7 i 6.

Korak 4) Uspoređujemo A[1] i A[2]. Kako je A[1] < A[2], lijevi susjedni element više nije veći. Zaključujemo da je 6 ispravno umetnut i ovdje zaustavljamo unutarnju petlju.

Kako funkcionira sortiranje umetanjem

Gore opisana operacija umetanja je okosnica sortiranja umetanjem. Postupak umetanja izvršava se na svakom elementu, a na kraju dobivamo sortirani popis kako sortirano područje raste za jedan element u svakom vanjskom prolazu.

Gornja slika prikazuje rad sortiranja umetanjem u strukturi podataka. U početku se u sortiranoj podlisti nalazi samo jedan element, tj. 4. Nakon umetanja A[1], tj. 3, veličina sortirane podliste raste na 2, a algoritam nastavlja ovaj obrazac sve dok se ne smjesti svaki element.

S uspostavljenim konceptualnim tokom, sljedeći odjeljci prikazuju konkretne implementacije u C++, C i Python tako da možete usporediti strukture petlji u različitim jezicima.

C++ Program za sortiranje umetanjem

The C++ Implementacija u nastavku koristi dvije ugniježđene petlje: vanjska petlja odabire sljedeći nesortirani element, a unutarnja petlja ga pomiče lijevo dok se ne pronađe ispravna pozicija.

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

Izlaz:

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

C Code za sortiranje umetanjem

Ista logika se izravno prevodi u C. Standard printf pozivi zamjenjuju izlaz toka, ali obrazac zamjene unutar unutarnje petlje je identičan onome C++ verzija.

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

Izlaz:

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

Python Program za sortiranje umetanjem

Python podržava zamjenu tuple-ovaping u jednom izrazu, tako da je unutarnja petlja kompaktnija od svog C i C++ kolegama uz očuvanje istog algoritamskog ponašanja.

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

Izlaz:

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

Svojstva sortiranja umetanjem

Evo važnih svojstava sortiranja umetanjem koja vam pomažu da odlučite kada je to pravi alat:

• Na liniji: Sortiranje umetanjem može sortirati elemente kako ih prima. Ako smo već sortirali popis elemenata i dodali još elemenata na popis, tada ne moramo ponovno pokretati cijeli postupak sortiranja. Umjesto toga, iteriramo samo na novododanim elementima.
• Na mjestu: Prostorna složenost algoritma sortiranja umetanjem je konstantna i ne zahtijeva dodatni prostor. Ovaj algoritam sortira elemente na mjestu.
• Stabilan: U sortiranju umetanjem ne mijenjamo elemente ako su im vrijednosti jednake. Na primjer, ako su dva elementa, x i y, jednaka i x se pojavljuje prije y u nesortiranom popisu, tada će se u sortiranom popisu x i dalje pojaviti prije y. To čini sortiranje umetanjem stabilnim.
• Prilagodljivo: A algoritam sortiranja je adaptivno ako traje kraće kada su ulazni elementi ili podskup elemenata već sortirani. Kao što smo gore raspravljali, najbolje vrijeme izvođenja sortiranja umetanjem je O(N), a najgore vrijeme izvođenja je O(N^2). Sortiranje umetanjem je jedan od adaptivnih algoritama sortiranja.

Složenost sortiranja umetanjem

Rasprava o složenosti u nastavku pokriva i korištenje memorije i vrijeme izvođenja, tako da možete pozicionirati sortiranje umetanjem u odnosu na alternative kao što su Bubble Razvrstaj i Brzo sortiranje.

Složenost prostora

Sortiranje umetanjem ne zahtijeva dodatni prostor za sortiranje elemenata. Prostorna složenost je konstantna, tj. O(1), jer se koristi samo nekoliko privremenih varijabli bez obzira na veličinu ulaza.

Složenost vremena

Budući da sortiranje umetanjem ponavlja jedan element odjednom, potreban je N-1 prolaz za sortiranje N elemenata. Za svaki prolaz može napraviti nula zamjena ako su elementi već sortirani ili može trebati mnogo zamjena ako su elementi poredani silaznim redoslijedom.

• Za prolaz 1, minimalni potrebni swapovi su nula, a maksimalni potrebni swapovi su 1.
• Za prolaz 2, minimalni potrebni swapovi su nula, a maksimalni potrebni swapovi su 2.
• Za prolaz N, minimalna potrebna zamjena je nula, a maksimalna potrebna zamjena je N.
• Minimalni swap je nula, tako da je najbolja vremenska složenost O(N) za ponavljanje N prolaza.
• Ukupni maksimalni broj zamjena je (1+2+3+4+…+N), tj. N(N+1)/2, pa je najgora vremenska složenost O(N^2).

Evo važne vremenske složenosti sortiranja umetanjem:

• Složenost u najgorem slučaju: O(n^2): Sortiranje niza u silaznom redoslijedu kada se zahtijeva da bude uzlazni je najgori mogući scenarij.
• Složenost u najboljem slučaju: O(n): Najbolji slučaj se događa kada je niz već sortiran; vanjska petlja se izvršava n puta, dok se unutarnja petlja uopće ne izvršava. Postoji samo n usporedbi, pa je složenost linearna.
• Prosječna složenost slučaja: O(n^2): To se događa kada se elementi niza pojavljuju u isprekidanom redoslijedu koji nije ni uzlazni ni silazni.

Pitanja i odgovori