Comb sort

De Wikipedia, la enciclopedia libre

El Comb sort es un algoritmo de ordenamiento de complejidad O(n log n) diseñado por Stephen Lacey y Richard Box.

Comb sort es un algoritmo mejorado de algoritmo de ordenamiento de burbuja y es comparable en velocidad a algoritmos más complejos, como el Quicksort.

En el ordenamiento de burbuja, cuando dos elementos se comparan, la distancia de comparación (h) es siempre 1. Es decir, se compara un elemento y el siguiente. La idea básica de comb sort es que la distancia de comparación sea mucho mayor que 1 para eliminar las tortugas que están al final de la lista.

Todo esto de usar la estratégia de promover las claves en dirección a sus posiciones definitivas por saltos mayores de que apenas un lugar de cada vez, da una ganancia significativa con relación al método bubble sort.

En la primera barredura, esta distancia h es dada por el valor h = n div 1,3. En las barreduras subsequentes, esta distancia es progresivamente disminuida del factor 1,3, hasta que sea igual a la unidad. En este momento, el método se confunde con el bubblesort tradicional.

El factor de 1,3 fue obtenido por medio de simulaciones por los propios diseñadores del método. La reducción del tempo de clasificación en relación al bubblesort tradicional (sin cualquier tipo de otimización) fue del orden de 27 veces.

[editar] Implementación en C

A continuación se muestra una implementación en lenguaje C del algoritmo:

// COMBSORT                                            


#include <stdio.h>

void main (void)
{
     int I;
     int AUX;
     int A[5];
     int SW;
     int CANT;
     int GAP;


     CANT = 5;
     printf("\n   ASIGNANDO VALORES AL VECTOR ... \n"); 
     I = 0;
     while (I < CANT)
     {
          scanf("%d", &A[I]);
          I = I + 1;
     }

     printf("\n   CALCULANDO. AGUARDE.... \n");
     GAP = CANT;
     SW = 1;
     while (SW = 1 | GAP > 1)
     {
          SW = 0;
          GAP = (int)(GAP/1.3);
          if (GAP < 1)
          {
               GAP = 1;
          }

          I = 0;
          while (I < (CANT - GAP))
          {
               if (A[I] > A[I + GAP])
               {
                    AUX = A[I];
                    A[I] = A[I+GAP];
                    A[I+GAP] = AUX;
                    SW = 1;
               }

               I = I + 1;
          }

     }

     printf("\n   VECTOR ORDENADO"); 
     printf("\n   ---------------\n"); 
     I = 0;
     while (I < CANT)
     {
          printf("\n   < A["); 
          printf(I);
          printf("] > = "); 
          printf(A[I]);
          I = I + 1;
     }

     printf("\n");
}

[editar] Código en WinPseudo 1.4

A continuación se muestra una implementación en WinPseudo 1.4 del algoritmo:

INICIO Programa14 - CombSort
  VAR
     NUMERICO I
     NUMERICO Aux
     VECTOR   A[5]
     NUMERICO Sw
     NUMERICO Cant
     NUMERICO Gap
  FIN-VAR

#  LEER (Cant)
   Cant = 5

  IMPRIMIR NL
  IMPRIMIR "   Asignando valores al Vector ... "
  IMPRIMIR NL

  I = 0
  MIENTRAS (I < Cant)
#     A[I] = Cant - I
     leer (A[I])
     I = I + 1
  FIN-MIENTRAS
  
  IMPRIMIR NL
  IMPRIMIR "   Calculando. Aguarde.... "
  IMPRIMIR NL

  Gap = Cant
  Sw = 1
  MIENTRAS (Sw = 1 | Gap > 1)      
     Sw = 0
     Gap = ENTERO (Gap/1.3)
     
     SI (Gap < 1)
        Gap = 1
     FIN-SI

     I = 0
     MIENTRAS (I < (Cant - Gap))
        SI (A[I] > A[I + Gap])
           Aux = A[I]
           A[I] = A[I+Gap]
           A[I+Gap] = Aux
           Sw = 1
        FIN-SI
        I = I + 1
     FIN-MIENTRAS


  IMPRIMIR NL
  IMPRIMIR "   Vector Ordenado "
  IMPRIMIR NL
  IMPRIMIR "  ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ"
  IMPRIMIR NL
  
  I = 0
  MIENTRAS (I < Cant)
      IMPRIMIR NL
      IMPRIMIR "   < A["
      IMPRIMIR ENTERO (I)
      IMPRIMIR "] > = "
      IMPRIMIR ENTERO (A[I])
      I = I + 1
  FIN-MIENTRAS
  IMPRIMIR NL
FINAL