Quicksort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
FrescoBot (discussione | contributi)
m Bot: numeri di pagina nei template citazione e modifiche minori
fix typo: articolo sbagliato
 
(2 versioni intermedie di 2 utenti non mostrate)
Riga 5:
| didascalia = Quicksort in esecuzione su una lista di numeri. La linea blu è il valore del [[Pivot (matematica)|pivot]].
| struttura dati = Variabile
| tempo = <math>\ThetaO(n^2)</math>
| tempo medio = <math>\Theta(n\log_2 n)</math> confronti
| tempo migliore = <math>\ThetaOmega(n\log_2 n)</math>
| spazio = Dipende dalle implementazioni
| ottimale = Spesso
Riga 13:
'''Quicksort''' è un [[algoritmo di ordinamento]] [[Algoritmo ricorsivo|ricorsivo]] [[Algoritmo in loco|in place]] non [[Algoritmo di ordinamento#Stabilit.C3.A0 di un algoritmo|stabile]]. E come l'algoritmo di ordinamento [[Merge sort|Mergesort]] basa il suo funzionamento sul paradigma del "''Divide et Impera''<ref>{{Cita web|lingua=it|url=https://www.freecodecamp.org/italian/news/gli-algoritmi-divide-et-impera/|titolo=Gli algoritmi Divide et Impera|sito=freeCodeCamp.org|data=21 luglio 2022|accesso=29 gennaio 2025}}</ref>"; ovvero sulla scomposizione del problema in più sottoproblemi di taglia minore<ref name="geeksforgeeks.org">{{Cita web|lingua=en|url=https://www.geeksforgeeks.org/quick-sort-algorithm/|titolo=Quick Sort|sito=GeeksforGeeks|data=7 gennaio 2014|accesso=29 gennaio 2025}}</ref>.
 
In generale il la logica dell'algoritmo può essere riassunta in questo modo<ref name="geeksforgeeks.org"/>:
 
# '''Scelta del pivot:'''
Riga 138:
Per lo studio nel caso medio si valuta il numero medio di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo, determinando di conseguenza l'ordine di grandezza del tempo medio di calcolo necessario per eseguire la procedura.
 
La complessità dell'algoritmo in questo caso è <math>O (n \log_2 (n))</math>, precisamente <math display="inline">1.39\ n \log_2(n)</math>.
 
=== Caso migliore ===
 
Il caso migliore si verifica quando l'algoritmo di partizionamento determina due sottoproblemi perfettamente bilanciati, entrambi di dimensione ''n/2''; in questo caso il tempo di esecuzione è <math display="inline">O(n \log_2(n))</math>, precisamente <math display="inline">1.39\ n \log_2(n)</math>.
 
== Tipi di partizionamento ==