Algoritmo di ordinamento degli inserimenti

In questo tutorial imparerai come funziona l'ordinamento per inserzione. Inoltre, troverai esempi funzionanti di ordinamento per inserzione in C, C ++, Java e Python.

L'ordinamento per inserzione funziona in modo simile allo smistamento delle carte in mano in un gioco di carte.

Partiamo dal presupposto che la prima carta sia già ordinata, quindi selezioniamo una carta non ordinata. Se la carta non ordinata è più grande della carta in mano, viene posizionata a destra, altrimenti a sinistra. Allo stesso modo, altre carte non ordinate vengono prese e messe al posto giusto.

Un approccio simile viene utilizzato dall'ordinamento per inserzione.

L'ordinamento di inserzione è un algoritmo di ordinamento che posiziona un elemento non ordinato nella posizione appropriata in ogni iterazione.

Come funziona l'ordinamento di inserzione?

Supponiamo di dover ordinare il seguente array.

Matrice iniziale

1. Si presume che il primo elemento dell'array sia ordinato. Prendi il secondo elemento e conservalo separatamente key.
   Confronta keycon il primo elemento. Se il primo elemento è maggiore di key, la chiave viene posizionata davanti al primo elemento. Se il primo elemento è maggiore della chiave, la chiave viene posizionata davanti al primo elemento.
2. Ora, i primi due elementi sono ordinati.
   Prendi il terzo elemento e confrontalo con gli elementi alla sua sinistra. Posizionato appena dietro l'elemento più piccolo di esso. Se non è presente alcun elemento più piccolo di esso, posizionalo all'inizio della matrice. Posiziona 1 all'inizio
3. Allo stesso modo, posiziona ogni elemento non ordinato nella posizione corretta. Posiziona 4 dietro 1 Posiziona 3 dietro 1 e la matrice viene ordinata

Algoritmo di ordinamento degli inserimenti

 insertionSort (array) segna il primo elemento come ordinato per ogni elemento non ordinato X 'estrae' l'elemento X per j X sposta l'elemento ordinato a destra di 1 loop di interruzione e inserisci X qui end insertionSort

Esempi di Python, Java e C / C ++

Python Java C C ++

 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)

  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )

 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Complessità

Complessità temporali

• Complessità caso peggiore: supponiamo che un array sia in ordine crescente e che tu voglia ordinarlo in ordine decrescente. In questo caso, si verifica la peggiore complessità. Ogni elemento deve essere confrontato con ciascuno degli altri elementi così, per ogni ennesimo elemento, viene effettuato il numero di confronti. Pertanto, il numero totale di confronti =O(n2)

(n-1)
n*(n-1) ~ n2
• Complessità caso migliore: O(n)
  quando l'array è già ordinato, il ciclo esterno viene eseguito per un ncerto numero di volte mentre il ciclo interno non viene eseguito affatto. Quindi, ci sono solo un nnumero di confronti. Quindi, la complessità è lineare.
• Complessità case media: si verifica quando gli elementi di un array sono in ordine confuso (né ascendente né discendente).O(n2)

Complessità spaziale

La complessità dello spazio è O(1)dovuta al fatto che keyviene utilizzata una variabile aggiuntiva .

Applicazioni di ordinamento per inserzione

L'ordinamento per inserzione viene utilizzato quando:

• l'array ha un numero limitato di elementi
• sono rimasti solo pochi elementi da ordinare