Ordinamenti ingenui

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Ordinamenti ingenui

Prendiamo in considerazione l'algoritmo di ordinamento Bubble Sort

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 l'if() ha successo; consideriamo il caso pessimo, cioè che succeda a ogni passo.

Quante volte viene eseguita?

i	j	T
1	1...N-1	N-1
2	1...N-2	N-2
...	...	...
N-1	1...(N-(N-1)) = 1...1	1

Quindi

T(n) = (n-1)+(n-2)+...+1.

Quanto vale la somma? Sappiamo che

1+2+...N = ½N(N+1)

e quindi

T(n) = ½(n-1)n = ½n²-½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 è zero ma rimane quadratico il numero di confronti.

Consideriamo ora il Selection Sort

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;

Quante volte viene eseguito l'if() ?

i	j	T
1	2..N	N-1
2	3..N	N-2
...	...	...
N-1	N..N	1

Come prima

T(n) = (n-1)+(n-2)+...+1

La complessità in tempo asintotica dell'algoritmo di ordinamento Selection Sort è O(n²), per il numero di confronti (e assegnazioni).

Il numero di scambi è N-1, lineare.

Ordinamenti ingenui - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito