Adaptivity
Lección 6 de 11 del curso Ordenamiento de burbuja de Coddy.
Hemos discutido la complejidad temporal de nuestro algoritmo de ordenamiento de burbuja (bubble sort), que es O(n2). Pero, ¿qué pasa si nuestro arreglo ya está ordenado? En ese caso, también tomará un tiempo de ejecución de O(n2).
¿Qué es la Adaptatividad?
Un algoritmo adaptativo es un algoritmo que cambia su comportamiento según la secuencia de entrada proporcionada.
Entonces, ¿es el ordenamiento de burbuja adaptativo?
Sí, podemos hacer que nuestro algoritmo de ordenamiento de burbuja sea adaptativo. Tenemos que escribir el algoritmo Bubble Sort con un tiempo de ejecución en el peor de los casos de O(n2) y en el mejor de los casos de O(n) para que sea adaptativo. Aquí, el mejor de los casos se refiere al escenario en el que el arreglo ya está ordenado.
Utilizaremos una variable de bandera (flag) booleana para controlar el bucle while, de modo que el algoritmo se detenga prematuramente si ya estaba ordenado anteriormente.
while(flag)
{
//code
}
Tenemos que repetir la pasada hasta que el arreglo esté ordenado. Ya hemos aprendido cómo contar el número de intercambios (swaps), por lo que podemos implementar una bandera y verificar si no se requiere ningún intercambio en la pasada y, entonces, podemos romper el bucle.
Desafío
IntermedioCrea una función llamada ad_bubblesort que reciba un arreglo y el tamaño del mismo. Implementa el algoritmo de ordenamiento de burbuja adaptativo. Recuerda usar una variable llamada flag para verificar si hubo intercambios.
Pruébalo tú mismo
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Escribe el código aquí
*returnSize = n;
return arr;
}
Todas las lecciones de Ordenamiento de burbuja
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm