Ci sono diversi algoritmi di base per risolvere il problema dell'ordinamento di un array. Uno dei più famosi tra questi è l'ordinamento per inserimento. Per la sua chiarezza e semplicità, ma a bassa efficienza, questo metodo viene utilizzato principalmente nella programmazione didattica. Ti permette di comprendere i meccanismi di smistamento di base.
Descrizione dell'algoritmo
L'essenza dell'algoritmo di ordinamento per inserimento è che un segmento correttamente ordinato viene formato all'interno dell'array iniziale. Ogni elemento viene confrontato uno ad uno con la parte spuntata e inserito al posto giusto. Pertanto, dopo aver ripetuto tutti gli elementi, si allineano nell'ordine corretto.
L'ordine di selezione degli elementi può essere qualsiasi, possono essere selezionati arbitrariamente o secondo un algoritmo. Molto spesso, l'enumerazione sequenziale viene utilizzata dall'inizio dell'array, dove si forma un segmento ordinato.
L'inizio dell'ordinamento potrebbe assomigliare a questo:
- Prendi il primo elemento dell'array.
- Dato che non c'è niente con cui confrontarlo, prendi l'elemento stesso come ordinatosequenza.
- Vai al secondo elemento.
- Confrontalo con il primo in base alla regola di ordinamento.
- Se necessario, scambia gli elementi in alcuni punti.
- Prendi i primi due elementi come una sequenza ordinata.
- Vai al terzo elemento.
- Confrontalo con il secondo, scambialo se necessario.
- Se viene effettuata la sostituzione, confrontala con la prima.
- Prendi tre elementi come sequenza ordinata.
E così via fino alla fine dell'array originale.
Ordinamento inserimento vita reale
Per chiarezza, vale la pena fornire un esempio di come questo meccanismo di smistamento viene utilizzato nella vita di tutti i giorni.
Prendi, ad esempio, un portafoglio. Banconote da cento, cinquecento e mille dollari giacciono in disordine nello scomparto delle banconote. Questo è un pasticcio, in un tale miscuglio è difficile trovare immediatamente il pezzo di carta giusto. La matrice delle banconote deve essere smistata.
La prima è una banconota da 1000 rubli e subito dopo - 100. Ne prendiamo cento e la mettiamo davanti. Il terzo consecutivo è di 500 rubli, il posto giusto è compreso tra cento e mille.
Allo stesso modo ordiniamo le carte ricevute quando giochiamo a "Fool" per facilitare la navigazione.
Operatori e funzioni di supporto
Il metodo di ordinamento per inserimento prende come input un array iniziale da ordinare, una funzione di confronto e, se necessario, una funzione che determina la regola per enumerare gli elementi. Più spesso usato inveceistruzione di ciclo regolare.
Il primo elemento è esso stesso un insieme ordinato, quindi il confronto inizia dal secondo.
L'algoritmo usa spesso una funzione di supporto per scambiare due valori (scambio). Utilizza una variabile temporanea aggiuntiva, che consuma memoria e rallenta un po' il codice.
Un' alternativa è spostare in massa un gruppo di elementi e quindi inserire quello corrente nello spazio libero. In questo caso, il passaggio all'elemento successivo avviene quando il confronto ha dato esito positivo, che indica l'ordine corretto.
Esempi di implementazione
L'implementazione specifica dipende in gran parte dal linguaggio di programmazione utilizzato, dalla sua sintassi e dalle sue strutture.
Implementazione C classica che utilizza una variabile temporanea per lo scambio di valori:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; matrice[j + 1]=matrice[j]; matrice[j]=temp; } }
Implementazione PHP:
funzione inserimento_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Qui, prima, tutti gli elementi che non corrispondono alla condizione di ordinamento vengono spostati a destra, quindi l'elemento corrente viene inserito nello spazio libero.
Codice Java usando il ciclo while:
public static void insertSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[Chiave precedente]; arr[prevKey]=currElem; prevKey--; } } }
Il significato generale del codice rimane invariato: ogni elemento dell'array viene confrontato in sequenza con i precedenti e scambiato con essi se necessario.
Tempo di esecuzione stimato
Ovviamente, nel migliore dei casi, l'input dell'algoritmo sarà un array già ordinato nel modo giusto. In questa situazione, l'algoritmo dovrà semplicemente controllare ogni elemento per assicurarsi che sia nel posto giusto senza fare scambi. Pertanto, il tempo di esecuzione dipenderà direttamente dalla lunghezza dell'array originale O(n).
L'input del caso peggiore è un array ordinato in ordine inverso. Ciò richiederà un gran numero di permutazioni, la funzione di runtime dipenderà dal numero di elementi al quadrato.
Il numero esatto di permutazioni per un array completamente non ordinato può essere calcolato usando la formula:
n(n-1)/2
dove n è la lunghezza dell'array originale. Pertanto, ci vorrebbero 4950 permutazioni per disporre 100 elementi nell'ordine corretto.
Il metodo di inserimento è molto efficiente per ordinare array piccoli o parzialmente ordinati. Tuttavia, non è consigliabile applicarlo ovunque a causa dell'elevata complessità dei calcoli.
L'algoritmo viene utilizzato come ausiliario in molti altri metodi di ordinamento più complessi.
Ordina valori uguali
L'algoritmo di inserimento appartiene ai cosiddetti ordinamenti stabili. Significa,che non scambia elementi identici, ma conserva il loro ordine originale. L'indice di stabilità è in molti casi importante per un ordine corretto.
Quello sopra è un ottimo esempio visivo di ordinamento per inserimento in una danza.
