Algoritmo di ordinamento per inserimento con C, C++, Java, Python Esempi

Cos'è l'ordinamento per inserzione?

L'ordinamento per inserimento è uno degli algoritmi di ordinamento per confronto utilizzati per ordinare gli elementi iterando su un elemento alla volta e posizionandolo nella sua posizione corretta all'interno di una regione già ordinata.

Ciascun elemento viene inserito sequenzialmente in una lista già ordinata. La dimensione iniziale della lista già ordinata è uno. L'algoritmo di ordinamento per inserimento garantisce che i primi k elementi siano ordinati dopo la k-esima iterazione del ciclo esterno.

Poiché l'algoritmo Insertion Sort costruisce il risultato in modo incrementale, è intuitivo da insegnare, facile da sottoporre a debug e rappresenta un'ottima base di partenza per input molto piccoli, dove algoritmi più complessi aggiungerebbero un sovraccarico senza vantaggi misurabili.

Caratteristiche dell'algoritmo di ordinamento per inserzione

L'algoritmo di ordinamento per inserimento presenta le seguenti caratteristiche importanti che ne spiegano il comportamento su carichi di lavoro reali:

• È una tecnica di ordinamento stabile, quindi non modifica l'ordine relativo degli elementi uguali.
• È efficiente per insiemi di dati di piccole dimensioni, ma non efficace per elenchi più lunghi dove prevale la crescita quadratica.
• L'ordinamento per inserimento è adattivo, ovvero riduce il numero totale di passaggi se l'input è parzialmente ordinato. Italia viene fornito come input per renderlo efficiente poiché l'accesso casuale consente spostamenti a tempo costante durante il ciclo interno.
• Si tratta di un algoritmo in loco, quindi non richiede memoria ausiliaria proporzionale alla dimensione dell'input.

Tenendo presenti queste caratteristiche, la sezione successiva illustra l'operazione di inserimento fondamentale che alimenta ogni passaggio dell'algoritmo.

Come funziona Insert Operalavoro?

Nell'algoritmo Insertion Sort, l'operazione di inserimento viene utilizzata per ordinare gli elementi non ordinati. Consente di inserire un nuovo elemento in un elenco già ordinato, preservando l'ordine esistente della regione ordinata.

Pseudocodice dell'operazione di inserimento:

Consideriamo una lista A di N elementi.

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

Nell'esempio precedente, un nuovo elemento 6 viene inserito in un elenco già ordinato. I passaggi seguenti trace il ciclo interno mentre il nuovo elemento migra verso sinistra, in direzione della sua posizione corretta.

Passo 1) Rispetto all'elemento adiacente sinistro di A[5], 9 > 6, invertiamo la posizione di 9 e 6. Ora l'elemento 6 viene spostato in A[4].

Passo 2) Ora confrontiamo A[4] e A[3] e scopriamo che A[3] > A[4], quindi scambiamo di nuovo la posizione di 6 e 8.

Passo 3) Ora confrontiamo A[3] e A[2]. Poiché A[2] > A[3], scambiamo la posizione di 7 e 6.

Passo 4) Confrontiamo A[1] e A[2]. Poiché A[1] < A[2], l'elemento adiacente a sinistra non è più maggiore. Concludiamo che 6 è stato inserito correttamente e interrompiamo il ciclo interno qui.

Come funziona l'ordinamento per inserimento

L'operazione di inserimento descritta sopra è la base dell'algoritmo di ordinamento per inserimento (Insertion Sort). La procedura di inserimento viene eseguita su ogni elemento e, alla fine, si ottiene la lista ordinata, poiché la regione ordinata si espande di un elemento a ogni passaggio verso l'esterno.

La figura sopra illustra il funzionamento dell'algoritmo di ordinamento per inserimento (Insertion Sort) in una struttura dati. Inizialmente, la sottolista ordinata contiene un solo elemento, ovvero 4. Dopo l'inserimento di A[1], ovvero 3, la dimensione della sottolista ordinata aumenta a 2 e l'algoritmo continua questo schema finché ogni elemento non è stato inserito.

Con il flusso concettuale in atto, le sezioni seguenti mostrano implementazioni concrete in C++, C, e Python in modo da poter confrontare le strutture dei cicli tra diversi linguaggi di programmazione.

C++ Programma per l'ordinamento per inserimento

Migliori C++ L'implementazione seguente utilizza due cicli annidati: il ciclo esterno seleziona il successivo elemento non ordinato, mentre il ciclo interno lo sposta a sinistra finché non viene trovata la posizione corretta.

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

Produzione:

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

C Code per l'ordinamento per inserimento

La stessa logica si traduce direttamente in C. Lo standard printf le chiamate sostituiscono l'output del flusso, ma lo schema di scambio all'interno del ciclo interno è identico a quello C++ versione.

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

Produzione:

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

Python Programma per l'ordinamento per inserimento

Python supporta lo scambio di tupleping in un'unica espressione, quindi il ciclo interno è più compatto del suo C e C++ controparti pur preservando lo stesso comportamento algoritmico.

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

Produzione:

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

Proprietà dell'ordinamento di inserimento

Ecco alcune importanti proprietà dell'algoritmo di ordinamento per inserimento che ti aiuteranno a decidere quando è lo strumento giusto per te:

• In linea: L'ordinamento per inserimento può ordinare gli elementi man mano che li riceve. Se abbiamo già ordinato un elenco di elementi e ne aggiungiamo altri, non è necessario eseguire nuovamente l'intera procedura di ordinamento. Invece, iteriamo solo sugli elementi appena aggiunti.
• A posto: La complessità spaziale dell'algoritmo di ordinamento per inserimento è costante e non richiede spazio aggiuntivo. Questo algoritmo ordina gli elementi sul posto.
• Stabile: Nell'algoritmo di ordinamento per inserimento, gli elementi non vengono scambiati se i loro valori sono uguali. Ad esempio, se due elementi, x e y, hanno lo stesso valore e x appare prima di y nell'elenco non ordinato, anche nell'elenco ordinato x apparirà prima di y. Questo rende l'algoritmo di ordinamento per inserimento stabile.
• Adattivo: A algoritmo di ordinamento Un algoritmo di ordinamento è adattivo se impiega meno tempo quando gli elementi di input, o un sottoinsieme di essi, sono già ordinati. Come discusso in precedenza, il tempo di esecuzione migliore dell'Insertion Sort è O(N), mentre il peggiore è O(N^2). L'Insertion Sort è uno degli algoritmi di ordinamento adattivo.

Complessità dell'ordinamento per inserimento

La discussione sulla complessità che segue copre sia l'utilizzo della memoria che il tempo di esecuzione, in modo da poter posizionare l'Insertion Sort rispetto ad alternative come Bubble Ordina and Ordinamento rapido.

Complessità spaziale

L'algoritmo di ordinamento per inserimento non richiede spazio aggiuntivo per ordinare gli elementi. La complessità spaziale è costante, ovvero O(1), poiché vengono utilizzate solo poche variabili temporanee indipendentemente dalla dimensione dell'input.

Complessità temporale

Poiché l'algoritmo di ordinamento per inserimento itera un elemento alla volta, richiede N-1 passaggi per ordinare N elementi. Per ogni passaggio, potrebbe non effettuare alcuno scambio se gli elementi sono già ordinati, oppure potrebbe richiederne molti se gli elementi sono disposti in ordine decrescente.

• Per il passaggio 1, gli scambi minimi richiesti sono zero e gli scambi massimi richiesti sono 1.
• Per il passaggio 2, gli scambi minimi richiesti sono zero e gli scambi massimi richiesti sono 2.
• Per il passaggio N, lo scambio minimo richiesto è zero e gli scambi massimi richiesti sono N.
• Lo scambio minimo è zero, quindi la migliore complessità temporale è O(N) per l'iterazione di N passaggi.
• Il numero massimo totale di scambi è (1+2+3+4+…+N), ovvero N(N+1)/2, quindi la complessità temporale peggiore è O(N^2).

Ecco la complessità temporale più importante dell'algoritmo di ordinamento per inserimento:

• Complessità del caso peggiore: O(n^2): Ordinare un array in ordine decrescente quando è richiesto un ordine crescente è lo scenario peggiore.
• migliore Complessità del caso: O(n): Il caso migliore si verifica quando l'array è già ordinato; il ciclo esterno viene eseguito n volte, mentre il ciclo interno non viene eseguito affatto. Ci sono solo n confronti, quindi la complessità è lineare.
• Complessità media del caso: O(n^2): Ciò si verifica quando gli elementi dell'array si presentano in un ordine disordinato che non è né crescente né decrescente.

DOMANDE FREQUENTI