Algoritmo di ordinamento: differenze tra le versioni

Versione delle 13:09, 21 feb 2023

Versione attuale delle 10:11, 10 gen 2025

(3 versioni intermedie di 3 utenti non mostrate)

Riga 6:

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

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

Riga 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"

Riga 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 362:

|| —

|| —

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

|- align="center"