Struttura dei dati - Tecniche di ordinamento
L'ordinamento si riferisce alla disposizione dei dati in un formato particolare. L'algoritmo di ordinamento specifica il modo in cui disporre i dati in un ordine particolare. Gli ordini più comuni sono in ordine numerico o lessicografico.
L'importanza dell'ordinamento risiede nel fatto che la ricerca dei dati può essere ottimizzata a un livello molto alto, se i dati vengono memorizzati in modo ordinato. L'ordinamento viene utilizzato anche per rappresentare i dati in formati più leggibili. Di seguito sono riportati alcuni esempi di ordinamento in scenari di vita reale:
Telephone Directory - La rubrica telefonica memorizza i numeri di telefono delle persone ordinate per nome, in modo che i nomi possano essere cercati facilmente.
Dictionary - Il dizionario memorizza le parole in ordine alfabetico in modo che la ricerca di qualsiasi parola diventi facile.
Ordinamento sul posto e Ordinamento non sul posto
Gli algoritmi di ordinamento possono richiedere uno spazio aggiuntivo per il confronto e l'archiviazione temporanea di pochi elementi di dati. Questi algoritmi non richiedono spazio aggiuntivo e si dice che l'ordinamento avvenga sul posto o, ad esempio, all'interno dell'array stesso. Questo è chiamatoin-place sorting. Bubble sort è un esempio di ordinamento sul posto.
Tuttavia, in alcuni algoritmi di ordinamento, il programma richiede uno spazio maggiore o uguale agli elementi da ordinare. Viene chiamato l'ordinamento che utilizza uno spazio uguale o maggiorenot-in-place sorting. Merge-sort è un esempio di ordinamento non sul posto.
Ordinamento stabile e non stabile
Se un algoritmo di ordinamento, dopo aver ordinato i contenuti, non cambia la sequenza di contenuti simili in cui compaiono, viene chiamato stable sorting.
Se un algoritmo di ordinamento, dopo aver ordinato i contenuti, cambia la sequenza di contenuti simili in cui compaiono, viene chiamato unstable sorting.
La stabilità di un algoritmo è importante quando desideriamo mantenere la sequenza di elementi originali, come ad esempio in una tupla.
Algoritmo di ordinamento adattivo e non adattivo
Un algoritmo di ordinamento si dice che sia adattivo, se si avvale di elementi già "ordinati" nell'elenco che deve essere ordinato. Cioè, durante l'ordinamento se l'elenco di origine ha qualche elemento già ordinato, gli algoritmi adattivi ne terranno conto e proveranno a non riordinarli.
Un algoritmo non adattivo è quello che non tiene conto degli elementi che sono già ordinati. Cercano di forzare il riordino di ogni singolo elemento per confermare la loro ordinamento.
Termini importanti
Alcuni termini sono generalmente coniati durante la discussione delle tecniche di ordinamento, ecco una breve introduzione ad essi:
Ordine crescente
Si dice che sia presente una sequenza di valori increasing order, se l'elemento successivo è maggiore del precedente. Ad esempio, 1, 3, 4, 6, 8, 9 sono in ordine crescente, poiché ogni elemento successivo è maggiore dell'elemento precedente.
Ordine decrescente
Si dice che sia presente una sequenza di valori decreasing order, se l'elemento successivo è minore di quello corrente. Ad esempio, 9, 8, 6, 4, 3, 1 sono in ordine decrescente, poiché ogni elemento successivo è minore dell'elemento precedente.
Ordine non crescente
Si dice che sia presente una sequenza di valori non-increasing order, se l'elemento successivo è minore o uguale al suo elemento precedente nella sequenza. Questo ordine si verifica quando la sequenza contiene valori duplicati. Ad esempio, 9, 8, 6, 3, 3, 1 sono in ordine non crescente, poiché ogni elemento successivo è minore o uguale a (nel caso di 3) ma non maggiore di qualsiasi elemento precedente.
Ordine non decrescente
Si dice che sia presente una sequenza di valori non-decreasing order, se l'elemento successivo è maggiore o uguale al suo elemento precedente nella sequenza. Questo ordine si verifica quando la sequenza contiene valori duplicati. Ad esempio, 1, 3, 3, 6, 8, 9 sono in ordine non decrescente, poiché ogni elemento successivo è maggiore o uguale a (nel caso di 3) ma non inferiore al precedente.