Comb Sort es principalmente una mejora sobre Bubble Sort. La ordenación de burbuja siempre compara valores adyacentes. Entonces todas las inversiones se eliminan una por una. Comb Sort mejora el Bubble Sort al usar un espacio de tamaño superior a 1. El espacio comienza con un valor grande y se reduce en un factor de 1,3 en cada iteración hasta que alcanza el valor 1. Por lo tanto, Comb Sort elimina más de una inversión cuenta con uno swap y funciona mejor que Bubble Sort.
Se ha encontrado empíricamente que el factor de reducción es 1.3 (al probar Combsort en más de 200 000 listas aleatorias) [Fuente: Wiki ]
Aunque, en promedio, funciona mejor que Bubble Sort, el peor de los casos sigue siendo O (n 2 ).
CPP
// C++ implementation of Comb Sort
#include <bits/stdc++.h>
using namespace std;
// To find gap between elements
int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap * 10) / 13;
if (gap < 1)
return 1;
return gap;
}
// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
// Initialize gap
int gap = n;
// Initialize swapped as true to make sure that
// loop runs
bool swapped = true;
// Keep running while gap is more than 1 and last
// iteration caused a swap
while (gap != 1 || swapped == true) {
// Find next gap
gap = getNextGap(gap);
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = false;
// Compare all elements with current gap
for (int i = 0; i < n - gap; i++) {
if (a[i] > a[i + gap]) {
swap(a[i], a[i + gap]);
swapped = true;
}
}
}
}
// Driver program
int main()
{
int a[] = { 8, 4, 1, 56, 3, -44, 23, -6, 28, 0 };
int n = sizeof(a) / sizeof(a[0]);
combSort(a, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
Sorted array: -44 -6 0 1 3 4 8 23 28 56
¡ Consulte el artículo completo sobre Comb Sort para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA