Quicksort: differenze tra le versioni

Versione delle 17:14, 31 mar 2025

Versione attuale delle 08:01, 29 mag 2025

(Una versione intermedia di un altro utente 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:'''