El ordenamiento por peine es un algoritmo de ordenamiento 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] El ordenamiento por peine mejora el ordenamiento por burbuja de la misma manera que el ordenamiento por shell mejora el ordenamiento por inserción , ya 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 "ordenación por incremento decreciente" de nist.gov menciona el término "ordenación por peine" como la visualización de pasadas iterativas de los datos, "donde los dientes de un peine se tocan"; 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 ordenación de burbuja estos ralentizan enormemente la ordenación. Los conejos , valores grandes cerca del comienzo de la lista, no plantean un problema en la ordenación de burbuja.
En el ordenamiento de burbuja, cuando se comparan dos elementos cualesquiera, siempre tienen un espacio (distancia entre sí) de 1. [5] La idea básica del ordenamiento en peine es que el espacio puede ser mucho mayor que 1. El bucle interno del ordenamiento de burbuja, que realiza el intercambio real , se modifica de modo que el espacio entre los elementos intercambiados disminuye (en cada iteración del bucle externo) en pasos de un "factor de contracción" k : [ norte/a , norte/k2 , norte/k3 , ..., 1] .
El espacio comienza como la longitud de la lista n que se está ordenando dividida por el factor de reducción k (generalmente 1,3; ver más abajo) y se aplica una pasada del ordenamiento de burbuja modificado mencionado anteriormente 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, el ordenamiento por peine continúa usando un espacio de 1 hasta que la lista esté completamente ordenada. La etapa final del ordenamiento es, por lo tanto, equivalente a un ordenamiento de burbuja, pero en este momento la mayoría de las tortugas han sido eliminadas, por lo que un ordenamiento de burbuja será eficiente.
El factor de reducción tiene un gran efecto en la eficiencia de la clasificación por peine. Dobosiewicz sugirió k = 4/3 = 1,333…, mientras que Lacey y Box sugieren 1,3 como un factor de reducción ideal después de realizar pruebas empíricas en más de 200 000 listas aleatorias de longitud de aproximadamente 1000. Un valor demasiado pequeño ralentiza el algoritmo al realizar muchas comparaciones innecesarias, mientras que un valor demasiado grande no logra lidiar de manera efectiva con las tortugas, lo que hace que se requieran muchos pases con un espacio de 1.
El patrón de pases de ordenación repetidos con espacios decrecientes es similar al de Shellsort, pero en Shellsort la matriz se ordena completamente en cada pase antes de pasar al siguiente espacio más pequeño. Los pases de ordenación por peine no ordenan 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": siempre use un tamaño de espacio de 11, redondeando los tamaños de espacio de 9 o 10 (alcanzados al dividir los espacios de 12, 13 o 14 por 1,3) a 11. Esto elimina las tortugas que sobreviven hasta el paso final del espacio 1.
La función combsort( matriz de entrada) es gap := input.size // Inicializar el tamaño del espacio encoger := 1.3 // Establecer el factor de encogimiento del espacio ordenado := falso loop while sorted = false // Actualizar el valor del espacio para un próximo peine gap := piso(espacio libre / encoger) Si gap ≤ 1 entonces brecha := 1 sorted := true // Si no hay intercambios en este paso, 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 bucle mientras i + gap < input.size // Ver Shell sort para una idea similar si input[i] > input[i+gap] entonces swap (input[i], input[i+gap]) ordenado := falso // Si esta asignación nunca ocurre dentro del bucle, // entonces no ha habido intercambios y la lista está ordenada. fin si yo := yo + 1 Fin del bucle Fin del bucle Fin de la función
