Algoritmul de sortare prin inserție cu C, C++, Java, Python Exemple

Ce este Insertion Sort?

Sortarea prin inserție este unul dintre algoritmii de sortare prin comparație utilizați pentru sortarea elementelor prin iterarea pe câte un element pe rând și plasarea elementului în poziția corectă într-o regiune deja ordonată.

Fiecare element este inserat secvențial într-o listă deja sortată. Dimensiunea inițială a listei deja sortate este unu. Algoritmul de sortare prin inserție asigură că primele k elemente sunt sortate după a k-a iterație a buclei exterioare.

Deoarece sortarea prin inserție construiește rezultatul incremental, este intuitiv de învățat, ușor de depanat și o bază puternică pentru intrări foarte mici, unde algoritmi mai complecși ar adăuga costuri suplimentare fără câștiguri măsurabile.

Caracteristicile algoritmului de sortare prin inserție

Algoritmul de sortare prin inserție are următoarele caracteristici importante care explică comportamentul său pe sarcini de lucru reale:

• Este o tehnică de sortare stabilă, deci nu modifică ordinea relativă a elementelor egale.
• Este eficient pentru seturi de date mai mici, dar nu și pentru liste mai mari unde domină creșterea pătratică.
• Sortarea prin inserție este adaptivă, ceea ce reduce numărul total de pași dacă datele de intrare sunt parțial sortate. Mulțime este furnizat ca intrare pentru a-l face eficient, deoarece accesul aleator permite deplasări constante în timp în timpul buclei interne.
• Este un algoritm in-place, deci nu necesită stocare auxiliară proporțională cu dimensiunea intrării.

Având în vedere aceste trăsături, următoarea secțiune explică operația de inserare de bază care alimentează fiecare pas al algoritmului.

Cum se inserează Operamunca de tion?

În algoritmul de sortare prin inserție, operația de inserare este utilizată pentru a sorta elementele nesortate. Aceasta ajută la inserarea unui element nou într-o listă deja sortată, păstrând în același timp ordinea existentă a regiunii sortate.

Pseudocod al operației de inserare:

Să considerăm o listă A de N elemente.

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

În exemplul de mai sus, un nou element 6 este inserat într-o listă deja sortată. Pașii următori trace bucla interioară pe măsură ce noul element migrează la stânga către poziția sa corectă.

Pas 1) În comparație cu elementul adiacent stâng al lui A[5], 9 > 6, schimbăm poziția lui 9 și 6. Acum elementul 6 este mutat în A[4].

Pas 2) Acum, comparăm A[4] și A[3] și constatăm că A[3] > A[4], așa că inversăm din nou poziția lui 6 și 8.

Pas 3) Acum comparați A[3] și A[2]. Când A[2] > A[3], inversăm poziția lui 7 și 6.

Pas 4) Comparăm A[1] și A[2]. Când A[1] < A[2], elementul adiacent la stânga nu mai este mai mare. Concluzionăm că 6 este introdus corect și oprim bucla interioară aici.

Cum funcționează sortarea inserției

Operația de inserare discutată mai sus este coloana vertebrală a sortării prin inserție. Procedura de inserare este executată pe fiecare element și, la final, obținem lista sortată pe măsură ce regiunea sortată crește cu un element la fiecare trecere externă.

Figura de mai sus demonstrează funcționarea sortării prin inserție într-o structură de date. Inițial, în sublista sortată se află un singur element, adică 4. După inserarea lui A[1], adică 3, dimensiunea sublistei sortate crește la 2, iar algoritmul continuă acest model până când fiecare element a fost plasat.

Odată ce fluxul conceptual a fost stabilit, următoarele secțiuni prezintă implementări concrete în C++, C și Python astfel încât să puteți compara structurile de bucle între diferite limbaje.

C++ Program de sortare prin inserare

C++ Implementarea de mai jos folosește două bucle imbricate: bucla exterioară selectează următorul element nesortat, iar bucla interioară îl deplasează la stânga până când este găsită poziția corectă.

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

ieșire:

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

C Code pentru sortare prin inserție

Aceeași logică se traduce direct în C. Standardul printf apelurile înlocuiesc ieșirea fluxului, dar modelul de swap din interiorul buclei interioare este identic cu C++ versiune.

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

ieșire:

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 de sortare prin inserare

Python suportă schimbarea tuplurilorping într-o singură expresie, deci bucla interioară este mai compactă decât C-ul său și C++ omologi, păstrând în același timp același comportament algoritmic.

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

ieșire:

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

Proprietăți ale sortării inserției

Iată câteva proprietăți importante ale sortării prin inserție care vă ajută să decideți când este instrumentul potrivit:

• online: Sortarea prin inserție poate sorta elementele pe măsură ce le primește. Dacă am sortat deja o listă de elemente și adăugăm mai multe elemente la listă, atunci nu este nevoie să rulăm din nou întreaga procedură de sortare. În schimb, iterăm doar pe elementele nou adăugate.
• La loc: Complexitatea spațială a algoritmului de sortare prin inserție este constantă și nu necesită spațiu suplimentar. Acest algoritm sortează elementele la locul lor.
• Grajd: În sortarea prin inserție, nu inversăm elementele dacă valorile lor sunt egale. De exemplu, dacă două elemente, x și y, sunt egale și x apare înaintea lui y în lista nesortată, atunci în lista sortată, x va apărea în continuare înaintea lui y. Acest lucru face ca sortarea prin inserție să fie stabilă.
• Adaptiv: A algoritm de sortare este adaptivă dacă durează mai puțin atunci când elementele de intrare sau un subset de elemente sunt deja sortate. După cum am discutat mai sus, cel mai bun timp de execuție al sortării prin inserție este O(N), iar cel mai slab timp de execuție este O(N^2). Sortarea prin inserție este unul dintre algoritmii de sortare adaptivă.

Complexitatea sortării inserției

Discuția despre complexitate de mai jos acoperă atât utilizarea memoriei, cât și timpul de execuție, astfel încât să puteți poziționa sortarea prin inserție în raport cu alternative precum Bubble Sortare și Sortare rapida.

Complexitatea spațială

Sortarea prin inserție nu necesită spațiu suplimentar pentru sortarea elementelor. Complexitatea spațiului este constantă, adică O(1), deoarece se utilizează doar câteva variabile temporare, indiferent de dimensiunea intrării.

Complexitatea timpului

Deoarece sortarea prin inserție iterează câte un element odată, necesită N-1 treceri pentru a sorta N elemente. Pentru fiecare trecere, poate face zero schimbări dacă elementele sunt deja sortate sau poate necesita mai multe schimbări dacă elementele sunt aranjate în ordine descrescătoare.

• Pentru trecerea 1, schimburile minime necesare sunt zero, iar swapurile maxime necesare sunt 1.
• Pentru trecerea 2, schimburile minime necesare sunt zero, iar swapurile maxime necesare sunt 2.
• Pentru trecerea N, schimbul minim necesar este zero, iar swapurile maxime necesare sunt N.
• Schimbarea minimă este zero, deci cea mai bună complexitate de timp este O(N) pentru repetarea N treceri.
• Numărul maxim de schimbări este (1+2+3+4+…+N), adică N(N+1)/2, deci cea mai slabă complexitate temporală este O(N^2).

Iată complexitatea temporală importantă a sortării prin inserție:

• Complexitatea celui mai rău cazO(n^2): Sortarea unui tablou în ordine descrescătoare atunci când trebuie să fie crescătoare este cel mai rău scenariu posibil.
• Complexitatea celui mai bun caz: O(n): Cel mai bun caz apare atunci când matricea este deja sortată; bucla externă rulează de n ori, în timp ce bucla interioară nu rulează deloc. Există doar n comparații, deci complexitatea este liniară.
• Complexitatea medie a cazului: O(n^2): Aceasta se întâmplă atunci când elementele tabloului apar într-o ordine amestecată, care nu este nici crescătoare, nici descendentă.

Întrebări frecvente