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

By: Sara Chen Sara Chen
Hours aggiornato

⚡ Riepilogo intelligente

L'ordinamento per inserimento è un metodo di ordinamento in loco basato sul confronto che costruisce una lista ordinata un elemento alla volta. È stabile, adattabile, semplice da implementare e, nella pratica, si adatta bene a set di dati di piccole dimensioni o quasi ordinati.

  • 📥 Idea centrale: L'algoritmo di ordinamento per inserimento seleziona ogni elemento e lo sposta a sinistra finché non si trova nella posizione corretta all'interno della sottolista già ordinata.
  • 🔁 inserire Operazione: L'algoritmo si basa su ripetuti confronti di scambio con sinistra, che aumentano la regione ordinata di un elemento per ogni passaggio del ciclo esterno.
  • ⚡ Complessità temporale: Il caso migliore richiede una complessità temporale di O(n) per dati già ordinati, mentre i casi peggiore e medio raggiungono O(n^2) per input invertiti o mescolati.
  • ✅ Proprietà: L'algoritmo è online, in loco, stabile e adattivo, il che lo rende prevedibile per inserimenti in streaming e array parzialmente ordinati.
  • 🧪 Code Copertura: Le implementazioni di riferimento sono fornite in C, C++e Python in modo che gli studenti possano confrontare le strutture dei cicli e i meccanismi di scambio fianco a fianco.
  • 🤖 Angolo dell'IA: I moderni assistenti basati sull'intelligenza artificiale visualizzano i passaggi dell'algoritmo di ordinamento per inserimento e lo raccomandano quando gli array di input sono corti o quasi ordinati.
Scopri di più

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

inserire Operalavoro di zione

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.

ARTICOLI CORRELATI

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.

L'ordinamento per inserimento funziona

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

Scegli l'algoritmo Insertion Sort per array di piccole dimensioni, dati quasi ordinati o inserimenti in streaming in cui i nuovi elementi arrivano dopo un ordinamento iniziale. Il suo basso overhead costante e il comportamento adattivo spesso superano algoritmi più complessi in questi carichi di lavoro.

Sì. L'algoritmo Insertion Sort è stabile perché non scambia mai i valori uguali, preservandone l'ordine originale. È inoltre in-place perché ordina utilizzando solo l'array di input più un piccolo numero fisso di variabili temporanee, fornendo uno spazio ausiliario O(1).

Il caso migliore è O(n) quando l'input è già ordinato perché il ciclo interno non viene mai eseguito. I casi peggiore e medio sono entrambi O(n^2) quando l'array è ordinato in modo inverso o disordinato, a causa dello spostamento ripetuto degli elementi verso l'inizio dell'array.

Gli assistenti IA generano animazioni e tabelle passo passo che contrassegnano l'elemento corrente, la regione ordinata e il puntatore di confronto per ogni passaggio. Questa visualizzazione aiuta gli studenti trace scambia, individua gli errori di un'unità e conferma che il prefisso ordinato cresca di un elemento ad ogni iterazione esterna.

Sì. I selettori basati sull'IA analizzano le dimensioni, la distribuzione e il preordinamento degli array, quindi instradano gli input piccoli o quasi ordinati all'Insertion Sort, mentre gli input casuali più grandi vengono instradati al Quick Sort o al Merge Sort. Algoritmi ibridi come Timsort applicano già questa idea all'interno delle loro partizioni interne.

L'algoritmo Insertion Sort costruisce la regione ordinata inserendo ogni nuovo elemento nella posizione corretta, mentre il Selection Sort trova ripetutamente il minimo della regione non ordinata e lo aggiunge. Insertion Sort è adattivo e stabile; il Selection Sort standard non è adattivo e non è intrinsecamente stabile.

Riassumi questo post con: