Comb sort

Harshit Jindal 12 octubre 2023
  1. Algoritmo de ordenación en peine
  2. Ejemplo de ordenación en peine
  3. Implementación del algoritmo Comb Sort
  4. Complejidad del algoritmo Comb Sort
Comb sort

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 variable swapped como true.
  • Declara la variable constante SHRINK_FACTOR como 1.3.
  • Mientras el gap no sea 1 o swapped esté en true haz lo siguiente:
    • Set swapped as false.
    • Set gap as (int)gap/SHRINK_FACTOR.
    • For every element in the range 0 to n - gap do the following - if A[i] > A[i+gap], swap(A[i], A[i+gap]) and set swapped to true.

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 avatar Harshit Jindal avatar

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

Artículo relacionado - Sort Algorithm