Discussione:Algoritmo di ordinamento

	Questa voce rientra tra gli argomenti trattati dal progetto tematico sottoindicato. Puoi consultare le discussioni in corso, aprirne una nuova o segnalarne una avviata qui.
Informatica bar di progetto monitoraggio voci

	La voce è stata parzialmente monitorata, completa la valutazione.
nc Nessuna informazione sull'accuratezza dei contenuti. (che significa?) nc Nessuna informazione sulla scrittura. (che significa?) nc Nessuna informazione sulla presenza di fonti. (che significa?) D Gravi problemi relativi alla dotazione di immagini e altri supporti grafici nella voce. Mancano molti file importanti per la comprensione del tema, alcuni essenziali. (che significa?)

Algoritmo di ordinamento
Argomento di scuola secondaria di II grado
Materia	informatica
Dettagli
Dimensione della voce	14 738 byte
Progetto Wikipedia e scuola italiana

Tabella

Io sarei per una proposta di modifica della tabella. Io modiificherei la tabella non indicando lo spazio in memoria ma la velocità nei vari casi di ordinare il vettore o quel che sia. Se non ricordo male il Merge sort dovrebbe essere (non ne sono sicuro) n*log(n)con n come numero di elementi. Questa tabella sarebbe utile a chiunque voglia creare un programma con ordinamento tenendo conto dei costi di tempo. Melknix

complessità di tempo

Sono d'accordo, ormai la valutazione dell'efficienza di un algoritmo è soprattutto una questione di tempo più che di spazio (dato l'evidente abbassamento dei costi delle memorie). Va da sè che resterà preferito un algoritmo che ordini in place (come quick sort), ma nella tabella andrebbe indicata la complessità di tempo.

Ho aggiunto la complessità temporale al caso pessimo medio e ottimo nonché la memoria aggiuntiva richiesta e la stabilità per gli algoritmi già presenti nelle pagine della wiki. Le informazioni provengono dalla pagina in inglese. Quando avrò un po' di tempo aggiungerò anche gli altri. Oppure può farlo qualche altro wikipediano :-) Beren023 14:54, 3 feb 2007 (CET)

Correzione della tabella

A mio avviso la tabella contenente gli algoritmi di ordinamento per confronto andrebbe rivista e corretta.Contiene infatti al suo interno degli algoritmi che non si basano sul confronto degli elementi della sequenza da ordinare,ma su altre procedure; quelli che finora ho riconosciuto sono: Integer Sort,Radix Sort e Bucket Sort. Questi infatti sono ordinamenti definiti lineari perchè la loro complessità è proprio O(n)...da questo si evince che ovviamente non possono basarsi su confronti visto che è dimostrato che il lower bound per algoritmi che si basano su questi ultimi è O(n*logn).--Goradan 14:54, 12 giu 2007 (CEST)

La tabella contiene un elenco di algoritimi di ordinamento che non si basano sul confronto (Es. counting sort), quindi è opportuno modificare l'intestazione della tabella da "algoritmi di ordinamento per confronto" a "algoritmi di ordinamento" oppure suddividere la tabella.--Emanuele.buchicchio 23:48, 4 gen 2008 (CET)

altezza di un albero binario

Dato un albero binario non vuoto, se, come detto nell'articolo siamo in presenza di n! nodi-foglia, allora l'altezza di tale albero è ALMENO log(n!) e non AL PIU'. Peraltro, subito dopo l'articolo si contraddice, perchè torna sulla retta via mettendo il maggioreuguale, come giusto che sia. Mi sbaglio?

Andrea Stoppa Unipd 504313

Insertion Sort

Ho notato che nella tabella l'Insertion Sort compare con una complessità di O(n+d) nel caso medio, ma non ho trovato alcun riferimento a cosa sia quella d. Qualcuno ha idea?

Edit: Ho notato lo stesso problema con alcuni degli algoritmi di ordinamento non per confronto. Cos'è la s del Radix Sort?

Ordinamento delle righe nella tabella "elenco degli algoritmi di ordinamento"

Penso che l'ordinamento crescente/decrescente delle righe che viene effettuato cliccando sull'intestazione delle colonne nella tabella "elenco degli algoritmi di ordinamento" generi molta confusione sulle colonne "Migliore", "Medio", "Peggiore" e "Memoria" in quanto l'utente si aspetta che ordinando le righe queste vengano ordinate per efficienza, mentre invece l'ordine mi sembra sia alfabetico. --Andrea Gobetti (msg) 16:56, 24 ott 2015 (CEST)

Imprecisione nel paragrafo "altezza"

Segnalo che, all'interno della dimostrazione del paragrafo "altezza", è presente un'imprecisione nella dimostrazione del teorema riportato: n! è il numero di nodi-foglia dell'albero, non di tutti i nodi. --Platnum97 (msg) 19:16, 11 lug 2017 (CEST)