Implementacja algorytmu sortowania przez wybieranie w języku Python

Analiza złożoności czasowej i pamięciowej

Aby wyznaczyć złożoność czasową algorytmu sortowania przez wybieranie, przeanalizujmy liczbę operacji podstawowychoperacja podstawowaoperacji podstawowych. Są nimi m.in. porównania i zamiany elementów.

Aby obliczyć liczbę porównań, zastanówmy się, ile razy wykona się wewnętrzna pętla w linii siódmej. W pierwszej iteracji wartość j będzie przyjmować wartości: 1, 2, ..., n - 1. Z każdą kolejną iteracją pętli zewnętrznej pętla wewnętrzna będzie wykonywać o jedną iterację mniej. Możemy zatem policzyć, że pętla ta będzie wykonywać się kolejno n - 1, n - 2, ..., 1 razy. Sumując wyrażenia za pomocą wzoru na sumę ciągu arytmetycznego, otrzymamy liczbę porównań równą $\frac{n(n-1)}{2}$. Liczba zamian jest równa $n - 1$. Złożoność czasowa algorytmu sortowania przez wybieranie jest zatem kwadratowa. W notacji wielkiego O będzie to złożoność czasowa $O(n^2)$.

Wyznaczenie złożoności pamięciowej opiera się na obserwacji, że nie używamy dodatkowej pamięci ponad stałą liczbę zmiennych i tablicę danych wejściowych. Jest ona stała, co w notacji wielkiego O zapisujemy jako $O(1)$. Algorytm sortowania przez wybieranie jest zatem algorytmem sortowania w miejscu.

Słownik