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

Ordinamenti ingenui

Precedente
SUPERIORE
Successiva

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?

ijT
11...N-1N-1
21...N-2N-2
.........
N-11...(N-(N-1)) = 1...11

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 = ½n2-½n.

La complessità in tempo asintotica dell'algoritmo di ordinamento Bubble Sort è O(n2), 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() ?

ijT
12..NN-1
23..NN-2
.........
N-1N..N1

Come prima

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

La complessità in tempo asintotica dell'algoritmo di ordinamento Selection Sort è O(n2), 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

Precedente
SUPERIORE
Successiva