Lekcja: "Algorytmy sortujące - sortowanie bąbelkowe, część II"
Ostatnia zamiana elementów wyznaczy pozycję końcową dla następnego obiegu. W każdym obiegu sortującym najstarszy element jest zawsze umieszczany na swojej docelowej pozycji. Jeśli ostatnia zamiana elementów wystąpiła na pozycji i-tej, to w następnym obiegu porównywanie elementów zakończymy na pozycji o 1 mniejszej - w ten sposób nie będziemy sprawdzać już najstarszego elementu z poprzedniego obiegu.
Sortowanie prowadzimy do momentu, aż w obiegu sortującym nie wystąpi ani jedna zamiana elementów.
Teoretycznie powinno to zoptymalizowaćalgorytm, ponieważ są sortowane tylko niezbędne fragmenty zbioru – zostaną pominięte obszary posortowane, które tworzą się na końcu i na początku zbioru. Jednak zysk nie będzie oszałamiający w przypadku zbioru nieuporządkowanego lub posortowanego odwrotnie (może się zdarzyć, że ewentualne korzyści czasowe będą mniejsze od czasu wykonywania dodatkowych operacji). Jednakże dla zbiorów w dużym stopniu uporządkowanych możemy uzyskać całkiem rozsądny algorytm sortujący prawie w czasie liniowym O(n).
