47334 zdj
5 (6)

l'l iiyi am»»u aiiM I    I

I I I f I t . i I

■

Analiza algorytmu

Liczba porównan w i-tym przesiewaniu wynosi maksymalnie i~1, minimalnie 1 oraz ponieważ wszystkie permutacje n elementów $ą równie prawdopodobne, średnio i/2. Liczba przesunięć jest o 2 większa od liczby porównań (uwzględniając ustawienie wartownika).

Liczba porównań (przypadek najgorszy):

k    I + 2 + 3 +.., *f (*V

Liczba przepisywań:

(2 4 I) f (2 f 2) + .,, f (2 -f (A — I) >

I iczbu porównćiri (przypadek najlepszy)

I iczba przepisy wań

2( N I)