Comb sort
- Algoritmo de ordenación en peine
- Ejemplo de ordenación en peine
- Implementación del algoritmo Comb Sort
- Complejidad del algoritmo Comb Sort
![Comb sort](/img/Algorithm/feature-image---comb-sort.webp)
La comb sort es un algoritmo de ordenación simple basado en la comparación. Es una forma mejorada de ordenamiento de burbuja. En la ordenación por burbujas, los elementos adyacentes se comparan en cada paso/fase y se eliminan las inversiones una a una. Por otro lado, la ordenación en peine comienza utilizando un hueco grande y lo reduce cada vez en un factor de encogimiento de 1.3
. La ordenación en peine puede eliminar múltiples inversiones con un solo intercambio. Se basa en la idea de matar a las tortugas. Las tortugas son los elementos pequeños hacia el final de la lista, lo que reduce la eficiencia de la ordenación por burbujas y matarlos mejora el rendimiento de la ordenación significativamente.
Algoritmo de ordenación en peine
Supongamos que tenemos un array sin ordenar A[]
que contiene n
elementos. Tomaremos el factor de encogimiento como 1.3
porque se ha encontrado empíricamente que da los mejores resultados.
-
Inicializa la variable
gap
como el tamaño del array y la variableswapped
comotrue
. -
Declara la variable constante
SHRINK_FACTOR
como1.3
. -
Mientras el
gap
no sea 1 oswapped
esté entrue
haz lo siguiente:-
Set
swapped
asfalse
. -
Set
gap
as(int)gap/SHRINK_FACTOR
. -
For every element in the range
0
ton - gap
do the following - ifA[i]
>A[i+gap]
,swap(A[i], A[i+gap])
and setswapped
totrue
.
-
Ejemplo de ordenación en peine
Supongamos que tenemos el array (3, 5, 2, 8, 1, 7, 6, 4)
. Vamos a ordenarlo utilizando el algoritmo Comb sort.
Inicializamos gap
=8, swapped
=true
y SHRINK_FACTOR
= 1.3
.
- La primera pasada
gap
= 8/1.3 = 6 , swapped
= false
Iteración | (3, 5, 2, 8, 1, 7, 6, 4) | Acción |
---|---|---|
i = 0 | (3, 5, 2, 8, 3, 7, 6, 4) | 3 < 6, No hay intercambio |
i = 1 | (3, 4, 2, 8, 1, 7, 6, 5) | 5 > 4, Intercambio |
- La segunda pasada
gap
= 6/1.3 = 4 , swapped
= false
Iteración | (3, 4, 2, 8, 1, 7, 6, 5) | Acción |
---|---|---|
i = 0 | (1, 4, 2, 8, 3, 7, 6, 5) | 3 > 1, Intercambio |
i = 1 | (1, 4, 2, 8, 3, 7, 6, 5) | 4 < 7, Sin intercambio |
i = 2 | (1, 4, 2, 8, 3, 7, 6, 5) | 2 < 6, No hay intercambio |
i = 3 | (1, 4, 2, 5, 3, 7, 6, 8) | 8 > 5, Intercambio |
- El tercer paso
gap
= 4/1.3 = 3 , swapped
= false
Iteración | (1, 4, 2, 5, 3, 7, 6, 8) | Acción |
---|---|---|
i = 0 | (1, 4, 2, 5, 3, 7, 6, 8) | 1 < 5, No hay intercambio |
i = 1 | (1, 3, 2, 5, 4, 7, 6, 8) | 4 > 3, Intercambio |
i = 2 | (1, 3, 2, 5, 4, 7, 6, 8) | 2 < 7, Sin intercambio |
i = 3 | (1, 3, 2, 5, 4, 7, 6, 8) | 5 < 6, No hay intercambio |
i = 4 | (1, 3, 2, 5, 4, 7, 6, 8) | 4 < 8, No hay intercambio |
- El cuarto paso
gap
= 3/1.3 = 2 , swapped
= false
Iteración | (1, 3, 2, 5, 4, 7, 6, 8) | Acción |
---|---|---|
i = 0 | (1, 3, 2, 5, 4, 7, 6, 8) | 1 < 2, Sin intercambio |
i = 1 | (1, 3, 2, 5, 4, 7, 6, 8) | 3 < 5, No hay intercambio |
i = 2 | (1, 3, 2, 5, 4, 7, 6, 8) | 2 < 4, No hay intercambio |
i = 3 | (1, 3, 2, 5, 4, 7, 6, 8) | 5 < 7, No hay intercambio |
i = 4 | (1, 3, 2, 5, 4, 7, 6, 8) | 4 < 6, No hay intercambio |
i = 5 | (1, 3, 2, 5, 4, 7, 6, 8) | 7 < 8, No hay intercambio |
- El quinto paso
gap
= 2/1.3 = 1 , swapped
= false
Iteración | (1, 3, 2, 5, 4, 7, 6, 8) | Acción |
---|---|---|
i = 0 | (1, 3, 2, 5, 4, 7, 6, 8) | 1 < 3, No hay intercambio |
i = 1 | (1, 2, 3, 5, 4, 7, 6, 8) | 3 > 2, Intercambio |
i = 2 | (1, 2, 3, 5, 4, 7, 6, 8) | 3 < 5, Sin intercambio |
i = 3 | (1, 2, 3, 4, 5, 7, 6, 8) | 5 > 4, Intercambio |
i = 4 | (1, 2, 3, 4, 5, 7, 6, 8) | 5 < 7, Sin intercambio |
i = 5 | (1, 2, 3, 5, 4, 6, 7, 8) | 7 > 6, Intercambio |
i = 6 | (1, 2, 3, 4, 5, 6, 7, 8) | 7 < 8, Sin intercambio |
Obtenemos el array ordenado final como (1, 2, 3, 4, 5, 6, 7, 8)
.
Implementación del algoritmo Comb Sort
#include <iostream>
using namespace std;
int updateGap(int gap) {
gap = (gap * 10) / 13;
if (gap < 1)
return 1;
else
return gap;
}
void combSort(int arr[], int n) {
int gap = n;
bool swapped = true;
while (gap > 1 || swapped == true) {
gap = updateGap(gap);
swapped = false;
for (int i = 0; i < (n - gap); i++) {
int temp;
if (arr[i] > arr[i + gap]) {
temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = true;
}
}
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
combSort(arr, n);
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Complejidad del algoritmo Comb Sort
Complejidad temporal
- Caso medio
La complejidad temporal es del orden de [Big Theta]: O(n2/2p) donde p
es el número de incrementos.
- El peor caso
La complejidad temporal en el peor de los casos es [Big O]: O(n2).
- El mejor caso
El mejor caso ocurre cuando el array ya está ordenado o casi ordenado. La complejidad temporal del mejor caso es [Big Omega]: O(nlogn)
. Es una mejora significativa sobre la complejidad temporal del mejor caso de la ordenación por burbujas.
Complejidad espacial
La complejidad espacial de este algoritmo es O(n)
porque el algoritmo de ordenación en peine no requiere más espacio que las variables temporales.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn