Wszyscy doskonale wiedzą, że z klasy rodzajów wymiany, najbardziej szybka metoda jest tzw szybkie sortowanie. Pisze się na ten temat rozprawy doktorskie, poświęca mu się wiele artykułów na temat Habré, na jego podstawie wymyśla się złożone algorytmy hybrydowe. Ale dzisiaj nie rozmawiamy szybkie sortowanie, ale o innej metodzie wymiany - starym dobrym sortowanie bąbelkowe oraz jego ulepszenia, modyfikacje, mutacje i odmiany.

Praktyczne wyniki z tych metod nie są tak gorące i wielu habrauserów przeszło przez to wszystko w pierwszej klasie. Dlatego artykuł adresowany jest do osób, które dopiero zainteresowały się teorią algorytmów i stawiają w tym kierunku pierwsze kroki.

obraz: bąbelki

Dziś porozmawiamy o najprostszych sortowanie giełd.

Jeśli ktoś jest zainteresowany, to powiem, że są inne zajęcia - sortowanie wyboru, sortowanie przez wstawianie, sortuj przez scalanie, dystrybucja sortowania, rodzaje hybrydowe oraz sorty równoległe. Nawiasem mówiąc, są sortowania ezoteryczne. Są to różne fałszywe, zasadniczo nierealne, komiksowe i inne pseudoalgorytmy, o których jakoś napiszę kilka artykułów w hubie IT-humor.

Ale to nie ma nic wspólnego z dzisiejszym wykładem, teraz interesują nas tylko proste rodzaje wymiany. Istnieje też całkiem sporo samych rodzajów wymiany (znam kilkanaście), więc rozważymy tzw sortowanie bąbelkowe i kilka innych, które są z nim blisko spokrewnione.

Z góry uprzedzę, że prawie wszystkie powyższe metody są bardzo powolne i nie będzie dogłębnej analizy ich złożoności czasowej. Jedne są szybsze, inne wolniejsze, ale z grubsza można powiedzieć, że średnio O(n 2). Nie widzę też powodu, aby zaśmiecać artykuł implementacjami w jakimkolwiek języku programowania. Zainteresowani mogą łatwo znaleźć przykłady kodu na Rosetcie, Wikipedii lub gdzie indziej.

Wróćmy jednak do sortowania wymian. Porządkowanie następuje w wyniku powtarzającej się sekwencyjnej iteracji tablicy i porównywania ze sobą par elementów. Jeśli porównywane elementy nie są posortowane względem siebie, to je zamieniamy. Pytanie tylko jak dokładnie ominąć tablicę i na jakiej podstawie wybrać pary do porównania.

Zacznijmy nie od referencyjnego sortowania bąbelkowego, ale od algorytmu o nazwie ...

Niemądry sort

Sortowanie jest naprawdę głupie. Przeglądamy tablicę od lewej do prawej i po drodze porównujemy sąsiadów. Jeśli spotkamy parę wzajemnie nieposortowanych elementów, to zamieniamy je i wracamy do kwadratu, czyli do samego początku. Przechodzimy i ponownie sprawdzamy tablicę, jeśli ponownie spotkamy „niewłaściwą” parę sąsiednich elementów, to zamieniamy się miejscami i zaczynamy od nowa. Kontynuujemy, aż tablica zostanie powoli posortowana.

„Więc każdy głupiec wie, jak sortować” - powiesz i będziesz miał absolutną rację. Dlatego sortowanie nazywa się „głupim”. W tym wykładzie będziemy konsekwentnie ulepszać i modyfikować tą drogą. Teraz ma złożoność czasową O(n 3), po dokonaniu jednej korekty, już doprowadzimy do O(n 2), potem trochę bardziej przyspieszamy, potem trochę bardziej, a na koniec dostajemy O(n dziennik n) - i wcale nie będzie to „Szybkie sortowanie”!

Zróbmy jedno ulepszenie do głupiego sortowania. Po znalezieniu dwóch sąsiadujących ze sobą nieposortowanych elementów podczas przejścia i ich zamianie, nie cofniemy się na początek tablicy, ale spokojnie będziemy kontynuować jej przechodzenie do samego końca.

W tym przypadku nie mamy przed sobą nic więcej niż dobrze znane...

sortowanie bąbelkowe

Lub sortowanie według prostych wymian. Nieśmiertelny klasyk gatunku. Zasada działania jest prosta: obchodzimy tablicę od początku do końca, jednocześnie zamieniając nieposortowane sąsiednie elementy. W wyniku pierwszego przejścia maksymalny element „wyskoczy” na ostatnie miejsce. Teraz ponownie omijamy nieposortowaną część tablicy (od pierwszego elementu do przedostatniego) i po drodze zmieniamy nieposortowanych sąsiadów. Drugi co do wielkości element znajdzie się na przedostatnim miejscu. Kontynuując w tym samym duchu, ominiemy stale zmniejszającą się nieposortowaną część tablicy, przesuwając znalezione maksima do końca.

Jeśli nie tylko zepchniemy wzloty do końca, ale także przesuniemy dołki na początek, to otrzymamy…

sortowanie z wytrząsaniem

ona jest sortuj losowo, ona jest sortowanie koktajli. Proces zaczyna się jak w „bańce”: wyciskamy maksimum na same podwórka. Następnie zawracamy o 180 0 i jedziemy w przeciwnym kierunku, tocząc się już do początku nie maksimum, ale minimum. Po posortowaniu pierwszego i ostatniego elementu w tablicy ponownie wykonujemy salto. Przechodząc kilka razy w tę i z powrotem, w końcu kończymy proces, znajdując się w środku listy.

Sortowanie wytrząsające działa nieco szybciej niż sortowanie bąbelkowe, ponieważ zarówno wzloty, jak i upadki naprzemiennie migrują przez tablicę we właściwych kierunkach. Ulepszenia, jak mówią, są oczywiste.

Jak widać, jeśli kreatywnie podejdziesz do procesu iteracji, to wypchnięcie ciężkich (lekkich) elementów na końce tablicy jest szybsze. Dlatego rzemieślnicy zaproponowali kolejną niestandardową „mapę drogową”, aby ominąć listę.

Rodzaj parzysty-nieparzysty

Tym razem nie będziemy biegać po tablicy w tę i z powrotem, ale ponownie wrócimy do idei systematycznego omijania od lewej do prawej, a jedynie zrobimy szerszy krok. W pierwszym przebiegu elementy z nieparzystym kluczem są porównywane z sąsiadami na podstawie parzystych miejsc (pierwszy jest porównywany z drugim, potem trzeci z czwartym, piąty z szóstym itd.). Następnie odwrotnie – elementy „parzyste” są porównywane/zmieniane na „nieparzyste”. Potem znowu "nieparzyste-parzyste", potem znowu "parzyste-nieparzyste". Proces zatrzymuje się, gdy po dwóch kolejnych przejściach przez tablicę („nieparzyste-parzyste” i „parzyste-nieparzyste”) nie doszło do wymiany. Więc załatwione.

W zwykłym „bańce” podczas każdego przejścia systematycznie wyciskamy aktualne maksimum do końca tablicy. Jeśli pominiemy indeksy parzyste i nieparzyste, to jednocześnie wszystkie mniej lub bardziej duże elementy tablicy są jednocześnie przesuwane w prawo o jedną pozycję w jednym przebiegu. W ten sposób robi się szybciej.

Przeanalizujmy ostatni remont* dla Sortowanie żarówek** - Sortowanie według grzebienia***. Ta metoda układa się bardzo szybko, O(n 2) to jego najgorsza złożoność. Średnio z biegiem czasu mamy O(n dziennik n), a najlepiej nawet, nie wierz w to O(n). To znaczy, bardzo godny konkurent dla każdego "szybkiego rodzaju" i to, pamiętaj, bez użycia rekurencji. Obiecałem jednak, że dzisiaj nie zagłębimy się w prędkości przelotowe, więc milczę i przejdę bezpośrednio do algorytmu.

To wina wszystkich żółwi

Mała historia. W 1980 roku Włodzimierz Dobosiewicz wyjaśnił, dlaczego sortowanie bąbelkowe i jego pochodne są tak powolne. Chodzi o żółwie. „Żółwie” to małe przedmioty, które znajdują się na końcu listy. Jak być może zauważyłeś, sortowanie bąbelkowe koncentruje się na „królikach” (nie mylić z „królikami” Babuszkina) – elementach o dużej wartości na początku listy. Bardzo żwawo zbliżają się do mety. Ale powolne gady niechętnie czołgają się na start. Możesz dostosować "tortillo" za pomocą grzebienie.

obraz: winny żółw

Sortowanie grzebieni

W „bańce”, „wstrząsaczu” i „parzyste-nieparzyste” podczas iteracji po tablicy są porównywane sąsiednie elementy. Główną ideą „grzebienia” jest początkowe zabranie wystarczającej ilości długi dystans między porównywanymi elementami i w miarę sortowania tablicy, zawęź tę odległość do minimum. W ten sposób niejako przeczesujemy macierz, stopniowo wygładzając ją w coraz dokładniejsze pasma.

Lepiej jest brać początkową przerwę między porównywanymi elementami nie byle jak, ale biorąc pod uwagę specjalną wartość zwaną czynnik redukujący, którego optymalna wartość wynosi około 1,247. Po pierwsze, odległość między elementami jest równa wielkości tablicy podzielonej przez współczynnik redukcji(wynik jest naturalnie zaokrąglany do najbliższej liczby całkowitej). Następnie, po przejściu przez tablicę tym krokiem, ponownie dzielimy krok przez współczynnik redukcji i ponownie przejrzyj listę. Trwa to do momentu, gdy różnica indeksów osiągnie jeden. W takim przypadku tablica jest ponownie sortowana za pomocą zwykłego bąbelka.

Optymalna wartość została ustalona eksperymentalnie i teoretycznie współczynnik redukcji:

Kiedy wynaleziono tę metodę, na przełomie lat 70. i 80. niewiele osób zwracało na nią uwagę. Dekadę później, kiedy programowanie przestało być udziałem naukowców i inżynierów IBM, a już szybko nabierało charakteru masowego, metoda została ponownie odkryta, zbadana i spopularyzowana w 1991 roku przez Stephena Laceya i Richarda Boxa.

To właściwie wszystko, co chciałem powiedzieć o sortowaniu bąbelkowym i innych podobnych.

- Notatki

* skrócony ( ukraiński) - poprawa
** Sortowanie z żarówką ( ukraiński) – Sortowanie bąbelkowe
*** Sortowanie według grzebienia ( ukraiński) – Sortowanie grzebieni

Szacuje się, że nawet jedna czwarta czasu, jaki scentralizowane komputery poświęcają na sortowanie danych. Dzieje się tak, ponieważ znacznie łatwiej jest znaleźć wartość w tablicy, która została wcześniej posortowana. W przeciwnym razie wyszukiwanie jest trochę jak szukanie igły w stogu siana.

Są programiści, którzy cały swój czas pracy poświęcają na studiowanie i wdrażanie algorytmów sortujących. Dzieje się tak, ponieważ zdecydowana większość oprogramowania w biznesie obejmuje zarządzanie bazami danych. Ludzie cały czas wyszukują informacje w bazach danych. Oznacza to, że algorytmy wyszukiwania są bardzo poszukiwane.

Ale jest jedno „ale”. Algorytmy wyszukiwania pracuj znacznie szybciej z bazami danych, które są już posortowane. W takim przypadku wymagane jest tylko wyszukiwanie liniowe.

Chociaż komputery są w pewnym momencie bez użytkowników, algorytmy sortowania nadal działają z bazami danych. Po raz kolejny pojawiają się osoby wyszukujące, a baza danych została już posortowana według tego lub innego celu wyszukiwania.

W tym artykule przedstawiono przykłady implementacji standardowych algorytmów sortowania.

Sortowanie wyboru

Aby posortować tablicę w porządku rosnącym, w każdej iteracji znajdź element z najwyższa wartość. Dzięki niemu musisz zamienić ostatni element. Kolejny element o najwyższej wartości staje się przedostatnim. Powinno to nastąpić, dopóki elementy znajdujące się na pierwszych miejscach w tablicy nie będą w odpowiedniej kolejności.

Kod C++

void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i dane[k])( j = k; )) tmp = dane[i]; dane[i] = dane[j]; dane[j] = tmp; ) )

Sortowanie bąbelkowe

Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia, jeśli następny element jest mniejszy niż poprzedni. Wymaga wielu przejść przez dane. Podczas pierwszego przebiegu dopasowywane są pierwsze dwa elementy tablicy. Jeśli nie są w porządku, są zamieniane, a następnie porównywane są elementy z następnej pary. Pod tym samym warunkiem zamieniają się również miejscami. W ten sposób sortowanie odbywa się w każdym cyklu, aż do osiągnięcia końca tablicy.

Kod C++

void SortAlgo::bubbleSort(int dane, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)( jeśli (dane[j])

Sortowanie przez wstawianie

Sortowanie przez wstawienie dzieli tablicę na dwa regiony: uporządkowany i nieuporządkowany. Początkowo cała tablica jest obszarem nieuporządkowanym. W pierwszym przejściu pierwszy element z nieuporządkowanego regionu jest usuwany i umieszczany we właściwej pozycji w uporządkowanym regionie.

W każdym przejściu rozmiar uporządkowanego regionu zwiększa się o 1, a rozmiar nieuporządkowanego regionu zmniejsza się o 1.

Główna pętla biegnie w zakresie od 1 do N-1. W j-tej iteracji element [i] jest wstawiany we właściwej pozycji w uporządkowanym obszarze. Odbywa się to poprzez przesunięcie wszystkich elementów uporządkowanego regionu, które są większe niż [i] o jedną pozycję w prawo. [i] jest wstawiane w odstępie między elementami, które są mniejsze niż [i] i tymi, które są większe niż [i].

Kod C++

void SortAlgo::insertionSort(int dane, int lenD) ( klucz int = 0; int i = 0; for (int j = 1; j =0 && data[i]>klucz)( dane = dane[i]; i = i-1; dane=klucz; )) )

Scal sortuj

Kod C++

void SortAlgo::mergeSort(int dane, int lenD) ( if (lenD>1)( int środek = lenD/2; int rem = lenD-środek; int * L = nowy int ; int * R = nowy int ; for ( int i=0;i

Szybkie sortowanie

Quicksort wykorzystuje algorytm dziel i zwyciężaj. Rozpoczyna się od podzielenia oryginalnej tablicy na dwa regiony. Te części znajdują się po lewej i prawej stronie zaznaczonego elementu, zwanego osią. Pod koniec procesu jedna część będzie zawierać elementy mniejsze niż oś, a druga część będzie zawierać elementy większe niż oś.

Kod C++

void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = nowy int ; int * R = nowy int ; oś = dane; for (i=0;i

Cześć wszystkim!

Dzisiaj przeanalizujemy sortowanie metodą „bąbelkową”. Algorytm ten jest często przekazywany w szkołach i na uniwersytetach, więc będziemy używać języka Pascal. Czym więc jest sortowanie? Sortowanie to porządkowanie elementów od najmniejszego do największego (sortowanie rosnąco) lub od największego do najmniejszego elementu (sortowanie malejąco). Tablice są zwykle posortowane.

Istnieją różne algorytmy sortowania. Niektóre są dobre w sortowaniu dużej liczby przedmiotów, inne są bardziej wydajne przy bardzo niewielu przedmiotach. Nasza metoda bąbelkowa jest charakterystyczna:

Plusy:

• Łatwość implementacji algorytmu
• Piękne imię

Minusy:

• Jedna z najwolniejszych metod sortowania (Czas wykonania zależy kwadratowo od długości tablicy n 2)
• Prawie nigdy nie używany w prawdziwym życiu (używany głównie do celów edukacyjnych)

Powiedzmy, że mamy tablicę: 3 1 4 2

Algorytm: Bierzemy element tablicy, porównujemy go z następnym, jeśli nasz element jest większy niż następny, to zamieniamy je. Po przejrzeniu całej tablicy możemy być pewni, że maksymalny element zostanie "wyrzucony" - i będzie ostatnim. Tym samym mamy już dokładnie jeden element na swoim miejscu. Dlatego musimy je wszystkie umieścić na swoich miejscach, dlatego musimy powtórzyć tę operację, tyle razy, ile mamy elementów tablicy minus 1. Ostatni element pojawi się automatycznie, jeśli pozostałe są na swoich miejscach.

Wróćmy do naszej tablicy: 3 1 4 2
Bierzemy pierwszy element „3” i porównujemy go z następnym „1”. Dlatego „3” > „1”, a następnie zamień:
1 3 4 2
Teraz porównujemy „3” i „4”, trzy to nie więcej niż cztery, więc nic nie robimy. Następnie porównujemy „4” i „2”. Cztery to więcej niż dwa - więc zamieniamy się miejscami: 1 3 2 4. Cykl się skończył. Więc największy element powinien już być na swoim miejscu!! Widzimy, że tak się stało. Wszędzie tam, gdzie znajduje się „4” (nasz największy element) – po przejściu przez całą tablicę nadal będzie ostatnim. Analogicznie – tak jak bańka powietrza unosi się w wodzie – tak więc nasz element unosi się w szyku. Dlatego algorytm nazywa się „Sortowaniem bąbelkowym”. Aby ustawić kolejny element, konieczne jest ponowne rozpoczęcie cyklu, ale ostatniego elementu nie można już brać pod uwagę, ponieważ stoi na swoim miejscu.

Porównujemy „1” i „3” – nic nie zmieniamy.
Porównaj "3" i "2" - Trzy to więcej niż dwa, więc zamieniamy się miejscami. Okazuje się: 1 2 3 4. Drugi cykl jest zakończony. Zrobiliśmy już dwa cykle - co oznacza, że ​​możemy śmiało powiedzieć, że mamy już posortowane dwa ostatnie elementy. Pozostaje nam posortować trzeci element, a czwarty automatycznie wpadnie we właściwe miejsce. Jeszcze raz porównujemy pierwszy element i drugi – widzimy, że mamy już wszystko na swoim miejscu, co oznacza, że ​​tablicę można uznać za posortowaną w rosnącej kolejności elementów.

Teraz pozostaje zaprogramować ten algorytm w Pascalu. const n = 4; (Zaczynamy stałą, będzie to długość tablicy) var i, j, k:integer; (Dwie zmienne dla pętli zagnieżdżonej, jedna dla zamiany elementów) m:array of integer; (Utwórz tablicę) begin (Poprosimy o tablicę z klawiatury:) Writeln("Wpisz tablicę:"); dla i:=1 do n rozpocznij Writeln(i, " element:"); readln(m[i]); koniec; (Pętla zewnętrzna jest odpowiedzialna za to, że musimy powtórzyć pętlę wewnętrzną tyle razy, ile mamy elementów tablicy minus 1.) dla rozpoczęcia i:=1 do n-1 (Pętla wewnętrzna już iteruje po elementach i porównuje ze sobą.) dla j :=1 do n-i zacznij (Jeśli element jest większy niż następny, zamień.) if m[j]>m to zacznij k:=m[j]; m[j]:=m; m:=k; koniec; koniec; koniec; (Wydrukuj wynik:) for i:=1 do n do Write(m[i], " "); koniec.
Oto wynik:

A oto samouczek wideo

Podczas pracy z tablicami danych często zdarza się, że: sortowanie w porządku rosnącym lub malejącym, tj. usprawnienie. Oznacza to, że elementy tej samej tablicy muszą być ułożone ściśle w kolejności. Na przykład w przypadku sortowania w porządku rosnącym poprzedzający element musi być mniejszy (lub równy) kolejnemu elementowi.

Rozwiązanie

Istnieje wiele metod sortowania. Niektóre z nich są bardziej wydajne, inne są łatwiejsze do zrozumienia. Wystarczająco proste do zrozumienia jest sortowanie metoda bąbelkowa, który jest również nazywany prosta metoda wymiany. Co to jest i dlaczego ma tak dziwną nazwę: „metoda bąbelkowa”?

Jak wiesz, powietrze jest lżejsze od wody, więc bąbelki powietrza unoszą się na wodzie. To tylko analogia. W rosnącym sortowaniu bąbelkowym lżejsze (o niższej wartości) elementy stopniowo „pływają” na początek tablicy, podczas gdy cięższe jeden po drugim opadają na dół (na koniec tablicy).

Algorytm i cechy tego rodzaju są następujące:

1. Podczas pierwszego przejścia przez tablicę elementy są porównywane parami: pierwszy z drugim, drugi z trzecim, trzeci z czwartym i tak dalej. Jeśli poprzedni element jest większy niż następny, są one zamieniane.
2. Nietrudno zgadnąć, że stopniowo największa liczba jest ostatnia. Reszta tablicy pozostaje nieposortowana, chociaż obserwuje się pewien ruch elementów o niższej wartości na początek tablicy.
3. Przy drugim przejeździe nie ma potrzeby porównywania ostatniego elementu z przedostatnim. Ostatni element jest już na miejscu. Oznacza to, że liczba porównań będzie o jedno mniejsza.
4. Przy trzecim przejściu nie trzeba już porównywać przedostatniego i trzeciego elementu od końca. Dlatego liczba porównań będzie o dwa mniej niż w pierwszym przejściu.
5. W końcu podczas iteracji po tablicy, gdy do porównania pozostały tylko dwa elementy, wykonywane jest tylko jedno porównanie.
6. Po tym pierwszy element nie ma z czym porównywać, dlatego ostatnie przejście przez tablicę nie jest potrzebne. Innymi słowy, liczba przejść przez tablicę to m-1, gdzie m to liczba elementów tablicy.
7. Liczba porównań w każdym przebiegu to m-i, gdzie i to numer przebiegu tablicy (pierwszy, drugi, trzeci itd.).
8. Przy wymianie elementów tablicy zwykle używa się zmiennej „buforowej” (trzeciej), w której tymczasowo umieszczana jest wartość jednego z elementów.

Program Pascala:

const m = 10 ; var arr: tablica [1 .. m ] liczby całkowitej ; i, j, k: liczba całkowita ; rozpocznij randomizację; pisać ( „Tablica źródłowa:”) ; for i : = 1 do m zacznij arr[ i] : = random(256 ) ; napisz (arr[ i] : 4 ) ; koniec ; napisane ; napisane ; for i : = 1 do m- 1 wykonaj dla j : = 1 do m- i wykonaj jeśli przyp[ j] > przyp[ j+1 ] to zacznij k : = przyp[ j] ; przyp[ j] := przyp[ j+ 1 ] ; arr[ j+1 ] : = k koniec ; pisać ( "Tablica posortowana:") ; dla i := 1 do m napisz (arr[ i] : 4 ) ; napisane ; przeczytaj koniec .

Ułóżmy tablicę od góry do dołu, od elementu zerowego do ostatniego.

Idea metody: etap sortowania polega na przechodzeniu od dołu do góry przez tablicę. Po drodze przegląda się pary sąsiadujących ze sobą elementów. Jeśli elementy jakiejś pary są w złej kolejności, to je zamieniamy.

Po przejściu zera przez tablicę „najlżejszy” element znajduje się „nad” – stąd analogia z bańką. Kolejne przejście do drugiego elementu od góry, tym samym drugi co do wielkości element jest podnoszony do właściwej pozycji...

Wykonujemy przejścia wzdłuż coraz mniejszej części tablicy, aż pozostanie w niej tylko jeden element. Na tym kończy się sortowanie, ponieważ sekwencja jest sortowana w porządku rosnącym.

Szablon void bubbleSort(T a, długi rozmiar) ( long i, j; T x; for(i=0; i< size; i++) { // i - numer przepustki for(j = rozmiar-1; j > i; j--) ( // wewnętrzna pętla przejść jeśli (a > a[j]) ( x=a; a=a[j]; a[j]=x; )) ) )

Średnia liczba porównań i wymian ma kwadratowy rząd wzrostu: Theta(n 2), stąd możemy stwierdzić, że algorytm bańki jest bardzo powolny i nieefektywny.
Ma jednak ogromny plus: jest prosty i można go w dowolny sposób ulepszyć. Co teraz zrobimy.

Najpierw rozważ sytuację, w której na żadnym z przepustek nie doszło do wymiany. Co to znaczy?

Oznacza to, że wszystkie pary są we właściwej kolejności, więc tablica jest już posortowana. I nie ma sensu kontynuować procesu (zwłaszcza jeśli tablica była posortowana od samego początku!).

Tak więc pierwszym usprawnieniem algorytmu jest zapamiętanie, czy na danym przejściu dokonano jakiejkolwiek wymiany. Jeśli nie, algorytm się kończy.

Proces doskonalenia można kontynuować, jeśli pamiętamy nie tylko sam fakt wymiany, ale także indeks ostatniej wymiany k. Rzeczywiście: wszystkie pary sąsiednich elementów o indeksach mniejszych niż k są już w wymaganej kolejności. Kolejne przejścia mogą kończyć się przy indeksie k zamiast przesuwać się w górę do ustalonej górnej granicy i.

Jakościowo różne ulepszenie algorytmu można uzyskać z następującej obserwacji. Chociaż lekki bąbelek od dołu uniesie się do góry w jednym przejściu, ciężkie bąbelki opadają z minimalną szybkością jednego kroku na iterację. Tak więc tablica 2 3 4 5 6 1 zostanie posortowana w 1 przejściu, podczas gdy posortowanie sekwencji 6 1 2 3 4 5 będzie wymagało 5 przejść.

Aby uniknąć tego efektu, możesz zmieniać kierunek kolejnych przejść. Wynikowy algorytm jest czasami określany jako „ shaker-sort".

Szablon void shakerSort(T a, długi rozmiar) ( długi j, k = rozmiar-1; długi lb=1, ub = rozmiar-1; // granice nieposortowanej części tablicy Tx; robić( // przejdź od dołu do góry for(j=ub; j>0; j--) ( jeśli (a > a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) lb =k+1; // przejście od góry do dołu dla (j=1; j<=ub; j++) { if (a >a[j]) (x=a; a=a[j]; a[j]=x; k=j;)) ub = k-1; ) podczas (lb< ub); }

W jakim stopniu opisane zmiany wpłynęły na skuteczność metody? Średnia liczba porównań, choć zmniejszyła się, pozostaje O(n 2), natomiast liczba wymian w ogóle się nie zmieniła. Średnia (to też najgorsza) liczba operacji pozostaje kwadratowa.

Dodatkowa pamięć oczywiście nie jest wymagana. Zachowanie ulepszonej (ale nie początkowej) metody jest całkiem naturalne, prawie posortowana tablica zostanie posortowana znacznie szybciej niż losowa. Sortowanie bąbelkowe jest stabilne, ale sortowanie z wytrząsaniem traci tę jakość.

W praktyce metoda bąbelkowa, nawet z ulepszeniami, jest niestety zbyt wolna. Dlatego prawie nigdy nie jest używany.