Ordenación del peine o de Dobosiewicz

Ordenación del peine o de Dobosiewicz

En 1980, Wlodzimierz Dobosiewicz propuso este algoritmo 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").

Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo publicado por la revista Byte en abril de 1991.

En el ordenamiento de burbuja, cuando dos elementos cualquiera se comparan, siempren tienen un espacio (distancia entre ellos) de 1. La idea básica del algoritmo CombSort es que el espacio pueda ser mucho mayor de uno.

El ordenamiento Shell también se basa en esta idea, pero es una modificación del algoritmo de ordenamiento por inserción más que del algoritmo de ordenamiento de burbuja.

Representación animada del algoritmo :

Representación animada de la ordenación del peine

  1. PROCEDIMIENTO comb_sort ( VECTOR a[1:n])
  2. gap ← n
  3. REPETIR
  4.     permut ← FALSO
  5.     gap ← gap / 1.3
  6.     SI gap < 1 ENTONCES gap ← 1
  7.     PARA i VARIANDO DE 1 HASTA n CON INCRECREMENT DE gap HACER
  8.         SI a[i] > a[i+gap] ENTONCES
  9.             intercambiar a[i] Y a[i+gap]
  10.             permut ← VERDADERO
  11.         FIN SI
  12.     FIN POUR
  13. MIENTRAS QUE permut = VERDADERO O gap > 1
  1. let comb_sort vector =
  2.     let gap = ref (Array.length vector) and permutación = ref true in
  3.     while (!permutación = true) or (!gap > 1)  do
  4.         permutación := false;
  5.         gap := int_of_float(float_of_int(!gap) /. 1.3);
  6.         if !gap < 1 then gap := 1;
  7.         for actual = 0 to (Array.length vector) - !gap - 1 do
  8.             if vector.(actual) > vector.(actual + !gap) then
  9.             begin
  10.                 (* Intercambiamos los dos elementos *)
  11.                 permutación := true;
  12.                 let temp = vector.(actual) in
  13.                 begin
  14.                    vector.(actual) <- vector.(actual + !gap);
  15.                    vector.(actual + !gap) <- temp;
  16.                 end
  17.             end
  18.         done;
  19.     done;
  20. vector;;
  1. type tab = array[1..20] of integer;
  2. procedure comb_sort(var vector : tab);
  3. var permutación : boolean;
  4.     actual : integer;
  5.     temp : integer;
  6.     gap : integer;
  7.  
  8. begin
  9.     gap:=20;
  10.     REPEAT
  11.         permutación := false;
  12.         gap:=trunc(gap / 1.3);
  13.         if gap<1 then gap := 1;
  14.         for actual := 1 to 20 - gap do
  15.         begin
  16.             if (vector[actual] > vector[actual + gap]) then
  17.             begin
  18.                 { Intercambiamos los dos elementos }
  19.                 temp := vector[actual];
  20.                 vector[actual]:=vector[actual + gap];
  21.                 vector[actual+gap]:=temp;
  22.                 permutación := true;
  23.             end;
  24.         end;
  25.     UNTIL (not permutación) and (gap = 1);
  26. end;
  1. import math  
  2. def comb_sort(vector):
  3.     permutación = True
  4.     gap = len(vector)
  5.     while (permutación == True) or  (gap>1):
  6.         permutación = False
  7.         gap = math.floor(gap / 1.3)
  8.         if gap<1: gap = 1
  9.         for actual in range(0, len(vector) - gap):
  10.             if vector[actual] > vector[actual + gap]:
  11.                 permutación = True
  12.                 # Intercambiamos los dos elementos
  13.                 vector[actual], vector[actual + gap] = \
  14.                 vector[actual + gap],vector[actual]
  15.     return vector  
  1. typedef int bool;
  2. enum { false, true };
  3.  
  4. void comb_sort(int* vector)
  5. {
  6.     int gap = 20;
  7.     bool permutación = true;
  8.     int actual;
  9.    
  10.     while (( permutación) || (gap>1)) {
  11.         permutación = false;
  12.         gap = gap / 1.3;
  13.         if (gap<1) gap=1;
  14.         for (actual=0;actual<20-gap;actual++) {
  15.             if (vector[actual]>vector[actual+gap]){
  16.                 permutación = true;
  17.                 // Intercambiamos los dos elementos
  18.                 int temp = vector[actual];
  19.                 vector[actual] = vector[actual+gap];
  20.                 vector[actual+gap] = temp;
  21.             }
  22.         }
  23.     }
  24. }

La elección del factor de descuento es crucial para la eficacia de este algoritmo. En general , se necesita un factor de reducción de entre 1,25 y 1,33. La animación de arriba utiliza 1.3 como el factor de reducción .

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 


La complejidad de este algoritmo es muy difícil de calcular. En general se considera que, en el mejor de los casos , es lineal ( O ( n)) , y que, en el caso peor es Θ(n2). En caso medio sería en O ( n log n ).

La aplicación Javascript a continuación evalúa el número de intercambios y comparaciones requeridas para el algoritmo para ordenar una lista . Elija el modo de generación de la serie para ordenar , el factor de reducción , el color de la curva y haga clic en " buscar ". Hasta cinco curvas se pueden visualizar en el mismo gráfico.

En el caso de los datos generados al azar, de aplicar el maquillaje hasta diez pases a las comparaciones y se mueve a la media.

Rendimiento del algoritmo
Reducción :
Número de términosGapsPasoComparacionesIntercambiosSuma
000
Número de términosGapsPasoComparacionesIntercambiosSuma
000
Número de términosGapsPasoComparacionesIntercambiosSuma
000
Número de términosGapsPasoComparacionesIntercambiosSuma
000
Número de términosGapsPasoComparacionesIntercambiosSuma
000