Quicksort: differenze tra le versioni

Versione delle 13:12, 3 feb 2025

Versione attuale delle 08:01, 29 mag 2025

(4 versioni intermedie di 4 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

}}

'''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=2022-07-21 luglio 2022|accesso=2025-01-29 gennaio 2025}}</ref>"; ovvero sulla scomposizione del problema in più sottoproblemi di taglia minore<ref name="geeksforgeeks.org">{{Cita web|lingua=en-US|url=https://www.geeksforgeeks.org/quick-sort-algorithm/|titolo=Quick Sort|sito=GeeksforGeeks|data=7 gennaio 2014-01-07|accesso=2025-01-29 gennaio 2025}}</ref>.

In generale il la logica dell'algoritmo può essere riassunta in questo modo<ref>{{Cita web|linguaname=en-US|url=https://www."geeksforgeeks.org"/quick-sort-algorithm/|titolo=Quick Sort|sito=GeeksforGeeks|data=2014-01-07|accesso=2025-01-29}}</ref>:

# '''Scelta del pivot:'''

Riga 23:

#* Alla fine di questa fase, il pivot sarà nella sua posizione corretta nella lista.

# '''Ricorsione sui sotto-array:'''

#* Applicazione del Quicksort alla parte sinistra (elementi minori o uguali al pivot) e alla parte destra (elementi maggiori).

#* Continua fino a che i sotto-array contengono un solo elemento o sono vuoti (caso base).

Riga 29:

== Storia ==

L'algoritmo quicksort fu ideato nel 1959 da [[Tony Hoare]] durante un viaggio nell'URSS, durante una sua visita alla [[Moscow State University]]. In quel periodo, Hoare lavorava a un progetto di [[traduzione automatica]] per il [[National Physical Laboratory, UK|National Physical Laboratory]]. Durante il processo di traduzione si rese necessario ordinare le parole russe prima di consultare il dizionario Russo-Inglese che era registrato su un [[nastro magnetico]] e ordinato alfabeticamente.<ref>{{Cita pubblicazione|cognome=Shustek|nome=L.|titolo=Interview: An interview with C.A.R. Hoare|doi=10.1145/1467247.1467261|rivista=[[Communications of the ACM|Comm. ACM]]|volume=52|numero=3|pp=38–4138-41|anno=2009}}</ref> Dopo aver capito che l'uso dell'[[insertion sort]] sarebbe stato troppo lento, concepì una nuova idea di algoritmo - il Quicksort. Scrisse il programma con [[Autocode]] relativa alla partizione ma non riuscì a gestire la parte relativa ai segmenti non ordinati. Tornato in Inghilterra, gli fu chiesto per lavoro di scrivere il codice di uno [[Shell sort]] - l'algoritmo di ordinamento più efficiente all'epoca. Hoare dichiarò al suo capo che conosceva un algoritmo più efficiente; il capo fece una scommessa, di sei pence, e perse. In seguito, Hoare venne a conoscenza del linguaggio [[ALGOL]] e della sua abilità di gestire la ricorsione; grazie ad esso, pubblicò il codice completo nella maggiore rivista scientifica di informatica del periodo, ''[[Communications of the ACM|Communications of the Association for Computing Machinery]]''.<ref>{{Cita web|url=http://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html|titolo=My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort|data=15 marzo 2015|accesso=|editore=Marcelo M De Barros|cognome=|nome=}}</ref>

== Algoritmo di base ==

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