Complessità: ordinamenti ingenui

Bubble sort

Codice analizzato (Pascal)

Procedure BUBBLESORT(Var V: Vettore; N: Integer);
Var
    i, j: Integer;
Begin
    For i:=1 To N-1 Do
        For j:=1 To N-i Do
            If(V[j] > V[j+1]) Then
                SCAMBIA(V[j], V[j+1]);
End;

L’istruzione SCAMBIA() viene eseguita ogni volta che ha successo il controllo dell’istruzione If(...) Then.
Consideriamo il caso pessimo, cioè che succeda a ogni passo.
Quanti sono i controlli e le esecuzioni di SCAMBIA()?

i	j	Numero confronti	Numero scambi
1	1…(n-1)	n-1	n-1
2	1…(n-2)	n-2	n-2
…	…	…	…
n-2	1…2	2	2
n-1	1…1	1	1
		Totale?	Totale?

Quindi

T_C(n) = T_S(n) = (n-1)+(n-2)+…+1.

Quanto vale la somma?

Sappiamo che 1+2+…n = $\displaystyle \frac{n(n+1)}{2}$ e quindi

T(n) = $\displaystyle \frac{(n-1)n}{2}$ = $\displaystyle \frac{1}{2}n^2 - \frac{1}{2}n$ .

La complessità in tempo asintotica dell’algoritmo di ordinamento Bubble Sort è O(n²), sia per il numero di confronti che per il numero di scambi.

Nel caso ottimo, il vettore già ordinato, il numero di scambi è 0 ma rimane quadratico il numero di confronti.

Selection sort

Codice analizzato (Pascal)

Procedure SELESORT(Var V: Vettore; N: Integer);
Var
    PosMin, i, j: Integer;
Begin
    For i:=1 To N-1 Do
        Begin
            PosMin:=i;
            For j:=i+1 To N Do
                If(V[j] < V[PosMin]) Then
                    PosMin:=j;
            SCAMBIA(V[i], V[PosMin]);
        End;
End;

Quanti sono i confronti e le esecuzioni di SCAMBIA()?