La clasificación en peine es un algoritmo de clasificación relativamente simple diseñado originalmente por Włodzimierz Dobosiewicz y Artur Borowy en 1980, [1] [2] posteriormente redescubierto (y llamado "Combsort") por Stephen Lacey y Richard Box en 1991. [3] Clasificación en peine mejora la clasificación de burbujas de la misma manera que Shellsort mejora la clasificación de inserción , en el sentido de que ambos permiten que los elementos que comienzan lejos de su posición prevista se muevan más de un espacio por intercambio.
La definición de "clasificación de incremento decreciente" de nist.gov menciona el término "clasificación de peine" como una visualización de pases iterativos de los datos, "donde se tocan los dientes de un peine"; el primer término está vinculado a Don Knuth . [4]
La idea básica es eliminar las tortugas , o valores pequeños cerca del final de la lista, ya que en una clasificación de burbujas estos ralentizan enormemente la clasificación. Rabbits , valores grandes al principio de la lista, no plantean un problema en la clasificación de burbujas.
En la clasificación de burbujas, cuando se comparan dos elementos cualesquiera, siempre tienen un espacio (distancia entre sí) de 1. [5] La idea básica de la clasificación en peine es que el espacio puede ser mucho mayor que 1. El bucle interior de la burbuja sort, que realiza el intercambio real , se modifica de modo que la brecha entre los elementos intercambiados disminuya (para cada iteración del bucle externo) en pasos de un "factor de reducción" k : [ norte/k , norte/k 2 , norte/k 3 , ..., 1] .
El espacio comienza como la longitud de la lista n que se está clasificando dividida por el factor de contracción k (generalmente 1,3; ver más abajo) y se aplica una pasada del tipo de burbuja modificado antes mencionado con ese espacio. Luego, el espacio se divide nuevamente por el factor de reducción, la lista se ordena con este nuevo espacio y el proceso se repite hasta que el espacio sea 1. En este punto, la clasificación en peine continúa usando un espacio de 1 hasta que la lista esté completamente ordenada. La etapa final de la clasificación es, por lo tanto, equivalente a una clasificación de burbujas, pero para entonces ya se han eliminado la mayoría de las tortugas, por lo que una clasificación de burbujas será eficiente.
El factor de contracción tiene un gran efecto en la eficiencia de la clasificación del peine. Dobosiewicz sugirió k = 4/3 = 1,333…, mientras que Lacey y Box sugieren 1,3 como factor de contracción ideal después de pruebas empíricas en más de 200.000 listas aleatorias de longitud aproximada 1.000. Un valor demasiado pequeño ralentiza el algoritmo al hacer muchas comparaciones innecesarias, mientras que un valor demasiado grande no logra lidiar eficazmente con las tortugas, por lo que se requieren muchas pasadas con un espacio de 1.
El patrón de pasadas de clasificación repetidas con espacios decrecientes es similar a Shellsort, pero en Shellsort la matriz se ordena completamente en cada pasada antes de pasar al siguiente espacio más pequeño. Los pases de clasificación en peine no clasifican completamente los elementos. Esta es la razón por la que las secuencias de espacios de Shellsort tienen un factor de contracción óptimo mayor, de aproximadamente 2,25.
Un refinamiento adicional sugerido por Lacey y Box es la "regla del 11": utilice siempre un tamaño de espacio de 11, redondeando hacia arriba los tamaños de espacio de 9 o 10 (que se alcanzan dividiendo espacios de 12, 13 o 14 entre 1,3) a 11. Esto elimina las tortugas que sobreviven hasta el paso final del espacio 1.
la función combsort ( entrada de matriz ) es gap := input.size // Inicializa la reducción del tamaño del espacio := 1.3 // Establece el factor de reducción del espacio ordenado := falso loop while sorted = false // Actualiza el valor del espacio para el siguiente peine espacio: = piso (espacio / encogimiento) si la brecha ≤ 1 entonces brecha := 1 ordenado := true // Si no hay intercambios en este pase, terminamos ; de lo contrario, si gap = 9 o gap = 10 , entonces gap := 11 // La "regla del 11" termina si // Un único "peine" sobre la lista de entrada yo := 0 loop while i + gap < input.size // Consulte Ordenación de Shell para obtener una idea similar si input[i] > input[i+gap] y luego intercambiar (input[i], input[i+gap]) ordenado := falso // Si esta asignación nunca ocurre dentro del ciclo, // entonces no ha habido intercambios y la lista está ordenada. terminar si yo := yo + 1 fin de bucle fin de bucle función de fin
