Sortiranje umetanjem: algoritam s C, C++, Java, Python Primjeri

Što je sortiranje umetanjem?

Sortiranje umetanjem jedan je od algoritama za usporedbu sortiranja koji se koristi za sortiranje elemenata iteriranjem jednog po jednog elementa i postavljanjem elementa na njegovu ispravnu poziciju.

Svaki element se redom umeće u već sortirani popis. Veličina već sortiranog popisa početno je jedan. Algoritam sortiranja umetanjem osigurava sortiranje prvih k elemenata nakon k-te iteracije.

Karakteristike algoritma sortiranja umetanjem

Algoritam za sortiranje umetanjem ima sljedeće važne karakteristike:

• 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.
• Sortiranje umetanjem je prilagodljivo, što smanjuje njegov ukupni broj koraka ako je djelomično sortirano. Poredak daje se kao ulaz kako bi bio učinkovit.

Kako Insert Operarad?

U algoritmu sortiranja umetanjem, operacija umetanja koristi se za sortiranje nesortiranih elemenata. Pomaže umetanje novog elementa u već sortirani popis.

Pseudokod operacije umetanja:

Razmotrimo listu A od N elemenata.

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   

U gornjem primjeru, novi element 6 treba umetnuti u već sortirani popis.

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], ponovno mijenjamo položaj 6 i 8.

Korak 3) Sada usporedite A[3] i A[2], budući da A[2] > A[3] mijenjaju položaj 7 i 6.

Korak 4) Uspoređujemo A[1] i A[2], a kako je A[1] < A[2], tj. lijevi susjedni element više nije veći. Sada zaključujemo da je 6 ispravno umetnuto i ovdje zaustavljamo algoritam.

Kako funkcionira sortiranje umetanjem

Gore razmotrena operacija umetanja je okosnica sortiranja umetanjem. Procedura umetanja se izvodi na svakom elementu, te na kraju dobijemo sortiranu listu.

Gornja primjerna slika pokazuje rad sortiranja umetanjem u strukturi podataka. U početku se samo jedan element nalazi u sortiranoj podlisti, tj. 4. Nakon umetanja A[1], tj. 3, veličina sortirane podliste raste na 2.

C++ Program za sortiranje umetanjem

#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

#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

#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:

• Na liniji: Sortiranje umetanjem može sortirati elemente kako ih primi. Odnosno, ako smo već sortirali popis elemenata i dodali još neke elemente popisima, tada ne moramo ponovno pokretati cijeli postupak sortiranja. Umjesto toga, trebamo ponavljati samo novo dodane elemente.
• Na mjestu: Prostorna složenost algoritma sortiranja umetanjem je konstantna i ne zahtijeva dodatni prostor. Ovaj algoritam sortira elemente na mjestu.
• Stabilan: Kod sortiranja umetanjem ne mijenjamo elemente ako su im vrijednosti jednake. Na primjer, dva elementa, x i y, su jednaka, a x se pojavljuje ispred y na nesortiranim popisima, tada će se na sortiranom popisu x pojaviti ispred y. To čini sortiranje umetanja stabilnim.
• Prilagodljivo: A algoritam sortiranja je prilagodljiv ako traje manje vremena ako su ulazni elementi ili podskup elemenata već sortirani. Kao što smo gore spomenuli, najbolje vrijeme izvođenja sortiranja umetanjem je O(N), a najgore vrijeme izvođenja je O(N^2). Insertion sort je jedan od adaptivnih algoritama sortiranja.

Složenost sortiranja umetanjem

Složenost prostora

Sortiranje umetanjem ne zahtijeva dodatni prostor za sortiranje elemenata, složenost prostora je konstantna, tj. O(1).

Složenost vremena

Kako sortiranje umetanjem ponavlja svaki element istovremeno, potrebno je N-1 prolaza za sortiranje N elemenata. Za svaki prolaz može izvršiti nultu zamjenu ako su elementi već sortirani ili zamijeniti 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 razmjene su (1+2+3+4+..+N) i. N(N+1)/2, najgora vremenska složenost je O(N^2).

Ovdje je važna vremenska složenost sortiranja umetanjem:

• Složenost u najgorem slučaju: O(n2): Sortiranje niza u silaznom redoslijedu kada je u uzlaznom redoslijedu najgori je scenarij.
• Složenost u najboljem slučaju: O(n): Složenost u najboljem slučaju događa se kada je niz već sortiran, vanjska petlja se izvodi n broj puta, dok se unutarnja petlja uopće ne pokreće. Postoji samo n broj usporedbi. Dakle, u ovom slučaju, složenost je linearna.
• Prosječna složenost slučaja: O(n2): To se događa kada se elementi niza pojavljuju u zbrkanom redoslijedu, koji nije ni uzlazni ni silazni.

Rezime

• Sortiranje umetanjem je metoda algoritma sortiranja koja se temelji na usporedbi.
• To je stabilna tehnika sortiranja, tako da ne mijenja relativni poredak jednakih elemenata.
• Na svakom elementu, operacija umetanja koristi se za umetanje elementa u sortirani pod-popis.
• Sortiranje umetanjem je algoritam za sortiranje na mjestu.
• Najgora i prosječna vremenska složenost sortiranja umetanjem je kvadratna, tj. O(N^2).
• Sortiranje umetanjem ne zahtijeva nikakav pomoćni prostor.