Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"
Podsumowanie
W prezentacji przedstawiono dwa rodzaje algorytmów: algorytm stabilny – na przykładzie sortowania przez wstawianie i algorytm niestabilny - na przykładzie sortowania przez wybór.
Algorytm sortowania przez wstawianie nie uwzględnia faktu posortowania zbioru. Jednakże również nie wyróżnia on przypadku posortowania zbioru w kierunku odwrotnym. Dla tego algorytmu złożoność czasowa nie zależy od rozkładu elementów w sortowanym zbiorze.
Przy sortowaniu przez wybór algorytm wykorzystuje fakt posortowania zbioru. Dla zbiorów w znacznym stopniu uporządkowanych klasa czasowej złożoności obliczeniowej algorytmu jest prawie liniowa. Czas sortowania takich zbiorów jest bardzo krótki.
Najbardziej niekorzystnym przypadkiem jest sortowanie zbioru posortowanego odwrotnie - czas sortowania jest najdłuższy. Czas sortowania zbioru o losowym rozkładzie elementów jest o połowę krótszy.
Algorytm sortowania przez wybór jest dużo lepszy od sortowania przez wstawianie w przypadku zbiorów w znacznym stopniu uporządkowanych. Również zbiory o losowym rozkładzie elementów będą posortowane szybciej. Jedynie w przypadku pesymistycznym, gdy zbiór jest posortowany odwrotnie, algorytm jest wolniejszy od algorytmu sortowania przez wybór. Te cechy czynią algorytm sortowania przez wstawianie zalecanym, prostym algorytmem sortującym klasy O(n2).
