L'ordinamento è un'operazione di base in cui gli elementi di un array sono disposti in un ordine specifico per migliorarne la ricercabilità. In parole semplici, i dati sono ordinati in modo tale da poter essere facilmente cercati.
Grafico comparativo
| Base per il confronto | Inserimento Ordina | Selezione Ordina |
|---|---|---|
| Di base | I dati vengono ordinati inserendo i dati in un file ordinato esistente. | I dati vengono ordinati selezionando e posizionando gli elementi consecutivi nella posizione ordinata. |
| Natura | Stabile | Instabile |
| Processo da seguire | Gli elementi sono noti in anticipo mentre viene cercata la posizione per posizionarli. | La posizione è nota in precedenza mentre gli elementi vengono cercati. |
| Dati immediati | L'ordinamento di inserzione è una tecnica di ordinamento in tempo reale che può gestire dati immediati. | Non può gestire dati immediati, deve essere presente all'inizio. |
| La migliore complessità del caso | Sopra) | O (n 2 ) |
Definizione di Insertion Sort
L'ordinamento di inserimento funziona inserendo l'insieme di valori nel file ordinato esistente. Costruisce l'array ordinato inserendo un singolo elemento alla volta. Questo processo continua finché l'intero array non viene ordinato in un determinato ordine. L'idea principale alla base dell'inserzione sort è quella di inserire ciascun elemento nella sua posizione appropriata nell'elenco finale. Il metodo di ordinamento per inserimento consente di risparmiare una quantità effettiva di memoria.
Funzionamento dell'ordinamento Insertion
- Utilizza due serie di array in cui si memorizzano i dati ordinati e altri su dati non ordinati.
- L'algoritmo di ordinamento funziona finché non ci sono elementi nel set non ordinato.
- Supponiamo che ci siano elementi "n" nella matrice. Inizialmente, l'elemento con indice 0 (LB = 0) esiste nel set ordinato. Gli elementi rimanenti si trovano nella partizione non ordinata dell'elenco.
- Il primo elemento della parte non ordinata ha indice di matrice 1 (Se LB = 0).
- Dopo ogni iterazione, sceglie il primo elemento della partizione non ordinata e lo inserisce nella posizione corretta nel set ordinato.
Vantaggi dell'inserzione sort
- Facilmente implementato e molto efficiente se utilizzato con insiemi di dati di piccole dimensioni.
- Il requisito di spazio di memoria aggiuntivo per l'ordinamento di inserimento è inferiore (ad esempio, O (1)).
- È considerata una tecnica di ordinamento dal vivo in quanto l'elenco può essere ordinato man mano che i nuovi elementi vengono ricevuti.
- È più veloce di altri algoritmi di ordinamento.
Esempio :
Definizione di selezione Ordina
L' ordinamento Selezione esegue l'ordinamento cercando il numero del valore minimo e posizionandolo nella prima o nell'ultima posizione in base all'ordine (crescente o decrescente). Il processo di ricerca della chiave minima e il suo posizionamento nella posizione corretta viene continuato fino a quando tutti gli elementi sono posizionati nella giusta posizione.
Funzionamento della selezione Ordina
- Supponiamo che un array ARR con N elementi nella memoria.
- Nel primo passaggio, viene cercata la chiave più piccola insieme alla sua posizione, quindi ARR [POS] viene scambiato con ARR [0]. Pertanto, ARR [0] è ordinato.
- Nel secondo passaggio, di nuovo la posizione del valore più piccolo viene determinata nel sottoarray degli elementi N-1. Intercambiare l'ARR [POS] con ARR [1].
- Nel passaggio N-1, viene eseguita la stessa procedura per ordinare il numero N di elementi.
Esempio :
Differenze chiave tra ordinamento di inserimento e ordinamento di selezione
- L'ordinamento di inserimento di solito esegue l'operazione di inserimento. Al contrario, la selezione seleziona la selezione e il posizionamento degli elementi richiesti.
- L'ordinamento di inserzione si dice che sia stabile mentre l'ordinamento di selezione non è un algoritmo stabile.
- Nell'algoritmo di ordinamento degli inserimenti gli elementi sono precedentemente noti. Al contrario, l'ordinamento di selezione contiene in anticipo la posizione.
- L'ordinamento di inserimento è una tecnica di ordinamento in tempo reale in cui gli elementi in arrivo vengono immediatamente ordinati nell'elenco mentre l'ordinamento di selezione non può funzionare correttamente con i dati immediati.
- L'ordinamento di inserimento ha il tempo di esecuzione O (n) nel migliore dei casi. Per contro, la complessità del tempo di esecuzione del caso migliore è O (n2).
Complessità dell'inserzione sort
La migliore complessità del caso dell'inserimento sort è O (n) volte, cioè quando l'array viene ordinato in precedenza. Allo stesso modo, quando l'array viene ordinato in ordine inverso, il primo elemento dell'array non ordinato deve essere confrontato con ciascun elemento nel set ordinato. Quindi, nel peggiore dei casi, il tempo di esecuzione dell'ordinamento Insertion è quadratico, ovvero O (n2) . In media, deve anche fare il minimo (k-1) / 2 confronti. Quindi, il caso medio ha anche il tempo di esecuzione quadratico O (n2).
Complessità della selezione Ordina
Poiché il lavoro di selezione, l'ordinamento non dipende dall'ordine originale degli elementi dell'array, quindi non c'è molta differenza tra il caso migliore e la complessità del caso peggiore dell'ordinamento di selezione.
L'ordinamento selezione seleziona l'elemento valore minimo, nel processo di selezione viene scansionato tutto il numero 'n' di elementi; quindi i confronti n-1 sono fatti nel primo passaggio. Quindi, gli elementi vengono scambiati. Allo stesso modo, nel secondo passaggio, anche per trovare il secondo elemento più piccolo, è necessario eseguire la scansione degli elementi rest n-1 e il processo viene proseguito finché l'intero array non viene ordinato.
Pertanto, la complessità del tempo di esecuzione dell'ordinamento di selezione è O (n2) .
= (n-1) + (n-2) + ......... .. + 2 + 1
= n (n-1) / 2 = O (n2)
Conclusione
Tra entrambi gli algoritmi di ordinamento, l'ordinamento di inserimento è veloce, efficiente, stabile mentre l'ordinamento di selezione funziona solo in modo efficiente quando è coinvolto il piccolo insieme di elementi o l'elenco è parzialmente ordinato in precedenza. Il numero di confronti effettuati per tipo di selezione è maggiore dei movimenti eseguiti mentre nell'inserimento ordina il numero di volte in cui un elemento viene spostato o scambiato è maggiore dei confronti effettuati.
