Comb sort

De Wikipedia, la enciclopedia libre

Contextualizar

Este artículo no posee un contexto claro. Por favor, añade información que aclare el contexto y permita evaluar la relevancia de este tema o el artículo será candidato para borrado.

Para más información sobre lo que se está solicitando, ver Ayuda:Contextualizar

[editar] Teoria

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 bubble sort y es comparable a algoritmos más complejos, como quick sort, en velocidad.

En el bubble sort, 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] Código en Lenguaje C

// 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.3

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

# Este SI es para evitar que salga del lazo mayor
# cuando Gap es aun mayor que 1

#     SI (Gap > 1)
#        Sw = 1
#     FIN-SI
  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