Algoritmo di ordinamento: differenze tra le versioni

Versione delle 10:37, 21 mag 2019

Versione attuale delle 10:11, 10 gen 2025

(22 versioni intermedie di 17 utenti non mostrate)

Riga 1:

[[File:Sorting stability playing cards.svg|thumb|alt=Un esempio di ordinamento stabile sulle carte da gioco. |Un esempio di ordinamento stabile sulle carte da gioco.]]

Un '''algoritmo di ordinamento''' ({{en}} ''sorting algorithm'') è un [[algoritmo]] che viene utilizzato per elencareposizionare 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'ordineessa 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 ==

Per analizzare e studiare gli algoritmi di ordinamento sono stati definiti differenti criteri di partizionamento, analizzati qui di seguito.

=== Ordinamento interno e ordinamento esterno ===

Se il file da ordinare, o la [[struttura dati]], può essere contenuto in memoria, il metodo viene detto interno. L'ordinamento di file residenti su disco o su nastro viene chiamato ordinamento esterno: la differenza principale tra i due tipi di ordinamento sta nel fatto che mentre nel primo è possibile accedere direttamente a un record, nel secondo i record devono essere indirizzati in modo sequenziale o al più per grandi blocchi.

Se il file da ordinare, o la struttura dati, può essere contenuto in memoria, il metodo viene detto interno. L'ordinamento di file residenti su disco o su nastro viene chiamato ordinamento esterno: la differenza principale tra i due tipi di ordinamento sta nel fatto che mentre nel primo è possibile accedere direttamente a un record, nel secondo i record devono essere indirizzati in modo sequenziale o al più per grandi blocchi.

=== Ordinamento per confronti-scambi e digitale ===

A seconda del tipo di operazione che viene effettuata, si hanno due differenti tipi di ordinamento.: Ll'ordinamento che effettua confronti e scambi (<math>a \leq b : exch(a,b)</math>) e l'algoritmo digitale che accede all'informazione tramite un gruppo di bit alla volta.

A seconda del tipo di operazione che viene effettuata, si hanno due differenti tipi di ordinamento. L'ordinamento che effettua confronti e scambi (<math>a \leq b : exch(a,b)</math>) e l'algoritmo digitale che accede all'informazione tramite un gruppo di bit alla volta.

=== Ordinamento adattivo ===

Solitamente un algoritmo di ordinamento sfrutta operazioni di confronto e scambio. Se tali operazioni vengono svolte in modo indipendente dai dati di input l'algoritmo viene definito non adattivo. Mentre se un metodo di ordinamento esegue diverse sequenze di operazioni in funzione del risultato dei confronti si ha un algoritmo adattivo.

=== Stabilità di un algoritmo ===<!-- Referenziata da "Sort (Unix)" -->

Solitamente un algoritmo di ordinamento sfrutta operazioni di confronto e scambio. Se tali operazioni vengono svolte in modo indipendente dai dati di input l'algoritmo viene definito non adattivo. Mentre se un metodo di ordinamento esegue diverse sequenze di operazioni in funzione del risultato dei confronti si ha un algoritmo adattivo.

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.

sina

=== Algoritmi in place ===

Un algoritmo si dice [[Algoritmo in loco|algoritmo ''in place'']] quando non crea una copia dell'input per raggiungere l'obiettivo, l'ordinamento in questo caso. Pertanto un algoritmo in place risparmia memoria rispetto ad un algoritmo non in place. Si noti infatti che, malgrado le considerazioni fatte sulla complessità abbiano senso in generale, hanno una rilevanza decisiva sui grandi numeri. Allo stesso modo della proprietà di essere o meno in place.

== Relazioni d'ordine e chiavi ==

La relazione d'ordine che intercorre tra gli elementi dell'insieme può essere:

* quella naturale (se esiste) per l'insieme preso in considerazione (ad esempio la relazione di <=math>\le</math> per sottoinsiemi dei numeri naturali)

* una relazione definita dalle necessità dell'applicazione.

Riga 39 ⟶ 37:

=== Dimostrazione ===

Si vuole dimostrare che in un algoritmo '''confronti e scambi''' la complessità è <math>\mathsf \Omega( n\log n)</math>. Data in input una sequenza <math>e_1, e_2, ... e_n</math> di n elementi, l'azione dell'algoritmo si può rappresentare come un albero binario, per ogni sequenza di ingresso ci sarà un cammino all'interno dell'albero, questo perché si ha una permutazione delle sequenze, infatti il numero di permutazioni possibili su n elementi sono <math>n!</math> combinazioni che corrispondono al numero di foglie dell'albero.

Riga 55 ⟶ 52:

=== 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:

Riga 63 ⟶ 59:

Vi sono varie classi di algoritmi di ordinamento, i più noti ed utilizzati sono gli algoritmi di ordinamento per confronto (''comparison sort algorithms''), ma esistono altre classi caratterizzate da un tempo di esecuzione nel caso peggiore inferiore a O(''n''log''n'').

Nella tabella seguente sono elencati alcuni algoritmi di ordinamento, riportandone la complessità al caso ''Migliore'', ''Medio'' e ''Peggiore'', la ''memoria aggiuntiva richiesta'', e la ''stabilità''. Si utilizzano due convenzioni nella tabella: gli algoritmi sono implementati su [[array]] di chiavi intere; la [[Teoria della complessità computazionale|complessità computazionale]] degli algoritmi di ordinamento per confronti è derivante unicamente dal numero di confronti effettuati.

{|class="wikitable sortable"

!|Nome || class="unsortable" | Migliore || class="unsortable" | Medio || class="unsortable" | Peggiore || class="unsortable" | Memoria || Stabile || ''In place'' || Note

|- align="center"

Riga 80 ⟶ 76:

|- align="center"

|| [[Bubble sort]]

|| OΘ(''n'')

|| OΘ(''n''²)

|| OΘ(''n''²)

|| Θ(1)

|| Sì

Riga 90 ⟶ 86:

|- align="center"

|| [[B sort]]

|| —

|| —

|| —

|| —

|| —

|| —

|| —

|- align="center"

|| [[B-Tree sort]]

|| —

|| —

Riga 170 ⟶ 156:

|- align="center"

|| [[Insertion sort]]

|| OΘ(''n'')

|| OΘ(''n''+''d''²)

|| OΘ(''n''²)

|| Θ(1)

|| Sì

Riga 180 ⟶ 166:

|- align="center"

|| [[Counting sort]]

|| OΘ(''n''+''k'')

|| OΘ(''n''+''k'')

|| OΘ(''n''+''k'')

|| O(''k'')

|| Sì

Riga 211 ⟶ 197:

|- align="center"

|| [[Merge sort]]

|| OΘ(''n''log''n'')

|| OΘ(''n''log''n'')

|| OΘ(''n''log''n'')

|| O(''n'')

|| Sì

Riga 271 ⟶ 257:

|- align="center"

|| [[Quicksort]]

|| OΘ(''n''log''n'')

|| OΘ(''n''log''n'')

|| O(''n''²)

|| O(''n'')

Riga 301 ⟶ 287:

|- align="center"

|| [[Selection sort]]

|| OΘ(''n''²)

|| OΘ(''n''²)

|| OΘ(''n''²)

|| Θ(1)

|| No

Riga 366 ⟶ 352:

|| Si

|| Si

|| A. non basato sul confronto. ''k'' è uguale a ''max(A)'', dove ''A'' è l'array. L'algoritmo necessità di un processo parallelo indipendente per ogni elemento dell'array.

|- align="center"

Riga 376 ⟶ 362:

|| —

|| —

|| A. per confronto tramite unione di componenti, miglioria dell{{'}}''[[Heap sort]]''

|- align="center"

Riga 397 ⟶ 383:

|| Sì

|| A. per confronto tramite partizionamento, di tipo ricorsivo. Le sue varianti possono essere stabili

|}

== Bibliografia ==

== Collegamenti esterni e bibliografia ==

* {{en}} [[Donald Knuth|D. E. Knuth]], ''[[The Art of Computer Programming]], Volume 3: Sorting and Searching''.

== Altri progetti ==

{{interprogetto|preposizione=sugli|etichetta=algoritmi di ordinamento}}

== Collegamenti esterni e bibliografia ==

* {{Collegamenti esterni}}

* [http://epaperpress.com/sortsearchItalian/index.html Una breve guida] agli algoritmi di ordinamento e ricerca

* {{cita web|1=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm|2=Spiegazione e analisi di molti algoritmi|lingua=en|accesso=27 novembre 2005|dataarchivio=13 dicembre 2012|urlarchivio=https://web.archive.org/web/20121213233414/http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm|urlmorto=sì}}

* {{cita web|http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html|Applet Java che mostra graficamente il funzionamento di alcuni algoritmi|lingua=en}}

* {{cita web|http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm|Corso sugli algoritmi reso gratuitamente disponibile on line dal MIT. Varie lezioni trattano di algoritmi di ordinamento|lingua=en}}

* [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]

* {{cita web|http://www.simplesoft.it/algoritmi-di-ordinamento-in-java.html|Una guida sugli algoritmi di ordinamento in java, con l'ausilio di un Applet che mostra graficamente l'ordinamento di un array}}

== Altri progetti ==

{{interprogetto|commons=Category:Sort algorithms}}

{{Ordinamento}}