Raccomandato, 2022

Scelta Del Redattore

Differenza tra Insertion Sort e Selection Sort

L'ordinamento e l'ordinamento di selezione sono le tecniche utilizzate per ordinare i dati. L'ordinamento e l'ordinamento delle selezioni possono essere differenziati in base al metodo utilizzato per ordinare i dati. L'ordinamento di inserimento inserisce i valori in un file preordinato per ordinare un set di valori. D'altra parte, l'ordinamento di selezione trova il numero minimo dall'elenco e lo ordina in un certo ordine.

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 confrontoInserimento OrdinaSelezione 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
StabileInstabile
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 casoSopra)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

  1. L'ordinamento di inserimento di solito esegue l'operazione di inserimento. Al contrario, la selezione seleziona la selezione e il posizionamento degli elementi richiesti.
  2. L'ordinamento di inserzione si dice che sia stabile mentre l'ordinamento di selezione non è un algoritmo stabile.
  3. Nell'algoritmo di ordinamento degli inserimenti gli elementi sono precedentemente noti. Al contrario, l'ordinamento di selezione contiene in anticipo la posizione.
  4. 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.
  5. 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.

Top