Bienvenidos 

Algoritmo Comb Sort.

Orígenes:

• En 1973, Donald Ervin Knuth propuso este algoritmo en el ejercicio 5.2.1-40 de su obra "The Art of Computer Programming", vol. 3, Sorting and Searching (ordenación y búsqueda).

• En 1980, Wlodzimierz Dobosiewicz lo propuso de nuevo en su breve artículo "An Efficient Variation of Bubble Sort", Information Processing Letters, vol. 11, num. 1, 1980. En él escribió literalmente: "Bubble sort can be improved in yet another way, which is similar to Shell’s version of the insertion sort." ("La ordenación por burbuja se puede mejorar de otra manera adicional, que es similar a la versión de Shell de la ordenación por inserción").

• En 1991, Stephen Lacey y Richard Box propusieron el mismo algoritmo bajo el nombre de "Combsort" en su artículo "A fast, easy sort" Byte, vol. 16, issue 4, Abril de 1991. 

Características Principales:

Características del algoritmo:

¿Cuánto tarda?	Peor caso: O(N2) Caso medio: O(N log N)  Mejor caso: O(N log N)
¿Cuánto espacio adicional necesita?	O(1)
¿Realiza una ordenación estable?	No
¿Es una red de ordenación?	Sí

Descripción del Algoritmo:

La idea es eliminar pequeños valores cerca del final de la lista, ya que en el algoritmo deordenamiento de burbuja esto reduce la velocidad de ordenamiento tremendamente.En el ordenamiento de burbuja, cuando dos elementos cualquiera se comparan, siempren tienenun espacio (distancia entre ellos) de 1.La idea básica del algoritmo comb sort es que el espacio pueda ser mucho mayor de uno.El espacio se inicia como la longitud de la lista a ordenar dividida por el factor de encogimiento(1.3). La clave para que comb sort sea rapido es que al principio compara e intercambia (o no) elementos distantes entre si. Despues va haciendo esa distancia cada vez menor. a esa distancia se le denomina gap o incremento.

Como funciona:

Pseudocodigo:

gap:= input.size //inicializar tamaño de espacio
    
    loop until gap = 1 and swaps = 0
        //actualizar el valor del espacio para el siguiente rastreo
        if gap > 1
            gap:= gap / 1.3
            if gap = 10 or gap = 9
                gap:= 11
            end if
        end if
        
        i:= 0
        swaps:= 0 //véase ordenamiento de burbuja para una explicación
        //un único "rastreo" sobre la lista de entrada
        loop until i + gap >= array.size
            if array[i] > array[i+gap]
                swap (array[i], array[i+gap])
                swaps:= swaps + 1
            end if
            i:= i + 1
        end loop
    end loop
end function

Codigo en C del algoritmo Comb Sort:

void Combsort11(double a[], int nElements)
{
  int i, j, gap, swapped = 1;
  double temp;
 
  gap = nElements;
  while (gap > 1 || swapped == 1)
  {
    gap = gap * 10 / 13;
    if (gap == 9 || gap == 10) gap = 11;
    if (gap < 1) gap = 1;
    swapped = 0;
    for (i = 0, j = gap; j < nElements; i++, j++)
    {
      if (a[i] > a[j])
      {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        swapped = 1;
      }
    }
  }
}