Comb sort

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

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.

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

• La segunda pasada

gap = 6/1.3 = 4 , swapped = false

• El tercer paso

gap= 4/1.3 = 3 , swapped = false

• El cuarto paso

gap = 3/1.3 = 2 , swapped = false

• El quinto paso

gap = 2/1.3 = 1 , swapped = false

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(n²/2^p) donde p es el número de incrementos.

• El peor caso

La complejidad temporal en el peor de los casos es [Big O]: O(n²).

• 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.