Skaičiuojama, kad iki ketvirtadalio centralizuotų kompiuterių laiko praleidžiama rūšiuojant duomenis. Taip yra todėl, kad iš anksto surūšiuotame masyve daug lengviau rasti reikšmę. Kitu atveju paieška yra panaši į adatos paiešką šieno kupetoje.

Yra programuotojų, kurie visą savo darbo laiką praleidžia studijuodami ir diegdami rūšiavimo algoritmus. Taip yra todėl, kad didžioji dauguma verslo programinės įrangos apima duomenų bazių valdymą. Žmonės nuolat ieško informacijos duomenų bazėse. Tai reiškia, kad paieškos algoritmai yra labai paklausūs.

Tačiau yra vienas „bet“. Paieškos algoritmai veikia daug greičiau su jau surūšiuotomis duomenų bazėmis. Šiuo atveju reikalinga tik linijinė paieška.

Kol kompiuteriai tam tikru momentu yra be vartotojų, rūšiavimo algoritmai ir toliau veikia duomenų bazėse. Paieškotojai vėl ateina, o duomenų bazė jau surūšiuojama pagal vieną ar kitą paieškos tikslą.

Šiame straipsnyje pateikiami standartinių rūšiavimo algoritmų įgyvendinimo pavyzdžiai.

Pasirinkimo rūšiavimas

Norėdami rūšiuoti masyvą didėjančia tvarka, kiekvienoje iteracijoje turite rasti didžiausią reikšmę turintį elementą. Su juo reikia pakeisti paskutinį elementą. Kitas didžiausią vertę turintis elementas yra antroje vietoje. Tai turėtų vykti tol, kol elementai pirmose masyvo vietose bus tinkama tvarka.

C++ kodas

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

Burbulų rūšiavimas

Burbulų rūšiavimas lygina gretimus elementus ir sukeičia vietomis, jei kitas elementas yra mažesnis nei ankstesnis. Reikia atlikti kelis duomenų perėjimus. Pirmojo praėjimo metu lyginami pirmieji du masyvo elementai. Jei jie nėra tvarkingi, jie sukeičiami ir tada lyginami kitos poros elementai. Esant tokioms pat sąlygoms, jie taip pat keičiasi vietomis. Taigi rūšiavimas vyksta kiekviename cikle, kol pasiekiama masyvo pabaiga.

C++ kodas

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

Įterpimo rūšiavimas

Įterpimo rūšiavimas padalija masyvą į dvi sritis: sutvarkytą ir netvarkingą. Iš pradžių visas masyvas yra netvarkingas regionas. Pirmuoju praėjimu pirmasis elementas iš netvarkingos srities pašalinamas ir įdedamas į teisingą vietą užsakytoje srityje.

Kiekviename pravažiavime sutvarkytos srities dydis padidėja 1, o netvarkingos srities dydis sumažėja 1.

Pagrindinė kilpa eina nuo 1 iki N-1. Atliekant j-ąją iteraciją, elementas [i] įterpiamas į teisingą vietą užsakytoje srityje. Tai atliekama perkeliant visus sutvarkytos srities elementus, kurie yra didesni nei [i] viena pozicija į dešinę. [i] įterpiamas į tarpą tarp tų elementų, kurie yra mažesni už [i] ir tų, kurie yra didesni už [i].

C++ kodas

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

Sujungti rūšiavimą

C++ kodas

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

Greitas rūšiavimas

„Quicksort“ naudoja „skaldyk ir valdyk“ algoritmą. Jis pradedamas dalijant pradinį masyvą į du regionus. Šios dalys yra pažymėto elemento, vadinamo atrama, kairėje ir dešinėje. Proceso pabaigoje vienoje dalyje bus elementai, mažesni už nuorodą, o kitoje dalyje bus elementai, didesni už nuorodą.

C++ kodas

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

Tai ne tik nelaikomas greičiausiu būdu, bet ir uždaro lėčiausių užsakymo būdų sąrašą. Tačiau tai taip pat turi savo privalumų. Taigi, burbulų rūšiavimas yra pats logiškiausias ir natūraliausias problemos sprendimas, jei reikia išdėstyti elementus tam tikra tvarka. Pavyzdžiui, paprastas žmogus jį naudos rankiniu būdu – tiesiog vadovaudamasis intuicija.

Iš kur kilo toks neįprastas vardas?

Metodo pavadinimas buvo išrastas pagal analogiją su oro burbuliukais vandenyje. Tai metafora. Kaip ir maži oro burbuliukai kyla į viršų – juk jų tankis yra didesnis nei bet kokio skysčio (šiuo atveju vandens), taip ir kiekvienas masyvo elementas, kuo mažesnės vertės, tuo palaipsniui didina savo vertę. kelią į skaičių sąrašo pradžią.

Algoritmo aprašymas

Burbulų rūšiavimas veikia taip:

• pirmasis praėjimas: skaičių masyvo elementai imami po du ir taip pat lyginami poromis. Jei kurioje nors poroje elementų pirmoji reikšmė yra didesnė už antrąją, programa juos sukeičia;
• todėl atsiduria masyvo pabaigoje. Nors visi kiti elementai lieka tokie, kokie buvo, chaotiška tvarka ir reikalauja tolesnio rūšiavimo;
• Štai kodėl reikalingas antrasis praėjimas: jis atliekamas pagal analogiją su ankstesniu (jau aprašytu) ir turi palyginimų skaičių - atėmus vieną;
• Trečioje ištraukoje yra vienu palyginimų mažiau nei antrojoje ir dviem mažiau nei pirmojoje. Ir taip toliau;
• Apibendrinkime, kad kiekvienas leidimas turi (bendras vertes masyve, konkretų skaičių) atėmus (praėjimo skaičius) palyginimus.

Dar trumpiau, būsimos programos algoritmą galima parašyti taip:

• skaičių masyvas tikrinamas tol, kol randami bet kurie du skaičiai, o antrasis iš jų turi būti didesnis už pirmąjį;
• Programa keičia masyvo elementus, kurie yra neteisingai išdėstyti vienas kito atžvilgiu.

Pseudokodas pagal aprašytą algoritmą

Paprasčiausias įgyvendinimas vyksta taip:

Procedūra Sortirovka_Puzirkom;

Pradėti

kilpa j iš pradinis_indeksas prieš konechii_index;

kilpa i iš pradinis_indeksas prieš konechii_index-1;

Jeigu massiv[i]>massiv

(pakeisti reikšmes);

Galas

Žinoma, čia paprastumas tik apsunkina situaciją: kuo paprastesnis algoritmas, tuo daugiau jame atsiranda visų trūkumų. Laiko sunaudojimas yra per didelis net ir mažam masyvui (čia veikia reliatyvumas: eiliniam žmogui laikas gali pasirodyti mažas, tačiau programuotojo versle svarbi kiekviena sekundė ar net milisekundė).

Reikėjo geresnio įgyvendinimo. Pavyzdžiui, atsižvelgiant į masyvo verčių apsikeitimą:

Procedūra Sortirovka_Puzirkom;

Pradėti

sortirovka = tiesa;

ciklas iki šiol sortirovka = tiesa;

sortirovka = klaidinga;

kilpa i iš pradinis_indeksas prieš konechii_index-1;

Jeigu massiv[i]>massiv(pirmasis elementas yra didesnis nei antrasis), tada:

(sukeisti elementai);

sortirovka = tiesa; (nurodė, kad mainai buvo atlikti).

Galas.

Metodo trūkumai

Pagrindinis trūkumas yra proceso trukmė. Kiek laiko užtrunka sukurti burbulą?

Vykdymo laikas skaičiuojamas iš masyve esančių skaičių kvadrato – jam proporcingas galutinis rezultatas.

Blogiausiu atveju masyvas bus perkeltas tiek pat kartų, kiek jame yra elementų atėmus vieną reikšmę. Taip atsitinka todėl, kad galiausiai lieka tik vienas elementas, su kuriuo nėra ką palyginti, o paskutinis ėjimas per masyvą tampa nenaudingu veiksmu.

Be to, paprastas mainų rūšiavimo metodas, kaip jis dar vadinamas, yra veiksmingas tik mažiems masyvams. Su jo pagalba nebus įmanoma apdoroti didelių duomenų kiekių: rezultatas bus arba klaidos, arba programos gedimas.

Privalumai

Burbulų rūšiavimą suprasti gana paprasta. Technikos universitetų studijų programose, studijuojant masyvo elementų eiliškumą, ji apžvelgiama pirmiausia. Metodas lengvai įgyvendinamas tiek Delphi programavimo kalba (D), tiek C/C++ (C/C plus plus), neįtikėtinai paprastas reikšmių išdėstymo teisinga tvarka algoritmas, o Bubble Sort idealiai tinka pradedantiesiems.

Algoritmas dėl savo trūkumų nenaudojamas užklasiniams tikslams.

Vizualus rūšiavimo principas

Pradinis masyvo vaizdas 8 22 4 74 44 37 1 7

1 žingsnis 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

2 žingsnis 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

3 veiksmas 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

4 veiksmas 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

5 veiksmas 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

6 veiksmas 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

7 veiksmas 1 4 7 8 22 37 44 74

Burbulų rūšiavimo Paskalyje pavyzdys

Pavyzdys:

const kol_mas=10;

var masyvas: sveikųjų skaičių masyvas;

a, b, k: sveikasis skaičius;

writeln("įvestis", kol_mas, "masyvo elementai");

for a:=1 į kol_mas do readln(masyvas[a]);

a:=1 į kol_mas-1 pradėkite

b:=a+1 į kol_mas pradėkite

jei massiv[a]>massiv[b] tada prasideda

k:=masyvas[a]; massiv[a]:=massiv[b]; masyvas[b]:=k;

galas;

writeln("po rūšiavimo");

for a:=1 į kol_mas do writeln(massiv[a]);

Burbulų rūšiavimo pavyzdys C kalba

#įtraukti

#įtraukti

int main (int argc, char* argv)

int masyvas = (36, 697, 73, 82, 68, 12, 183, 88),i, ff;

dėl (; ;)(

ff = 0;

jei (i = 7; i>0; i--)(

if (masyvas[i]< massiv) {

swap(masyvas[i],massiv);

if (ff == 0) pertrauka;

getch(); // ekrano delsa

Praktinė šių metodų nauda nėra tokia didelė, ir daugelis habros naudotojų visa tai patyrė dar pirmoje klasėje. Todėl straipsnis skirtas tiems, kurie ką tik susidomėjo algoritmų teorija ir žengia pirmuosius žingsnius šia kryptimi.

vaizdas: burbuliukai

Šiandien kalbėsime apie paprasčiausią mainų rūšiavimas.

Jei kam įdomu, pasakysiu, kad yra ir kitų užsiėmimų - atrankos rūšiavimas, įterpimo rūšiavimas, sujungti rūšiuoti, paskirstymo rūšiavimas, hibridinės rūšys Ir lygiagrečios rūšys. Beje, taip pat yra ezoteriniai rūšiavimai. Tai įvairūs netikri, iš esmės neįgyvendinami, komiški ir kitokie pseudoalgoritmai, apie kuriuos „IT Humor“ centre parašysiu porą straipsnių.

Bet tai neturi nieko bendra su šios dienos paskaita; dabar mus domina tik paprastas mainų rūšiavimas. Taip pat yra nemažai ir pačių mainų rūšiavimo (žinau ne vieną dešimtį), tad pažiūrėsime į vadinamuosius. burbulų rūšiavimas ir kai kurie kiti glaudžiai su juo susiję.

Iš anksto įspėsiu, kad beveik visi aukščiau išvardinti metodai yra labai lėti ir nebus išsamios jų laiko sudėtingumo analizės. Vieni greitesni, kiti lėtesni, bet grubiai tariant, galima sakyti, kad vidutiniškai O(n 2). Be to, nematau jokios priežasties perkrauti straipsnį įgyvendinimais kokiomis nors programavimo kalbomis. Besidomintieji gali nesunkiai rasti kodų pavyzdžių Rosetta, Vikipedijoje ar kitur.

Bet grįžkime prie mainų rūšiavimo. Tvarka atsiranda dėl pakartotinės nuoseklios masyvo paieškos ir elementų porų palyginimo tarpusavyje. Jei lyginami elementai nėra surūšiuoti vienas kito atžvilgiu, mes juos sukeičiame. Vienintelis klausimas, kaip tiksliai apeiti masyvą ir kokiu pagrindu pasirinkti poras palyginimui.

Pradėkime ne nuo standartinio burbulų rūšiavimo, o nuo algoritmo, vadinamo...

Kvaila rūšis

„Bet koks kvailys gali taip rūšiuoti“, - pasakysite ir būsite visiškai teisus. Štai kodėl rūšiavimas vadinamas „kvaila“. Šioje paskaitoje šį metodą nuosekliai tobulinsime ir modifikuosime. Dabar jis turi laikinų sunkumų O(n 3), atlikę vieną pataisymą, jau atnešime į O(n 2), tada dar šiek tiek paspartinsime, tada dar šiek tiek ir galų gale gausime O(nžurnalas n) – ir tai visai nebus „Greitasis rūšiavimas“!

Patobulinkime kvailą rūšiavimą. Perėjimo metu atradę du gretimus nerūšiuotus elementus ir juos sukeitę, nebegrįšime į masyvo pradžią, o ramiai tęsime ją iki pat pabaigos.

Šiuo atveju mes neturime nieko daugiau, kaip gerai žinomą...

Burbulų rūšiavimas

Jei ne tik maksimumus nustumsime iki galo, bet ir minimumus nustumsime į pradžią, tada mums pavyksta...

Shaker rūšiavimas

Rūšiavimas su purtikliu veikia šiek tiek greičiau nei burbulų rūšiavimas, nes tiek maksimumai, tiek minimumai pakaitomis migruoja per masyvą reikiamomis kryptimis. Patobulinimai, kaip sakoma, akivaizdūs.

Kaip matote, jei į surašymo procesą žiūrite kūrybiškai, tada sunkiųjų (lengvų) elementų išstūmimas į masyvo galus vyksta greičiau. Todėl meistrai sąrašui apeiti pasiūlė dar vieną nestandartinį „kelių žemėlapį“.

Lyginis-nelyginis rūšiavimas

Įprastame „burbule“ kiekvieno praėjimo metu sistemingai išspaudžiame esamą maksimumą iki masyvo pabaigos. Jei šokinėjate išilgai lyginių ir nelyginių indeksų, tada visi daugiau ar mažiau dideli masyvo elementai vienu metu vienu metu nustumiami į dešinę vieną poziciją. Taip veikia greičiau.

Pažiūrėkime į paskutinį iš naujo dekoruotas* Dėl Sortuvannya bulbashka** - Rūšiavimas šukomis***. Šis metodas organizuojamas labai greitai, O(n 2) yra didžiausias jo sunkumas. Vidutiniškai per laiką turime O(nžurnalas n), o geriausia, net nepatikėsite, O(n). Tai yra, labai vertas konkurentas visoms „greitoms rūšims“, ir tai, atkreipkite dėmesį, nenaudojant rekursijos. Tačiau pažadėjau, kad šiandien nesigilinsime į kreiserinius greičius, todėl nustosiu kalbėti ir eisiu tiesiai prie algoritmo.

Dėl visko kalti vėžliai

vaizdas: kaltas vėžlys

Šukų rūšiavimas

Geriau imti pradinį atotrūkį tarp lyginamų elementų ne bet kokį, o atsižvelgiant į specialią reikšmę, vadinamą redukcinis veiksnys, kurio optimali reikšmė yra maždaug 1,247. Pirma, atstumas tarp elementų yra lygus masyvo dydžiui, padalintam iš mažinimo koeficientas(rezultatas, žinoma, suapvalinamas iki artimiausio sveikojo skaičiaus). Tada, perėję masyvą šiuo žingsniu, mes vėl padalijame žingsnį iš mažinimo koeficientas ir dar kartą peržiūrėkite sąrašą. Tai tęsiasi tol, kol indekso skirtumas pasiekia vieną. Šiuo atveju masyvas rūšiuojamas įprastu burbulu.

Optimali vertė buvo nustatyta eksperimentiškai ir teoriškai mažinimo koeficientas:

Kai šis metodas buvo išrastas, 70-80-ųjų sandūroje mažai kas į jį atkreipė dėmesį. Praėjus dešimtmečiui, kai programavimas jau nebuvo IBM mokslininkų ir inžinierių sritis, o jau sparčiai populiarėjo masiškai, metodą 1991 metais iš naujo atrado, ištyrė ir išpopuliarino Stephenas Lacy ir Richardas Boxas.

Tai iš tikrųjų viskas, ką norėjau pasakyti apie burbulų rūšiavimą ir kitus panašius dalykus.

- Pastabos

* sutrumpintas ( ukrainiečių) – tobulinimas
** Rūšiuota pagal lemputę ( ukrainiečių) – burbulinis rūšiavimas
*** Rūšiavimas pagal šukas ( ukrainiečių) – Šukų rūšiavimas

Dirbant su duomenų masyvais dažnai iškyla užduotis rūšiavimas didėjančia arba mažėjančia tvarka, t.y. užsakymas. Tai reiškia, kad to paties masyvo elementai turi būti išdėstyti griežtai eilės tvarka. Pavyzdžiui, rūšiavimo didėjančia tvarka atveju ankstesnis elementas turi būti mažesnis (arba lygus) paskesniam elementui.

Sprendimas

Yra daug rūšiavimo būdų. Kai kurie iš jų yra efektyvesni, kiti lengviau suprantami. Rūšiuoti gana lengva suprasti burbulo metodas, kuris taip pat vadinamas paprastas keitimo būdas. Kas tai yra ir kodėl jis turi tokį keistą pavadinimą: „burbulo metodas“?

Kaip žinote, oras yra lengvesnis už vandenį, todėl oro burbuliukai plūduriuoja. Tai tik analogija. Didėjančio burbulo rūšiavimo metu lengvesni (mažesnės vertės) elementai palaipsniui „plaukia“ į masyvo pradžią, o sunkesni vienas po kito krenta į apačią (iki masyvo galo).

Šio rūšiavimo algoritmas ir funkcijos yra tokie:

1. Pirmojo praėjimo per masyvą metu elementai lyginami vienas su kitu poromis: pirmasis su antruoju, antrasis su trečiuoju, trečiasis su ketvirtuoju ir t.t. Jei ankstesnis elementas yra didesnis nei paskesnis, tada jie pakeičiami.
2. Nesunku atspėti, kad palaipsniui didžiausias skaičius tampa paskutinis. Likusi masyvo dalis lieka nerūšiuota, nors mažesnės vertės elementai šiek tiek juda į masyvo pradžią.
3. Antruoju praėjimu nereikia lyginti paskutinio elemento su priešpaskutiniu. Paskutinis elementas jau yra vietoje. Tai reiškia, kad palyginimų bus vienu mažiau.
4. Trečiajame važiavime nebereikia lyginti priešpaskutinio ir trečiojo elemento nuo galo. Todėl palyginimų bus dviem mažiau nei per pirmąjį pravažiavimą.
5. Juk kartojant per masyvą, kai belieka palyginti du elementus, atliekamas tik vienas palyginimas.
6. Po to nėra su kuo lyginti pirmojo elemento, todėl galutinis perėjimas per masyvą yra nereikalingas. Kitaip tariant, perėjimų per masyvą skaičius yra m-1, kur m yra masyvo elementų skaičius.
7. Palyginimų skaičius kiekviename žingsnyje yra lygus m-i, kur i yra perėjimų per masyvą skaičius (pirmas, antras, trečias ir tt).
8. Keičiant masyvo elementus dažniausiai naudojamas „buferinis“ (trečiasis) kintamasis, kuriame laikinai įdedama vieno iš elementų reikšmė.

Pascal programa:

const m = 10; var arr: masyvas [ 1 .. m ] sveikasis skaičius ; i, j, k: sveikasis skaičius ; pradėti randomizuoti; rašyti ( „Šaltinio masyvas:“) ; for i : = 1 to m do start arr[ i] : = atsitiktinis(256 ); rašyti (arr[ i] : 4 ) ; galas ; parašyta ; parašyta ; jei i : = nuo 1 iki m- 1 daryti j : = 1 iki m- i daryti, jei arr[ j] > arr[ j+ 1 ] tada prasideda k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k galas ; rašyti ( "Rūšiuotas masyvas:") ; i : = 1 iki m rašyti (arr[ i] : 4 ); parašyta ; skaitymo pabaiga.

Išdėskime masyvą iš viršaus į apačią, nuo nulinio elemento iki paskutinio.

Metodo idėja: rūšiavimo žingsnis susideda iš masyvo perėjimo iš apačios į viršų. Pakeliui apžiūrimos gretimų elementų poros. Jei tam tikros poros elementai yra neteisinga tvarka, mes juos sukeičiame.

Po to, kai per masyvą praeina nulis, viršuje pasirodo šviesiausias elementas – taigi analogija su burbulu. Kitas praėjimas atliekamas ant antrojo elemento iš viršaus, taip pakeliant antrą pagal dydį elementą į teisingą padėtį...

Mes darome praėjimus išilgai vis mažėjančios apatinės masyvo dalies, kol joje lieka tik vienas elementas. Čia rūšiavimas baigiasi, nes seka išdėstyta didėjančia tvarka.

Šablonas void bubbleSort(T a, ilgas dydis) (ilgas i, j; T x; for(i=0; i< size; i++) { // i - leidimo numeris for(j = dydis-1; j > i; j--) ( // vidinė kilpa jei (a > a[j]) (x=a; a=a[j]; a[j]=x; ) ) )

Vidutinis palyginimų ir mainų skaičius turi kvadratinę augimo tvarką: Theta(n 2), iš kurios galime daryti išvadą, kad burbulo algoritmas yra labai lėtas ir neefektyvus.
Tačiau jis turi didžiulį pranašumą: yra paprastas ir gali būti visokeriopai tobulinamas. Ką mes dabar darysime?

Pirma, panagrinėkime situaciją, kai keitimai neįvyko nė viename perdavime. Ką tai reiškia?

Tai reiškia, kad visos poros yra teisinga tvarka, taigi masyvas jau surūšiuotas. Ir nėra prasmės tęsti proceso (ypač jei masyvas buvo rūšiuojamas nuo pat pradžių!).

Taigi, pirmasis algoritmo patobulinimas yra prisiminti, ar buvo atliktas keitimas tam tikru leidimu. Jei ne, algoritmas nutrūksta.

Tobulinimo procesą galima tęsti, jei prisiminsite ne tik patį keitimo faktą, bet ir paskutinio keitimo indeksą k. Iš tiesų: visos gretimų elementų poros, kurių indeksai mažesni nei k, jau yra išdėstyti reikiama tvarka. Tolesni važiavimai gali baigtis indeksu k, o ne pereiti prie iš anksto nustatytos viršutinės ribos i.

Kokybiškai skirtingą algoritmo patobulinimą galima gauti iš toliau pateikto stebėjimo. Nors apačioje esantis lengvas burbulas pakils į viršų per vieną praėjimą, sunkūs burbuliukai nuslūgs minimaliu greičiu: vienu žingsniu per iteraciją. Taigi masyvas 2 3 4 5 6 1 bus surūšiuotas vienu žingsniu, tačiau norint surūšiuoti seką 6 1 2 3 4 5 reikės 5 eilių.

Norėdami išvengti šio efekto, galite pakeisti nuoseklių ėjimų kryptį. Gautas algoritmas kartais vadinamas " kratytuvo rūšiavimas".

Šablonas void shakerSort(T a, long size) (ilgas j, k = dydis-1; long lb=1, ub = dydis-1; // nerūšiuotos masyvo dalies ribos Tx; daryti ( // pereiti iš apačios į viršų for(j=ub; j>0; j--) (jei (a > a[j]) (x=a; a=a[j]; a[j]=x; k=j; ) ) lb = k+1; // pereiti iš viršaus į apačią už (j = 1; j<=ub; j++) { if (a >a[j]) (x=a; a=a[j]; a[j]=x; k=j; ) ) ub = k-1; ) o (lb< ub); }

Kiek aprašyti pokyčiai paveikė metodo efektyvumą? Vidutinis palyginimų skaičius, nors ir sumažėjo, išlieka O(n 2), o mainų skaičius visiškai nepasikeitė. Vidutinis (dar žinomas kaip blogiausias) operacijų skaičius išlieka kvadratinis.

Akivaizdu, kad papildomos atminties nereikia. Patobulinto (bet ne pradinio) metodo veikimas yra gana natūralus, beveik surūšiuotas masyvas bus surūšiuotas daug greičiau nei atsitiktinis. Rūšiavimas burbulais yra stabilus, tačiau rūšiuojant kratytuvu ši kokybė prarandama.

Praktiškai burbulo metodas, net ir patobulinus, veikia, deja, per lėtai. Ir todėl jis beveik niekada nenaudojamas.