13108 zdj
0 (9)

Analiza algorytmu

Aby znaleźć postać wyrażenia, które określa liczbę I działań (porównań i przestawień elementów) (wykonywanych w algorytmie sortowania przez wybór.

I wystarczy zauważyć, że jest on iteracja algorytmu znajdowania najmniejszego elementu w ciągu, który w kolejnych iteracjach jest coraz krótszy. Liczba przestawień jest równa liczbie iteracji, wynosi wiec n-1, zaś liczba porównań wynosi (n-1) + (n-2) + ... + 2 + 1. Wartość tej sumy można obliczyć wieloma sposobami, wynosi ona: n(n-1)/2

12