Comb Sort

Comb Sort, también denominado de Peine o Cardado, es un algoritmo de ordenación que mejora el algoritmo de Burbuja. Utiliza la misma acción que Shellsort para aumentar la brecha en las comparaciones e intercambios, el valor empírico del factor de reducción para extender la brecha es (1 – eφ ) ≈ 1,24733095, también √2 = 1,259. La mayoría de sus implementaciones usa 1,3, que es el espacio de trabajo (distancia entre elementos) que comienza con un tamaño grande y se va reduciendo en cada iteración, en ese factor, hasta alcanzar el valor 1. Estos valores han estado durante mucho tiempo en controversia, pero la realidad es la que es y en estos momentos el algoritmo está por detrás de otros en rendimiento.

 

Rendimiento – Complejidad
Mejor caso Ω Peor caso O Media Θ Espacio
(n log n) (n²) (n²) O(1)

Donald E. Knuth Ordenación de vectores COMB

Robert W. Floyd Ordenación de vectores COMB

 

Muchas publicaciones indican que fue Wlodzimierz Dobosiewicz quién lo desarrolló en 1.980, pero Donald E. Knuth y Robert W. Floyd quienes lo propusieron en “The Art of Computer Programming, Vol 3” de 1.973 como una variante de Shellsort. Otra fecha de autoría es la de 1.994 de Stephen Lacey y Richard Box.

 

En el algoritmo de ejemplo se propone la variante de Stephen Lacey – Richard Box:  brecha = (brecha * 10) / 13  que da un factor superior a 1,3.

 

Comb. Algoritmo de ordenación en Java

 

 

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.

Comb sort. Rendimientos estadística de 10 a 100 mil elementos

 

Comb sort. Rendimientos estadística de 100 mil a 1 millon de elementos