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 ).
Java
// Java program for implementation of Comb Sort
class CombSort {
// 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 arr[] using Comb Sort
void sort(int arr[])
{
int n = arr.length;
// initialize gap
int gap = n;
// Initialize swapped as true to make sure that
// loop runs
boolean 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 (arr[i] > arr[i + gap]) {
// Swap arr[i] and arr[i+gap]
int temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
// Set swapped
swapped = true;
}
}
}
}
// Driver method
public static void main(String args[])
{
CombSort ob = new CombSort();
int arr[] = { 8, 4, 1, 56, 3, -44, 23, -6, 28, 0 };
ob.sort(arr);
System.out.println("sorted array");
for (int i = 0; i < arr.length; ++i)
System.out.print(arr[i] + " ");
}
}
/* This code is contributed by Rajat Mishra */
sorted array -44 -6 0 1 3 4 8 23 28 56
Complejidad de tiempo: La complejidad del peor de los casos de este algoritmo es O(n 2 ).
Espacio Auxiliar: O(1).
¡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