Mindenki jól tudja, hogy a cserefajták közül a legjobban gyors módszer az ún gyors válogatás. Értekezések születnek róla, Habréról sok cikk foglalkozik, komplex hibrid algoritmusokat találnak ki az alapján. De ma nem erről beszélünk gyorsválogatás, hanem egy másik cseremódszerről – a jó öregről buborék fajtaés annak fejlesztései, módosításai, mutációi és változatai.

Ezeknek a módszereknek a gyakorlati eredménye nem olyan forró, és sok habrauser átesett mindezen az első osztályban. Ezért a cikk azoknak szól, akik most kezdtek érdeklődni az algoritmusok elmélete iránt, és megteszik az első lépéseket ebbe az irányba.

kép: buborékok

Ma a legegyszerűbbről fogunk beszélni válogató cserék.

Ha valakit érdekel, szólok, hogy vannak más órák is... kiválasztási rendezés, beillesztési rendezés, összevonási rendezés, válogatás elosztás, hibrid fajtákÉs párhuzamos rendezések. Egyébként vannak ezoterikus válogatások. Különféle kamu, alapvetően megvalósíthatatlan, komikus és egyéb ál-algoritmusokról van szó, amelyekről majd valahogy írok pár cikket az IT-humor hub-ba.

De ennek semmi köze a mai előadáshoz, minket most már csak az egyszerű cserefajták érdekelnek. Maga is jó néhány cserefajta létezik (több mint egy tucatnyit ismerek), ezért figyelembe vesszük az ún buborék fajtaés néhány más, amely szorosan kapcsolódik hozzá.

Előre figyelmeztetem, hogy a fenti módszerek szinte mindegyike nagyon lassú, és nem lesz időbeli összetettségük mélyreható elemzése. Van, amelyik gyorsabb, van, amelyik lassabb, de durván fogalmazva átlagosan ezt mondhatjuk O(n 2). Nem látok okot arra sem, hogy a cikket telezsúfoljam bármilyen programozási nyelv implementációjával. Az érdeklődők könnyen találhatnak kódpéldákat a Rosettán, a Wikipédián vagy máshol.

De térjünk vissza a cserék rendezéséhez. A rendezés a tömb ismételt szekvenciális iterációja és az elempárok egymással való összehasonlítása eredményeként jön létre. Ha az összehasonlított elemek nincsenek egymáshoz képest rendezve, akkor felcseréljük őket. A kérdés csak az, hogy pontosan hogyan kerüljük ki a tömböt, és milyen alapon válasszunk párokat az összehasonlításhoz.

Ne a referenciabuborék-rendezéssel kezdjük, hanem egy algoritmussal, amelyet ...

Hülye fajta

A válogatás tényleg hülyeség. Végignézzük a tömböt balról jobbra, és összehasonlítjuk a szomszédokat. Ha találkozunk egy pár kölcsönösen rendezetlen elemmel, akkor felcseréljük őket, és visszatérünk az elsőhöz, vagyis a legelejére. Átmegyünk és újra ellenőrizzük a tömböt, ha ismét találkozunk a „rossz” szomszédos elempárral, akkor helyet cserélünk és kezdjük elölről. Addig folytatjuk, amíg a tömb lassan rendeződik.

„Tehát minden bolond tudja, hogyan kell válogatni” – mondod, és teljesen igazad lesz. Ezért nevezik a válogatást "hülyének". Ebben az előadásban következetesen javítani és módosítani fogunk Ily módon. Most már bonyolult az idő O(n 3), miután egy javítást végrehajtottunk, máris eljuttatjuk O(n 2), majd gyorsíts még egy kicsit, aztán még egy kicsit, és a végén megkapjuk O(n log n) - és egyáltalán nem lesz "Gyorsrendezés"!

Egyetlen fejlesztést tegyünk a hülye válogatáson. Miután az áthaladás során találtunk két szomszédos rendezetlen elemet, és felcseréltük őket, nem gurulunk vissza a tömb elejére, hanem nyugodtan folytatjuk a bejárást a legvégéig.

Ebben az esetben nem áll előttünk más, mint a jól ismert ...

buborék fajta

Vagy válogatás egyszerű cserékkel. A műfaj halhatatlan klasszikusa. A cselekvés elve egyszerű: körbejárjuk a tömböt az elejétől a végéig, egyidejűleg felcserélve a rendezetlent szomszédos elemek. Az első lépés eredményeként a maximális elem az utolsó helyre „felugrik”. Most ismét megkerüljük a tömb rendezetlen részét (az első elemtől az utolsó előttiig), és közben megváltoztatjuk a rendezetlen szomszédokat. A második legnagyobb elem az utolsó előtti helyen lesz. Ugyanebben a szellemben folytatva megkerüljük a tömb egyre csökkenő szortírozatlan részét, a talált maximumokat a végére tolva.

Ha nemcsak a csúcsokat toljuk a végére, hanem a mélypontokat is az elejére toljuk, akkor azt kapjuk...

shaker fajta

Ő az véletlenszerű rendezés, ő az koktélválogatás. A folyamat úgy kezdődik, mint egy „buborékban”: a maximumot a hátsó udvarokig szorítjuk. Utána 180 0 körül fordulunk, és megyünk az ellenkező irányba, közben már nem maximumot, hanem minimumot tekerünk az elejére. Miután rendeztük a tömb első és utolsó elemét, ismét bukfencet hajtunk végre. Többször oda-vissza körbejárva végül a lista közepén állva befejezzük a folyamatot.

A rázós rendezés valamivel gyorsabban működik, mint a buborékos rendezés, mivel mind a magas, mind a mélypontok felváltva vándorolnak át a tömbön a megfelelő irányba. A javulás, ahogy mondani szokás, nyilvánvaló.

Mint látható, ha kreatívan közelítjük meg az iterációs folyamatot, akkor a nehéz (könnyű) elemeket gyorsabban toljuk a tömb végére. Ezért a kézművesek egy másik, nem szabványos "útvonaltervet" javasoltak a lista megkerülésére.

Páros-páratlan fajta

Ezúttal nem a tömb körül forgolódunk össze-vissza, hanem ismét visszatérünk a balról jobbra történő szisztematikus megkerülés gondolatához, de csak egy szélesebb lépést teszünk. Az első lépésben a páratlan kulcsú elemek páros helyek alapján kerülnek összehasonlításra a szomszédokkal (az 1. a 2., majd a 3. a 4., az 5. a 6. és így tovább). Ezután fordítva - a "páros" elemeket összehasonlítja / megváltoztatja a "páratlan" elemekkel. Aztán megint "páratlan-páros", majd ismét "páros-páratlan". A folyamat leáll, ha két egymást követő áthaladás után a tömbön ("páratlan-páros" és "páros-páratlan") nem történt csere. Szóval, rendezve.

A szokásos "buborékban" minden egyes lépés során szisztematikusan kipréseljük az aktuális maximumot a tömb végére. Ha a páros és páratlan indexek mentén ugrunk, akkor a tömb összes többé-kevésbé nagy eleme egyszerre, egy futásban egy pozícióval jobbra tolódik. Így gyorsabb lesz.

Elemezzük az utolsót felújítása* Mert Izzóválogatás** - Fésűs rendezés***. Ez a módszer nagyon gyorsan rendeződik, O(n 2) a legrosszabb összetettsége. Idővel átlagosan megvan O(n log n), és még a legjobb is, ne hidd el O(n). Vagyis egy nagyon méltó versenytársa minden "gyors rendezésnek", és ez, ne feledje, rekurzió használata nélkül. Megígértem azonban, hogy ma nem merülünk el az utazósebességben, így csendben leszek, és közvetlenül az algoritmushoz megyek.

Ez mind a teknősök hibája

Egy kis háttértörténet. 1980-ban Włodzimierz Dobosiewicz elmagyarázta, miért olyan lassú a buborékos rendezés és származékai. Minden a teknősökről szól. A "teknősök" kis elemek, amelyek a lista végén találhatók. Amint azt már észrevetted, a buborékok a „nyulakra” (nem tévesztendő össze Babuskin „nyulaival”) – a lista elején található nagy értékű elemekre összpontosítanak. Nagyon lendületesen haladnak a célba. De a lassú hüllők kelletlenül másznak a rajthoz. Testreszabhatja a "tortilló" segítségével fésűk.

kép: bűnös teknős

Fésűs válogatás

A „buborék”, a „rázó” és a „páros-páratlan” tömbökben a szomszédos elemek összehasonlítása történik. A "fésű" fő ötlete az, hogy kezdetben eleget vegyen távolsági az összehasonlított elemek között és a tömb rendezésekor csökkentse ezt a távolságot a minimumra. Így mintegy fésüljük a tömböt, fokozatosan egyre pontosabb szálakká simítva.

Az összehasonlított elemek közötti kezdeti rést jobb nem akárhogyan venni, hanem egy speciális, ún redukáló tényező, amelynek optimális értéke megközelítőleg 1,247. Először is, az elemek közötti távolság egyenlő a tömb méretével osztva redukciós tényező(az eredményt természetesen a legközelebbi egész számra kerekítjük). Majd miután ezzel a lépéssel végigmentünk a tömbön, ismét elosztjuk a lépést ezzel redukciós tényezőés nézd át újra a listát. Ez addig folytatódik, amíg az indexkülönbség el nem éri az egyet. Ebben az esetben a tömb egy szabályos buborékkal újrarendezésre kerül.

Az optimális érték kísérletileg és elméletileg került megállapításra redukciós tényező:

Amikor ezt a módszert feltalálták, a 70-es, 80-as évek fordulóján kevesen figyeltek rá. Egy évtizeddel később, amikor a programozás már nem az IBM tudósai és mérnökei közé tartozott, hanem már rohamosan tömeges jelleget öltött, a módszert 1991-ben Stephen Lacey és Richard Box fedezte fel újra, kutatta és népszerűsítette.

Valójában csak ennyit szerettem volna elmondani a buborékos rendezésről és a többi hasonlóról.

- Jegyzetek

* rövidített ( ukrán) - javítás
** Válogatás izzóval ( ukrán) – Buborékos rendezés
*** Rendezés fésű szerint ( ukrán) – Fésűs válogatás

Becslések szerint a központosított számítógépek az adatok rendezésére fordított időnek akár egynegyedét is töltik. Ennek az az oka, hogy egy előre rendezett tömbben sokkal könnyebben lehet értéket találni. Egyébként a keresés kicsit olyan, mintha tűt keresnénk a szénakazalban.

Vannak programozók, akik minden munkaidejüket a rendezési algoritmusok tanulmányozásával és megvalósításával töltik. Ez azért van, mert az üzleti szoftverek túlnyomó többsége adatbázis-kezelést foglal magában. Az emberek folyamatosan keresnek információkat az adatbázisokban. Ez azt jelenti, hogy a keresési algoritmusok iránt nagy a kereslet.

De van egy "de". Keresési algoritmusok sokkal gyorsabban dolgozhat a már rendezett adatbázisokkal. Ebben az esetben csak lineáris keresésre van szükség.

Míg a számítógépek bizonyos időpontokban felhasználói nélkül vannak, a rendezési algoritmusok továbbra is működnek az adatbázisokkal. Ismét bejönnek a keresők, és az adatbázist már egy-egy keresési cél alapján rendezték.

Ez a cikk példákat ad a szabványos rendezési algoritmusok megvalósítására.

Kijelölés rendezése

Egy tömb növekvő sorrendbe rendezéséhez minden iterációnál keresse meg a következővel rendelkező elemet legmagasabb érték. Ezzel ki kell cserélni az utolsó elemet. A következő legmagasabb értékű elem lesz az utolsó előtti. Ennek addig kell történnie, amíg a tömb első helyén lévő elemek a megfelelő sorrendbe nem kerülnek.

C++ kód

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

Buborékos fajta

A buborékrendezés összehasonlítja a szomszédos elemeket, és felcseréli, ha a következő elem kisebb, mint az előző. Többszöri áthaladást igényel az adatokon. Az első lépés során a tömb első két eleme illeszkedik. Ha nem működnek, akkor felcserélik őket, majd összehasonlítják a következő pár elemeit. Ugyanilyen feltételek mellett helyet is cserélnek. Így a rendezés minden ciklusban megtörténik, amíg el nem éri a tömb végét.

C++ kód

void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)( if (adat[j]

Beillesztési rendezés

A beillesztési rendezés két régióra osztja a tömböt: rendezett és rendezetlen. Kezdetben a teljes tömb egy rendezetlen terület. Az első lépésben az első elemet a rendezetlen régióból eltávolítják és a megfelelő helyre helyezik a rendezett régióban.

Minden lépésnél a rendezett régió mérete 1-gyel nő, a rendezetlené pedig 1-gyel csökken.

A fő hurok 1 és N-1 tartományban fut. A j-edik iterációnál az [i] elem a megfelelő helyre kerül a rendezett területre. Ez úgy történik, hogy a rendezett tartomány minden elemét, amely nagyobb, mint [i], egy pozícióval jobbra tolja. Az [i] az [i]-nél kisebb és az [i]-nél nagyobb elemek közötti intervallumba kerül.

C++ kód

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

Összevonás rendezés

C++ kód

void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lennD/2; int rem = LEND-middle; int * L = new int ; int * R = new int ; for ( int i=0;i

Gyors rendezés

A Quicksort oszd meg és uralkodj algoritmust használ. Úgy kezdődik, hogy az eredeti tömböt két régióra osztja. Ezek a részek a megjelölt elemtől, az úgynevezett pivottól balra és jobbra vannak. A folyamat végén az egyik rész a pivotnál kisebb elemeket, a másik pedig a pivotnál nagyobb elemeket tartalmaz.

C++ kód

void SortAlgo::quickSort(int * adatok, 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 = new int ; int * R = new int ; pivot = adatok ; for (i=0;i

Sziasztok!

Ma a "buborék" módszerrel történő rendezést elemezzük. Ezt az algoritmust gyakran alkalmazzák iskolákban és egyetemeken, ezért a Pascal nyelvet fogjuk használni. Szóval, mi a válogatás? A rendezés az elemek sorrendje a legkisebbtől a legnagyobbig (növekvő rendezés) vagy a legnagyobbtól a legkisebbig (csökkenő rendezés). A tömbök általában rendezve vannak.

Különféle rendezési algoritmusok léteznek. Egyesek jó nagy számú cikk válogatásában, mások hatékonyabbak nagyon kevés tételnél. Buborékos módszerünk jellemző:

Előnyök:

• Az algoritmus végrehajtásának egyszerűsége
• Szép név

Mínuszok:

• Az egyik leglassabb rendezési módszer (A végrehajtási idő négyzetesen függ az n 2 tömb hosszától)
• A való életben szinte soha nem használták (főleg oktatási célokra használják)

Tegyük fel, hogy van egy tömbünk: 3 1 4 2

Algoritmus: Vegyünk egy tömbelemet, összehasonlítjuk a következővel, ha az elemünk nagyobb, mint a következő elem, akkor felcseréljük őket. A teljes tömb átjárása után biztosak lehetünk benne, hogy a maximális elemet "leugrik" - és ez az utolsó. Így már egy elem pontosan a helyén van. Mert mindegyiket a helyére kell helyeznünk, ezért ezt a műveletet meg kell ismételnünk, ahányszor van tömbelemünk mínusz 1. Az utolsó elem automatikusan megjelenik, ha a többi a helyén van.

Térjünk vissza a tömbünkhöz: 3 1 4 2
Vegyük az első "3" elemet, és összehasonlítjuk a következő "1"-el. Mert "3" > "1", majd cserélje ki:
1 3 4 2
Most összehasonlítjuk a "3"-at és a "4-et", a három nem több, mint négy, tehát nem teszünk semmit. Ezután összehasonlítjuk a "4"-et és a "2-t". A négy több mint kettő – ezért helyet cserélünk: 1 3 2 4. A ciklusnak vége. Tehát a legnagyobb elem már a helyén legyen!! Látjuk, hogy ez történt. Bárhol is található a "4" (legnagyobb elemünk) - a teljes tömb áthurkolása után is ez lesz az utolsó. Analógia - ahogy egy légbuborék lebeg a vízben -, így az elemünk egy tömbben lebeg. Ezért az algoritmust "buborékos rendezésnek" nevezik. A következő elem pozicionálásához elölről kell kezdeni a ciklust, de az utolsó elem már nem jöhet számításba, mert az a helyén áll.

Összehasonlítjuk az "1"-et és a "3-at" - semmit sem változtatunk.
Hasonlítsa össze a „3” és a „2” számot – a három több, mint kettő, ezért helyet cserélünk. Kiderült: 1 2 3 4. A második ciklus véget ért. Két ciklust már megtettünk – ami azt jelenti, hogy bátran kijelenthetjük, hogy az utolsó két elemet már rendeztük. Nekünk marad a harmadik elem rendezése, és a negyedik automatikusan a megfelelő helyre kerül. Még egyszer összehasonlítjuk az első és a második elemet - látjuk, hogy már minden a helyén van, ami azt jelenti, hogy a tömb az elemek növekvő sorrendjében rendezettnek tekinthető.

Most már csak Pascalban kell programozni ezt az algoritmust. const n = 4; (Elindítunk egy konstanst, ez lesz a tömb hossza) var i, j, k:integer; (Két változó a beágyazott ciklushoz, egy az elemek cseréjéhez) m: egész szám tömbje; (Tömb létrehozása) begin (Kérünk egy tömböt a billentyűzetről:) Writeln("Írjon be egy tömböt:"); az i:=1-től n-ig kezdődjön a Writeln(i, " elem:"); readln(m[i]); vége; (A külső ciklus felelős azért, hogy a belső ciklust annyiszor kell megismételnünk, ahány tömbelem mínusz 1 van.) Az i:=1-től n-1-ig nem kezdődik (A belső ciklus már iterál az elemeken és összehasonlítja egymással.) for j :=1 to n-i do begin (Ha az elem nagyobb, mint a következő, akkor felcseréljük.) ha m[j]>m akkor kezdődik k:=m[j]; m[j]:=m; m:=k; vége; vége; vége; (Eredmény nyomtatása:) for i:=1 to n do Write(m[i], " "); vége.
Íme az eredmény:

És itt van az oktatóvideó

Amikor adattömbökkel dolgozik, nem ritka, hogy ezt teszik növekvő vagy csökkenő sorrendbe rendezés, azaz. racionalizálása. Ez azt jelenti, hogy ugyanannak a tömbnek az elemeit szigorúan sorrendbe kell rendezni. Például növekvő sorrendben történő rendezés esetén az előző elemnek kisebbnek (vagy egyenlőnek) kell lennie a következő elemnél.

Megoldás

Számos válogatási módszer létezik. Némelyikük hatékonyabb, mások könnyebben érthetők. A válogatás megértéséhez elég egyszerű buborékos módszer, amit más néven egyszerű cseremódszer. Mi ez, és miért van ilyen furcsa neve: "buborék módszer"?

Mint tudják, a levegő könnyebb, mint a víz, ezért a légbuborékok lebegnek. Ez csak egy hasonlat. A növekvő buborékos rendezésben a könnyebb (alacsonyabb értékű) elemek fokozatosan „lebegnek” a tömb elejére, míg a nehezebbek egyenként a tömb aljára (a tömb végére) süllyednek.

Az ilyen típusú algoritmus és jellemzők a következők:

1. A tömb első áthaladása során az elemeket párban hasonlítják össze: az elsőt a másodikkal, majd a másodikat a harmadikkal, majd a harmadikat a negyedikkel, és így tovább. Ha az előző elem nagyobb, mint a következő, akkor felcserélődnek.
2. Nem nehéz kitalálni, hogy fokozatosan a legnagyobb szám az utolsó. A tömb többi része rendezetlen marad, bár megfigyelhető az alacsonyabb értékű elemek mozgása a tömb elejére.
3. A második lépésnél nem kell összehasonlítani az utolsó elemet az utolsó előttivel. Az utolsó elem már a helyén van. Ez azt jelenti, hogy az összehasonlítások száma eggyel kevesebb lesz.
4. A harmadik menetnél már nem kell összehasonlítani az utolsó előtti és a harmadik elemet a végétől. Ezért az összehasonlítások száma kettővel kevesebb lesz, mint az első menetben.
5. Hiszen a tömb iterációja során, amikor már csak két elem maradt az összehasonlításra, csak egy összehasonlítás történik.
6. Ezt követően az első elemnek nincs mihez hasonlítania, ezért nincs szükség a tömb utolsó lépésére. Más szóval, a tömbön való áthaladások száma m-1, ahol m a tömbelemek száma.
7. Az összehasonlítások száma minden lépésben m-i, ahol i a tömb lépésszáma (első, második, harmadik stb.).
8. A tömbelemek cseréjénél általában "puffer" (harmadik) változót használnak, ahová az egyik elem értéke ideiglenesen kerül.

Pascal program:

const m = 10; var arr: tömb [ 1 .. m ] of integer ; i, j, k: egész szám ; indítsa el a véletlenszerűsítést; ír( "Forrástömb: ") ; for i : = 1 to m do kezdődik arr[ i] : = véletlen(256 ); írás (arr[ i] : 4 ) ; vége ; írva ; írva ; for i : = 1-től m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] akkor kezdődik k : = arr[ j] ; arr[ j] := arr[ j+ 1 ] ; arr[ j+ 1 ] : = k vége ; ír ( "Rendezett tömb:") ; mert i := 1 - m nem ír (arr[ i] : 4 ); írva ; readln end .

Rendezzük el a tömböt felülről lefelé, a nulla elemtől az utolsóig.

A módszer ötlete: a rendezési lépés abból áll, hogy alulról felfelé haladunk a tömbön. A szomszédos elemek párjait végignézi az út során. Ha valamelyik pár elemei rossz sorrendben vannak, akkor felcseréljük őket.

Miután a nulla áthaladt a tömbön, a „legkönnyebb” elem „felül” van – innen ered az analógia a buborékkal. A következő lépés felülről a második elemig történik, így a második legnagyobb elemet a megfelelő pozícióba emeljük...

Addig haladunk a tömb egyre csökkenő alsó részén, amíg csak egy elem marad benne. Itt ér véget a rendezés, mivel a sorozat növekvő sorrendben történik.

Sablon void bubbleSort(T a, long size) ( long i, j; T x; for(i=0; i< size; i++) { // i - belépőszám for(j = méret-1; j > i; j--) ( // belső áteresztő hurok ha (a > a[j]) (x=a; a=a[j]; a[j]=x; ) ) )

Az összehasonlítások és cserék átlagos számának négyzetes növekedési sorrendje van: Theta(n 2), ebből arra következtethetünk, hogy a buborékalgoritmus nagyon lassú és nem hatékony.
Van azonban egy hatalmas előnye: egyszerű és bármilyen módon javítható. Mit fogunk most tenni.

Először is vegyük figyelembe azt a helyzetet, amikor egyik bérleten sem történt csere. Mit jelent?

Ez azt jelenti, hogy minden pár a megfelelő sorrendben van, tehát a tömb már rendezve van. És nincs értelme folytatni a folyamatot (főleg, ha a tömböt a kezdetektől rendezték!).

Tehát az algoritmus első fejlesztése az, hogy megjegyezzük, történt-e csere egy adott lépésen. Ha nem, az algoritmus leáll.

A javítási folyamat akkor folytatható, ha nemcsak magára a csere tényére emlékezünk, hanem az utolsó k csere indexére is. Valóban: minden k-nál kisebb indexű szomszédos elempár már a kívánt sorrendben van. A további lépések a k indexnél végződhetnek, ahelyett, hogy az előre beállított i felső korlátra lépnének felfelé.

A következő megfigyelésből az algoritmus minőségileg eltérő fejlesztése érhető el. Bár az alulról jövő könnyű buborék egy menetben a tetejére emelkedik, a nehéz buborékok iterációnként legalább egy lépéssel ereszkednek le. Tehát a 2 3 4 5 6 1 tömb 1 lépésben lesz rendezve, míg a 6 1 2 3 4 5 sorozat rendezéséhez 5 lépésre lesz szükség.

Ennek elkerülése érdekében megváltoztathatja az egymást követő lépések irányát. Az eredményül kapott algoritmust néha "" shaker-sort".

Sablon void shakerSort(T a, long size) ( long j, k = méret-1; long lb=1, ub = méret-1; // a tömb rendezetlen részének határai Tx; do( // alulról felfelé halad for(j=ub; j>0; j--) ( if (a > a[j]) (x=a; a=a[j]; a[j]=x; k=j; ) ) lb =k+1; // felülről lefelé halad for (j=1; j<=ub; j++) { if (a >a[j]) (x=a; a=a[j]; a[j]=x; k=j; ) ) ub = k-1; ) míg (lb< ub); }

Mennyiben befolyásolták a leírt változások a módszer hatékonyságát? Az összehasonlítások átlagos száma, bár csökkent, továbbra is O(n 2), míg a cserék száma mit sem változott. Az átlagos (egyben a legrosszabb) műveletek száma továbbra is négyzetes.

További memória nyilvánvalóan nem szükséges. A továbbfejlesztett (de nem kezdeti) metódus viselkedése teljesen természetes, egy majdnem rendezett tömb sokkal gyorsabban lesz rendezve, mint egy véletlenszerű. A buborékos rendezés stabil, de a rázós rendezés elveszti ezt a minőségét.

A gyakorlatban a buborékos módszer még fejlesztésekkel is sajnos túl lassú. Ezért szinte soha nem használják.