Metraipolis › archive › dc_76cff4ac6949
Comb sort — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Comb_sort
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-02T06:50:57.036Z
- SHA-256 of the archived text
87d711a961e4071164bd5129e8585a528aa5f52a98fdde132f9afd446f46d7ed- Stable URL of this page
https://metraipolis.com/documento/dc_76cff4ac6949
How to cite
Comb sort — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Comb_sort (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_76cff4ac6949 (Metraipolis archive dc_76cff4ac6949, sha256 87d711a961e4071164bd5129e8585a528aa5f52a98fdde132f9afd446f46d7ed)
BibTeX
@misc{dc76cff4ac6949,
title = {Comb sort — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Comb_sort},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_76cff4ac6949; sha256 87d711a961e4071164bd5129e8585a528aa5f52a98fdde132f9afd446f46d7ed},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Comb_sort. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In Informatica il Comb sort è un algoritmo di ordinamento pubblicato per la prima volta da Stephen Lacey e Richard Box sul numero di aprile 1991 della rivista Byte. Il Comb sort rielabora le idee che Wlodzimierz Dobosiewicz applicò nel 1980 per rendere più efficiente lo shell sort utilizzando la funzione del bubble sort. Il Comb sort migliora l'algoritmo bubble sort e compete in velocità con algoritmi storicamente veloci come il Merge sort. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette "tartarughe", ovvero valori piccoli vicini alla fine della lista, essendo provato che in un bubble sort questi valori tendono spessissimo a scendere nella loro posizione in modo tremendamente lento. (i "conigli", ovvero grandi valori all'inizio della lista, non rappresentano un problema nel bubble sort perché generalmente vengono spostati molto velocemente). Nel bubble sort, quando vengono confrontati due elementi, essi hanno sempre un passo (distanza reciproca) pari ad 1. L'idea alla base del comb sort è che il passo possa essere anche maggiore (anche lo Shell sort è basato su questa idea, ma esso rappresenta una modifica dell'insertion sort piuttosto che del bubble sort). Il passo, o intervallo del confronto, è impostato inizialmente alla lunghezza dell'array da ordinare divisa per il fattore di riduzione (generalmente 1,3), e la lista viene ordinata con tale intervallo (arrotondato per difetto all'intero, se necessario). Terminato il primo passaggio il passo viene diviso nuovamente per il fattore di riduzione (arrotondato all'intero), e la lista viene ordinata con questo nuovo intervallo. Il processo si ripete finché il passo è pari a 1. A questo punto, il Comb sort continua ad usare un passo di 1 finché non si ha un ordinamento totale. Il passaggio finale dell'algoritmo è quindi equivalente ad un bubble sort, ma in questo modo molte "tartarughe" sono scomparse, ed in tal modo il bubble sort è molto più efficiente. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico). Fonte: Wikipedia in italiano, voce «Comb sort» — https://it.wikipedia.org/wiki/Comb_sort Wikidata Q133939: «algoritmo di ordinamento» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q133939 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Comb_sort?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 149561401, consultata il 2026-11-02T06:42:32.008Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ff9c8682bbac249da33deb01338ed58cfeadbe1b08b3f884232579483a430f0f