Complessità del tempo di ordinazione della bolla
In questo articolo è considerato l'ordinamento ascendente. Questo articolo mira a indicare la velocità relativa dell'algoritmo di ordinamento della bolla. Questa velocità relativa viene definita complessità temporale. La codifica viene eseguita nella lingua del computer C.
Contenuto dell'articolo
- Introduzione - Vedi sopra
- Illustrazione di ordinamento a bolle
- Prestazioni peggiori
- Migliori prestazioni per il tipo di bolle
- Alcune sequenze di elementi intervallate già ordinate
- Custodia perfetta
- Conclusione
Illustrazione di ordinamento a bolle
Considera il seguente elenco non prestito:
R x f s u z v jCi sono 8 elementi, che necessitano di 8 scansioni complete, risultando:
R f s u x v j zF r s u v j x z
F r s u j v x z
F r s j u v x z
F r j s u v x z
F j r s u v x z
F j r s u v x z
F j r s u v x z
La disposizione dell'elenco finale è l'ordinamento completo.
Prestazioni peggiori
Il codice C per ordinare gli otto caratteri precedenti, precedentemente spiegato è:
#includerevoid BubbleSort (char arr [], int n)
int counter = 0;
per (int i = 0; i < n; i++)
per (int j = 1; j < n; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
contatore+= 1;
printf ("%i \ n", contatore);
Il codice per lo scambio è nell'assolo nidificato interno. Il contatore conta il numero di operazioni di base. I passanti esterni per loop da 0 a 7, i.e., 8 volte. I loop per loop interni da 1 a 7, i.e., 7 volte. Il numero totale di operazioni di base (per loop interno) è 8 x 7 = 56. L'output del contatore è 56.
Se il circuito interno per loop fosse da 0 a 7, il numero totale di operazioni di base sarebbe stato 8 x 8 = 64. Questo è il numero massimo di operazioni di base per questo nidificazione per loops. Lascia che 8 sia n. Quindi, il numero massimo di tale nidificazione per loop è n2.
La complessità del tempo peggiore per la funzione precedente è data come,
SU2)
Il grande O seguito dalle sue parentesi con n2 è chiamato la notazione Big-O. Indica la velocità relativa del codice. Sebbene nel codice precedente, il numero di operazioni di base è 56, il numero massimo possibile di operazioni, 82 = 64, è ciò che verrebbe dato per la complessità del tempo.
Una funzione principale C idonea per il codice precedente è:
int main (int argc, char ** argv)int n = 8;
char arr [] = 'r', 'x', 'f', 's', 'u', 'z', 'v', 'j';
Bubblesort (arr, n);
per (int i = 0; i
printf ("\ n");
restituzione 0;
Migliori prestazioni per il tipo di bolle
Si noti nell'illustrazione precedente per l'ordinamento della bolla; Dopo la prima scansione, l'elemento più alto è all'estremità destra. Dopo la seconda scansione, i due elementi più alti sono all'estremità destra, in ordine. Dopo la terza scansione, i tre elementi più alti sono all'estremità destra, in ordine e così via. Le operazioni su questi elementi estremi di destra man mano che crescono possono essere omesse nella codifica. Ciò aumenterebbe la velocità complessiva (tempo per l'ordinamento completo). Il seguente codice modificato illustra questo:
void BubbleSort (char arr [], int n)int counter = 0;
per (int i = 0; i < n; i++)
per (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
contatore+= 1;
printf ("%i \ n", contatore);
Questa volta, l'output del contatore è 28. Il numero di operazioni di base è 28, leggermente meno della metà di 64, che è 32. I passanti per loop interni da 1 a n - i. Nella sua prima scansione, I è zero e n - i = 8.
Ora,
tronco d'albero2 8 = log2 23
= 3
8 x 3 = 8xlog2 23
= 24
che è vicino a 28. Sia n = 8. L'ultima ma una espressione dell'opera e l'ultima destra sopra, diventa n.tronco d'albero2 23, = n.tronco d'albero2 8, generalmente scritto come, n log n.
Quando la complessità del tempo si trova all'interno di un intervallo medio, da 20 a 40, in questo caso, è espressa come:
O (n log n)
Dove n è il numero di elementi nell'elenco. Quindi, la complessità temporale per le prestazioni migliorate di Bolle Sort è N log n, che significa n x log2(N).
Alcune sequenze di elementi intervallate già ordinate
Ci sono otto scansioni per la precedente illustrazione di Sort. Si noti che alla sesta scansione, l'elenco era già già ordinato. Le ultime due righe sono ripetizioni della sesta fila. Per questo particolare elenco non senza cortili, le due scansioni precedenti non erano necessarie. Questo accade quando l'elenco non orientato da indicato ha alcune sequenze intervallate già ordinate. Se l'elenco indicato non è completamente insorti, allora l'ultima riga sarebbe l'elenco ordinato finale (non sarebbe una ripetizione del precedente).
Le ultime righe come le ultime due sopra possono essere omesse nell'ordinamento e quindi migliorare le prestazioni (velocità). Il seguente codice illustra questo:
void BubbleSort (char arr [], int n)_Bool scambiato = 0;
per (int i = 0; i < n; i++)
scambiati = 0;
per (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
scambiati = 1;
if (scambiati == 0)
rottura;
Custodia perfetta
Performance perfette si verificano quando l'elenco dato è già completamente ordinato. Il codice per testare questo è:
void BubbleSort (char arr [], int n)int counter = 0;
_Bool scambiato = 0;
per (int i = 0; i < n; i++)
scambiati = 0;
per (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
scambiati = 1;
contatore+= 1;
if (scambiati == 0)
rottura;
printf ("%i \ n", contatore);
L'output è:
7F j r s u v x z
per un elenco di input di,
F j r s u v x zIl 7 è dall'interno per loop. Tuttavia, per la complessità del tempo, viene considerato un massimo di 8. La complessità temporale per la performance perfetta è espressa come:
SU)
Conclusione
In questo articolo, abbiamo discusso della complessità del tempo di ordinazione della bolla e abbiamo sottolineato quanto segue:
La complessità del tempo peggiore per la bolle è:
SU2)
Con il miglioramento del codice, la complessità del tempo diventa:
O (n log n)
Quando l'elenco dato è già completamente ordinato, la complessità del tempo è:
SU)