Quicksort: differenze tra le versioni

Versione delle 21:07, 5 mar 2025

Versione delle 01:34, 13 mar 2025

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