Adaptivity
Lição 6 de 11 do curso Bubble Sort da Coddy.
Nós discutimos a complexidade de tempo para o nosso algoritmo bubble sort, que é O(n2) . Mas, e se o nosso array já estiver ordenado? Ainda assim, ele levará o tempo de execução de O(n2).
O que é Adaptatividade?
Um algoritmo adaptativo é um algoritmo que muda seu comportamento com base na sequência de entrada fornecida.
Então, o bubble sort é adaptativo?
Sim, podemos tornar nosso algoritmo bubble sort adaptativo. Temos que escrever o algoritmo Bubble Sort com um tempo de execução de pior caso de O(n2) e melhor caso de O(n) para que ele seja adaptativo. Aqui, o melhor caso refere-se ao caso em que o array já está ordenado.
Usaremos uma variável de flag booleana para controlar o loop while, de modo que o algoritmo pare mais cedo se já estiver ordenado.
while(flag)
{
//code
}
Temos que repetir a passagem até que o array esteja ordenado. Já aprendemos como contar o número de trocas, então podemos implementar uma flag e verificar se nenhuma troca foi necessária na passagem e, então, podemos interromper o loop.
Desafio
MédioCrie uma função chamada ad_bubblesort que recebe um array e o tamanho do array. Execute o algoritmo adaptive bubble sort. Lembre-se de usar uma variável chamada flag para verificar trocas.
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Escreva o código aqui
*returnSize = n;
return arr;
}
Todas as lições de Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm