Adattività

Lezione 6 di 11 del corso Ordinamento a bolle di Coddy.

Abbiamo discusso la complessità temporale del nostro algoritmo di ordinamento a bolle, che è O(n²) . Ma, cosa succede se il nostro array è già ordinato? Anche in questo caso, il tempo di esecuzione sarà O(n²).

Che cos'è l'adattività?

Un algoritmo adattivo è un algoritmo che cambia il proprio comportamento in base alla sequenza di input fornita.

Quindi, l'ordinamento a bolle è adattivo?

Sì, possiamo rendere adattivo il nostro algoritmo di ordinamento a bolle. Dobbiamo scrivere l'algoritmo di ordinamento a bolle con un tempo di esecuzione del caso peggiore pari a O(n²) e del caso migliore pari a O(n), in modo che sia adattivo. In questo caso, il caso migliore si riferisce alla situazione in cui l'array è già ordinato.

Utilizzeremo una variabile flag booleana per controllare il ciclo while, così che l'algoritmo si interrompa in anticipo se l'array era già ordinato.

while(flag)

{

//code

}

Dobbiamo ripetere il passaggio finché l'array non è ordinato. Abbiamo già imparato a contare il numero di scambi, quindi possiamo implementare un flag e verificare se durante il passaggio non è necessario alcuno scambio; in tal caso, possiamo interrompere il ciclo.

Sfida

Medio

Crea una funzione chiamata ad_bubblesort che riceva un array e la dimensione dell'array. Esegui l'algoritmo di ordinamento a bolle adattivo. Ricorda di usare una variabile chiamata flag per controllare gli scambi.

Provalo tu

#include <stdio.h>
#include <stdlib.h>

int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
    // Scrivi il codice qui
    *returnSize = n;
    return arr;
}

Tutte le lezioni di Ordinamento a bolle

1Nozioni di base dell'ordinamento a bolle

Introduzione Come funziona l'ordinamento a bolle Scambiare elementi adiacenti Algoritmo di ordinamento a bolle

2Analisi

Analisi della complessitàAdattivitàStabilità

3Sfide pratiche

Ordinamento inverso Differenza minimo-massimo Elemento k-esimo più piccolo Abhinav e i suoi amici

Esercitati da solo: Compilatore C online