Lekcja: "Algorytmy sortujące - sortowanie bąbelkowe, część II"
Dalsze optymalizacje
Czy jest możliwe dalsze ulepszanie – optymalizacja algorytmu sortowania bąbelkowego? Tak, jednak zaczynamy już osiągać kres możliwości, ponieważ ulepszenia polegają jedynie na redukcji operacji pustych.
Wykorzystamy informację o miejscu wystąpienia zamiany elementów (czyli o miejscu wykonania operacji sortującej).
Jeśli w obiegu sortującym wystąpi pierwsza zamiana na pozycji i-tej, to w kolejnym obiegu rozpoczniemy sortowanie od pozycji o jeden mniejszej (chyba, że pozycja 7-ma była pierwszą pozycją w zbiorze). Zamiana spowodowała, iż młodszy element znalazł się na pozycji i-tej. Ponieważ w obiegu sortującym młodszy element zawsze przesuwa się o 1 pozycję w kierunku początku zbioru, to nie ma sensu sprawdzanie pozycji od 1 doi-2, ponieważ w poprzednim obiegu zostały one już sprawdzone, nie wystąpiła na nich zamiana elementów, zatem elementy na pozycjach od 1 doi-2 są chwilowo w dobrej kolejności względem siebie. Brak jest tylko pewności co do pozycji i-1-szej oraz i-tej, ponieważ ostatnia zamiana elementów umieściła na i-tej pozycji młodszy element, który prawdopodobnie należy wymienić z elementem na pozycji wcześniejszej, czyli i-1. W ten sposób określimy początkową pozycję, od której rozpoczniemy sortowanie elementów w następnym obiegu sortującym.