Algoritmo di ordinamento: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
m Bot: fix citazione web (v. discussione) |
||
Riga 1:
Un '''algoritmo di ordinamento''' ({{en}} ''sorting algorithm'') è un [[algoritmo]] che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una [[relazione d'ordine]], in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due elementi dell'insieme): le relazioni d'ordine parziale danno origine agli algoritmi di [[ordinamento topologico]]. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente.
== Criteri di partizionamento ==
Riga 19:
=== Stabilità di un algoritmo ===<!-- Referenziata da "Sort (Unix)" -->
Un metodo di ordinamento si dice stabile se preserva l'ordine relativo dei dati con chiavi uguali all'interno del file da ordinare. Ad esempio se si ordina per anno di corso una lista di studenti già ordinata alfabeticamente un metodo stabile produce una lista in cui gli alunni dello stesso anno sono ancora in ordine alfabetico mentre un ordinamento instabile probabilmente produrrà una lista senza più alcuna traccia del precedente ordinamento.
La stabilità può essere forzata aggiungendo prima dell'ordinamento un piccolo indice a ciascuna chiave o allungando in qualche altro modo le chiavi sulle quali operare, in modo da renderle univoche preservando l'informazione sulla posizione relativa degli elementi.
Riga 60:
=== Albero di copertura ===
Ogni operazione dell'algoritmo di ordinamento può essere analizzata tramite un [[albero binario]] di copertura. Per ordinare una sequenza di n elementi bisognerà effettuare un numero di operazioni pari all'altezza minima di un albero binario con k foglie:
<math>h(T) \geq \lceil\log k\rceil</math>
Riga 262:
|| —
|| —
|- align="center"
Line 273 ⟶ 272:
|| —
|| —
|- align="center"
Line 333 ⟶ 331:
|| Sì
|| Sì
|| A. per confronto tramite scambio di elementi, miglioria del ''[[Bubble sort]]''. Noto anche come ''[[Cocktail sort]]''
|- align="center"
Line 409 ⟶ 407:
* {{en}} [[Donald Knuth|D. E. Knuth]], ''[[The Art of Computer Programming]], Volume 3: Sorting and Searching''.
* [http://epaperpress.com/sortsearchItalian/index.html Una breve guida] agli algoritmi di ordinamento e ricerca
* {{
* {{
* {{
* [h**p://www.massimop.eu/?page_id=103 Applet Java che mostra l'ordinamento di array con alcuni algoritmi diversi e varie modalità di esecuzione - OFFLINE]
*
== Altri progetti ==
| |||