Ordinamento di inserimento: algoritmo con C, C++, Java, Python Esempi
Sara Chen
Cos'è l'ordinamento per inserzione?
L'ordinamento per inserimento è uno degli algoritmi di ordinamento per confronto utilizzati per ordinare gli elementi eseguendo l'iterazione su un elemento alla volta e posizionando l'elemento nella posizione corretta.
Ogni elemento viene inserito in sequenza in una lista già ordinata. La dimensione dell'elenco già ordinato inizialmente è uno. L'algoritmo di ordinamento per inserimento garantisce che i primi k elementi vengano ordinati dopo la kesima iterazione.
Caratteristiche dell'algoritmo di ordinamento per inserzione
L'algoritmo per l'ordinamento per inserimento presenta le seguenti importanti caratteristiche:
- È una tecnica di ordinamento stabile, quindi non modifica l'ordine relativo degli elementi uguali.
- È efficiente per set di dati più piccoli ma non efficace per elenchi più grandi.
- L'ordinamento di inserimento è adattivo e riduce il numero totale di passaggi se viene ordinato parzialmente. Italia viene fornito come input per renderlo efficiente.
Come funziona Insert Operalavoro?
Nell'algoritmo di ordinamento di inserimento, l'operazione di inserimento viene utilizzata per ordinare gli elementi non ordinati. Aiuta a inserire un nuovo elemento in un elenco già ordinato.
Pseudocodice dell'operazione di inserimento:
Consideriamo una lista A di N elementi.
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
Nell'esempio sopra riportato si vuole inserire un nuovo elemento 6 in una lista già ordinata.
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 troviamo che A[3] > A[4], invertiamo nuovamente la posizione di 6 e 8.
Passo 3) Ora confronta A[3] e A[2], poiché A[2] > A[3] scambia la posizione di 7 e 6.
Passo 4) Confrontiamo A[1] e A[2] e poiché A[1] < A[2], cioè l'elemento adiacente sinistro non è più maggiore. Ora concludiamo che 6 è inserito correttamente e interrompiamo qui l'algoritmo.
Come funziona l'ordinamento per inserimento
L'operazione di inserimento discussa sopra è la spina dorsale dell'ordinamento per inserzione. La procedura di inserimento viene eseguita su ogni elemento e alla fine otteniamo l'elenco ordinato.
La figura di esempio sopra mostra il funzionamento dell'ordinamento per inserimento nella struttura dei dati. Inizialmente, nella sottolista ordinata è presente un solo elemento, ovvero 4. Dopo aver inserito A[1], ovvero 3, la dimensione della sottolista ordinata aumenta fino a 2.
C++ Programma per l'ordinamento per inserimento
#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
Codice C per l'ordinamento di inserzione
#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
#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 le proprietà importanti dell'ordinamento per inserzione:
- In linea: L'ordinamento per inserzione può ordinare gli elementi man mano che riceve. Cioè, se abbiamo già ordinato un elenco di elementi e aggiungiamo altri elementi agli elenchi, non avremo bisogno di eseguire nuovamente l'intera procedura di ordinamento. Dobbiamo invece eseguire l'iterazione solo sugli elementi appena aggiunti.
- A posto: La complessità spaziale dell'algoritmo di ordinamento per inserimento è costante e non richiede spazio extra. Questo algoritmo ordina gli elementi sul posto.
- Stabile: Nell'ordinamento per inserzione, non scambiamo gli elementi se i loro valori sono uguali. Ad esempio, due elementi, x e y, sono uguali e x appare prima di y negli elenchi non ordinati, quindi nell'elenco ordinato x apparirà prima di y. Ciò rende stabile l'ordinamento per inserzione.
- Adattivo: A algoritmo di ordinamento è adattivo se richiede meno tempo se gli elementi di input o il sottoinsieme di elementi sono già ordinati. Come discusso in precedenza, il tempo di esecuzione migliore per l'ordinamento per inserzione è O(N) e il tempo di esecuzione peggiore è O(N^2). L'ordinamento per inserzione è uno degli algoritmi di ordinamento adattivo.
Complessità dell'ordinamento per inserimento
Complessità spaziale
L'ordinamento per inserimento non richiede spazio extra per ordinare gli elementi, la complessità dello spazio è costante, ovvero O(1).
Complessità temporale
Poiché l'ordinamento per inserimento itera ogni elemento simultaneamente, richiede N-1 passaggi per ordinare N elementi. Per ogni passaggio, può effettuare zero scambi se gli elementi sono già ordinati, o scambiare 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.
- Gli swap massimi totali sono (1+2+3+4+..+N) i. N(N+1)/2, la peggiore complessità temporale è O(N^2).
Ecco l'importante complessità temporale dell'ordinamento per inserimento:
- Complessità del caso peggiore: O(n2): ordinare un array in ordine decrescente quando è in ordine crescente è lo scenario peggiore.
- migliore Complessità del caso: O(n): migliori Case Complexity si verifica quando l'array è già ordinato, il ciclo esterno viene eseguito per n volte mentre il ciclo interno non viene eseguito affatto. Ci sono solo n confronti. Quindi, in questo caso, la complessità è lineare.
- Complessità media del caso: O(n2): accade quando gli elementi di un array si presentano in ordine confuso, che non è né ascendente né discendente.
Sintesi
- L'ordinamento per inserzione è un metodo di algoritmo di ordinamento basato sul confronto.
- È una tecnica di ordinamento stabile, quindi non modifica l'ordine relativo degli elementi uguali.
- Su ogni elemento, l'operazione di inserimento viene utilizzata per inserire l'elemento nel sottoelenco ordinato.
- L'ordinamento per inserzione è un algoritmo di ordinamento sul posto.
- La complessità temporale peggiore e media dell'ordinamento per inserimento è quadratica, ovvero O(N^2).
- L'ordinamento per inserimento non richiede spazio ausiliario.
