Sortowanie: Różnice pomiędzy wersjami

 

Jeżeli algorytm sortowania zamienia tylko elementy sąsiadujące ze sobą, musi dokonać średnio <math>\frac{n}{3}</math> zamian dla każdego z ''n'' elementów. A więc średnia liczba porównań wynosi <math>n\cdot \frac{n}{3}= \frac{n^2}{3}=O(n^2)</math>. Jedynym sposobem zmniejszenia asymptotycznej złożoności algorytmów sortujących jest wprowadzenie możliwości zamieniania elementów nie sąsiadujących ze sobą.

 

==Przykładowe algorytmy sortowania==