L'ordinamento per inserimento è un semplice algoritmo di ordinamento che funziona nello stesso modo in cui ordiniamo le carte da gioco che abbiamo in mano.
Programma Python per l'ordinamento per inserimento
La funzione insertSort accetta un array arr come input. Innanzitutto calcola la lunghezza dell'array (n). Se la lunghezza è 0 o 1, la funzione restituisce immediatamente il risultato poiché un array con 0 o 1 elemento viene considerato già ordinato.
Per gli array con più di un elemento, la funzione procede con l'iterazione sull'array a partire dal secondo elemento. Prende l'elemento corrente (denominato chiave) e lo confronta con gli elementi nella parte ordinata dell'array che lo precedono. Se la chiave è più piccola di un elemento nella porzione ordinata, la funzione sposta quell'elemento a destra, creando spazio per la chiave. Questo processo continua finché non viene trovata la posizione corretta per la chiave, che viene quindi inserita in quella posizione.
L'esempio fornito dimostra il processo di ordinamento utilizzando l'algoritmo di ordinamento per inserimento. L'array iniziale [12, 11, 13, 5, 6] è soggetto alla funzione insertSort. Dopo l'ordinamento, l'array dovrebbe essere [5, 6, 11, 12, 13]. Il codice stampa l'array ordinato come output finale.
df loc
Pitone
strutture dati in Java
def> insertionSort(arr):> >n>=> len>(arr)># Get the length of the array> > >if> n <>=> 1>:> >return> # If the array has 0 or 1 element, it is already sorted, so return> >for> i>in> range>(>1>, n):># Iterate over the array starting from the second element> >key>=> arr[i]># Store the current element as the key to be inserted in the right position> >j>=> i>->1> >while> j>>=> 0> and> key # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)> |
>
>
Produzione:
Sorted array is: [5, 6, 11, 12, 13]>
Complessità temporale: O(N2)
Spazio ausiliario: O(1)
Si prega di fare riferimento all'articolo completo su Ordinamento per inserimento per ulteriori dettagli!