Razvrstavanje mjehurića si. Metode sortiranja u programiranju: bubble sort. Odakle tako neobično ime?
Procjenjuje se da se do četvrtine vremena centraliziranih računala troši na sortiranje podataka. To je zato što je puno lakše pronaći vrijednost u nizu koji je unaprijed sortiran. Inače, potraga je poput traženja igle u plastu sijena.
Postoje programeri koji cijelo svoje radno vrijeme provode proučavajući i implementirajući algoritme sortiranja. To je zato što velika većina poslovnog softvera uključuje upravljanje bazom podataka. Ljudi cijelo vrijeme traže informacije u bazama podataka. To znači da su algoritmi pretraživanja vrlo traženi.
Ali postoji jedan "ali". Algoritmi pretraživanja rade mnogo brže s bazama podataka koje su već sortirane. U ovom slučaju potrebno je samo linearno pretraživanje.
Dok su računala u nekim trenucima bez korisnika, algoritmi za sortiranje nastavljaju raditi na bazama podataka. Tražitelji ponovno dolaze, a baza podataka već je sortirana prema jednoj ili drugoj svrsi pretraživanja.
Ovaj članak pruža primjere implementacija standardnih algoritama sortiranja.
Odabir vrste
Za sortiranje niza uzlaznim redoslijedom, morate pronaći element s najvećom vrijednošću u svakoj iteraciji. S njim morate zamijeniti posljednji element. Sljedeći element s najvećom vrijednošću postavlja se na pretposljednje mjesto. To bi se trebalo događati sve dok elementi na prvim mjestima u nizu ne budu u ispravnom redoslijedu.
C++ kod
void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
Razvrstavanje mjehurića
Bubble sortiranje uspoređuje susjedne elemente i mijenja mjesta ako je sljedeći element manji od prethodnog. Potrebno je više prolaza kroz podatke. Tijekom prvog prolaza uspoređuju se prva dva elementa u nizu. Ako nisu u redu, zamjenjuju se i uspoređuju elementi u sljedećem paru. Pod istim uvjetom mijenjaju i mjesta. Dakle, sortiranje se događa u svakom ciklusu dok se ne dosegne kraj niza.
C++ kod
void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i Sortiranje umetanjem dijeli niz u dvije regije: uređenu i neuređenu. U početku, cijeli niz je neuređena regija. Prilikom prvog prolaza, prvi element iz neuređenog područja uklanja se i postavlja na ispravan položaj u uređenom području. Prilikom svakog prolaza, veličina uređene regije povećava se za 1, a veličina neuređene regije smanjuje se za 1. Glavna petlja ide od 1 do N-1. U j-toj iteraciji, element [i] je umetnut na ispravnu poziciju u uređenom području. To se postiže pomicanjem svih elemenata uređene regije koji su veći od [i] za jedno mjesto udesno. [i] se umeće u razmak između onih elemenata koji su manji od [i] i onih koji su veći od [i]. C++ kod
void SortAlgo::insertionSort(int podaci, int lenD) ( int ključ = 0; int i = 0; for (int j = 1;j C++ kod
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i Quicksort koristi algoritam podijeli pa vladaj. Započinje dijeljenjem izvornog niza u dvije regije. Ovi dijelovi su lijevo i desno od označenog elementa, koji se naziva oslonac. Na kraju procesa jedan dio će sadržavati elemente manje od reference, a drugi dio elemente veće od reference. C++ kod
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 = novi int ; int * R = novi int ; pivot = podaci; za (i=0;i Praktične koristi od ovih metoda nisu tako velike, a mnogi korisnici habre sve su to prošli u prvom razredu. Stoga je članak namijenjen onima koji su se tek zainteresirali za teoriju algoritama i poduzimaju prve korake u tom smjeru. slika: mjehurići Danas ćemo govoriti o najjednostavnijem razmjena razvrstavanja. Ako nekoga zanima, reći ću da postoje i druge klase - odabir vrste, sortiranje umetanjem, sortiranje spajanjem, distribucijsko sortiranje, hibridne sorte I paralelne vrste. Usput, također postoji ezoterijska sortiranja. To su razni lažni, fundamentalno neostvarivi, komični i drugi pseudoalgoritmi, o kojima ću napisati nekoliko članaka u čvorištu “IT Humor”. Ali to nema nikakve veze s današnjim predavanjem; sada nas zanimaju samo jednostavna sortiranja razmjene. Ima i dosta samih sortiranja mjenjačnica (znam više od desetak), pa ćemo se osvrnuti na tzv. sortiranje mjehurića i neki drugi s njim usko povezani. Unaprijed ću vas upozoriti da su gotovo sve gore navedene metode vrlo spore i neće biti dublje analize njihove vremenske zahtjevnosti. Neki su brži, neki sporiji, ali ugrubo govoreći, to možemo reći u prosjeku O(n 2). Također, ne vidim razloga za zatrpavanje članka implementacijama u bilo kojem programskom jeziku. Zainteresirani mogu lako pronaći primjere koda na Rosetti, Wikipediji ili drugdje. No, vratimo se sortiranju razmjena. Redoslijed se javlja kao rezultat ponovljenog sekvencijalnog pretraživanja niza i usporedbe parova elemenata međusobno. Ako elementi koji se uspoređuju nisu poredani jedan u odnosu na drugi, tada ih mijenjamo. Pitanje je samo kako točno zaobići niz i na temelju čega odabrati parove za usporedbu. Počnimo ne sa standardnim sortiranjem mjehurića, već s algoritmom koji se zove... “Svaka budala može tako sortirati”, reći ćete i bit ćete potpuno u pravu. Zbog toga se sortiranje naziva "glupim". U ovom predavanju dosljedno ćemo poboljšavati i modificirati ovu metodu. Sada ima privremenih poteškoća O(n 3), izvršivši jednu ispravku, već ćemo je dovesti do O(n 2), pa ćemo još malo ubrzati, pa još malo i na kraju ćemo dobiti O(n log n) – i to uopće neće biti “Brzo sortiranje”! Napravimo jedno jedino poboljšanje glupog sortiranja. Nakon što smo tijekom prolaza otkrili dva susjedna nerazvrstana elementa i zamijenili ih, nećemo se vratiti na početak niza, već ćemo ga mirno nastaviti obilaziti do samog kraja. U ovom slučaju pred sobom nemamo ništa više od dobro poznatog... Ako ne guramo samo maksimume do kraja, nego i minimume guramo do početka, onda uspijevamo... Shaker razvrstavanje radi malo brže od razvrstavanja s mjehurićima, jer i maksimumi i minimumi naizmjence migriraju nizom u traženim smjerovima. Poboljšanja su, kako kažu, očita. Kao što možete vidjeti, ako procesu nabrajanja pristupite kreativno, izbacivanje teških (laganih) elemenata na krajeve niza događa se brže. Stoga su obrtnici predložili još jednu nestandardnu "mapu puta" kako bi zaobišli popis. U redovnom "mjehuriću", tijekom svakog prolaza sustavno istiskujemo trenutni maksimum do kraja niza. Ako skačete duž parnih i neparnih indeksa, tada se svi više ili manje veliki elementi niza istovremeno guraju na jednu poziciju udesno u jednom trčanju. Ovako radi brže. Pogledajmo posljednju preuređen* Za Sortuvannya bulbashka** - Razvrstavanje po češlju***. Ova metoda organizira vrlo brzo, O(n 2) je njegova najveća poteškoća. U prosjeku s vremenom imamo O(n log n), a najbolji, nećete ni vjerovati, O(n). Odnosno, vrlo vrijedan konkurent svim vrstama "brzih sortiranja" i to, imajte na umu, bez upotrebe rekurzije. Međutim, obećao sam da danas nećemo ulaziti u brzine krstarenja, pa ću prestati govoriti i prijeći izravno na algoritam. slika: kriva kornjača Bolje je uzeti početni jaz između uspoređivanih elemenata ne bilo koji, već uzimajući u obzir posebnu vrijednost tzv redukcijski faktor, čija je optimalna vrijednost približno 1,247. Prvo, udaljenost između elemenata jednaka je veličini niza podijeljenoj s redukcijski faktor(rezultat se, naravno, zaokružuje na najbliži cijeli broj). Zatim, nakon prelaska niza s ovim korakom, ponovno dijelimo korak s redukcijski faktor i ponovno prođite kroz popis. To se nastavlja sve dok razlika indeksa ne dosegne jedinicu. U ovom slučaju, niz je sortiran običnim oblačićem. Optimalna vrijednost utvrđena je eksperimentalno i teorijski redukcijski faktor: Kada je ova metoda izmišljena, na prijelazu iz 70-ih u 80-e malo je ljudi obraćalo pažnju na nju. Desetljeće kasnije, kada programiranje više nije bilo područje IBM-ovih znanstvenika i inženjera, već je već brzo dobivalo masovnu popularnost, metodu su 1991. ponovno otkrili, istražili i popularizirali Stephen Lacy i Richard Box. To je zapravo sve što sam vam htio reći o sortiranju mjehurića i ostalima poput njega. - Bilješke * skraćeno ( ukrajinski) - poboljšanje Bok svima! Danas ćemo pogledati sortiranje mjehurića. Ovaj algoritam se često uči u školama i na sveučilištima, pa ćemo koristiti Pascal. Dakle, što je sortiranje? Sortiranje je poredak elemenata od najmanjeg prema najvećem (uzlazno sortiranje) ili od najvećeg elementa prema najmanjem (opadajuće sortiranje). Nizovi su obično sortirani. Postoje različiti algoritmi sortiranja. Neki su dobri u sortiranju velikog broja elemenata, drugi su učinkovitiji s vrlo malim brojem elemenata. Našu metodu mjehurića karakterizira: Algoritam:
Uzimamo element niza, uspoređujemo ga sa sljedećim, ako je naš element veći od sljedećeg elementa, mijenjamo ih. Nakon što prođemo kroz cijeli niz, možemo biti sigurni da će maksimalni element biti "izbačen" - i da će biti posljednji. Dakle, jedan element je već točno na svom mjestu. Jer moramo ih sve staviti na njihova mjesta, stoga ovu operaciju moramo ponoviti onoliko puta koliko imamo elemenata niza minus 1. Zadnji element će automatski stajati ako su ostali na svojim mjestima.
Vratimo se našem nizu: 3 1 4 2 Sada preostaje samo programirati ovaj algoritam u Pascalu. const n = 4; (Postavili smo konstantu, to će biti duljina niza) var i, j, k:integer; (Dvije varijable za ugniježđenu petlju, jedna za zamjenu elemenata) m: niz cijelih brojeva; (Stvaramo niz) begin (Zatražit ćemo niz s tipkovnice:) Writeln("Unesite niz:"); for i:=1 to n do begin Writeln(i, " element:"); Readln(m[i]); kraj; (Vanjska petlja je odgovorna za činjenicu da moramo ponoviti unutarnju petlju onoliko puta koliko imamo elemenata niza minus 1.) za i:=1 do n-1 počinje (unutarnja petlja već ponavlja kroz elemente i uspoređuje međusobno.) za j :=1 do n-i do start (Ako je element veći od sljedećeg, tada zamijeni mjesta.) if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; kraj; kraj; kraj; (Ispiši rezultat:) for i:=1 to n do Write(m[i], " "); kraj. Oznake: Bubble sort C, Bubble sort, Bubble sort dvodimenzionalnog niza A ideja algoritma je vrlo jednostavna. Prolazimo kroz niz brojeva i provjeravamo redoslijed (sljedeći broj mora biti veći i jednak prethodnom), čim naiđemo na kršenje redoslijeda, odmah mijenjamo elemente, dolazimo do kraja niz, a zatim počnite ispočetka. Poredaj niz (1, 5, 2, 7, 6, 3) 1, 2, 5, 3, 6, 7 Kažu da je to slično "lebdenju" "lakših" elemenata, poput mjehurića, po čemu je algoritam i dobio ime. void bubbleSort(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) {
for (j = 1; j < size; j++) {
if (a[j] >a) (tmp = a[j]; a[j] = a; a = tmp; ) ) ) ) Ovaj algoritam će uvijek poduzeti (n-1) 2 koraka, bez obzira na ulazne podatke. Čak i ako je niz sortiran, svejedno će se prijeći (n-1) 2 puta. Štoviše, već sortirani podaci bit će ponovno provjereni. Recimo da trebamo sortirati niz 1, 2, 4, 3 1 2 4 3 Nakon što su elementi a i a zamijenjeni, više nema potrebe prelaziti ovaj dio niza. Uzmimo to u obzir i preradimo algoritam Void bubbleSort2(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) {
for (j = i; j >0; j--) ( if (a[j]< a) {
tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Još jedna implementacija Void bubbleSort2b(int *a, size_t size) ( size_t i, j; int tmp; for (i = 1; i< size; i++) {
for (j = 1; j <= size-i; j++) {
if (a[j] < a) {
tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
U ovom slučaju bit će upola manje koraka, ali problem sortiranja već sortiranog niza i dalje ostaje: morate osigurati da funkcija jednom pregleda sortirani niz. Da bismo to učinili, uvodimo varijablu zastavice: ona će biti izostavljena (zastavica = 0) ako je niz sortiran. Čim naiđemo na kršenje reda, zastavica će biti podignuta (zastavica = 1) i počet ćemo sortirati niz kao i obično. Void bubbleSort3(int *a, size_t size) ( size_t i; int tmp; char zastavica; do ( zastavica = 0; for (i = 1; i)< size; i++) {
if (a[i] < a) {
tmp = a[i];
a[i] = a;
a = tmp;
flag = 1;
}
}
} while (flag);
}
U ovom slučaju, složenost je također reda veličine n 2 , ali u slučaju sortiranog niza bit će samo jedan prolaz. Sada poboljšajmo algoritam. Napišimo opću funkciju za sortiranje niza tipa void. Budući da tip varijable nije poznat, morat ćete dodatno proslijediti veličinu jednog elementa polja i funkciju usporedbe. Int intSort(const void *a, const void *b) ( return *((int*)a) > *((int*)b); ) void bubbleSort3g(void *a, size_t item, size_t size, int (* cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; char zastavica; tmp = malloc(item); do ( zastavica = 0; for (i = 1; i< size; i++) {
if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
memcpy(tmp, ((char*)a + i*item), item);
memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
memcpy(((char*)a + (i-1)*item), tmp, item);
flag = 1;
}
}
} while (flag);
free(tmp);
}
Funkcija izgleda ružno - često se računa adresa trenutnog i prethodnog elementa. Istaknimo zasebne varijable za ovo. Void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(stavka); do ( zastavica = 0; i = 1; prev = (char*)a; cur = (char*)prev + item; while (i< size) {
if (cmp(cur, prev)) {
memcpy(tmp, prev, item);
memcpy(prev, cur, item);
memcpy(cur, tmp, item);
flag = 1;
}
i++;
prev = (char*)prev + item;
cur = (char*)cur + item;
}
} while (flag);
free(tmp);
}
Sada pomoću ovih funkcija možete sortirati nizove bilo koje vrste, na primjer Void main() ( int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i = 0;i< 10; i++) {
printf("%d ", a[i]);
}
_getch();
}
Sortiranje statičkog višedimenzionalnog niza u biti se ne razlikuje od sortiranja jednodimenzionalnog. Možete iskoristiti činjenicu da statični jednodimenzionalni i višedimenzionalni nizovi imaju istu zastupljenost u memoriji. Void main() ( int a = (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi(a, sizeof(int), 9, intSort); for (i = 0;i< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include Drugo, prvo možete premjestiti niz u jednodimenzionalni, sortirati jednodimenzionalni niz, a zatim ga premjestiti natrag u dvodimenzionalni. Void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) ( size_t size = m*n, sub_size = n*item; size_t i, j , k; void *arr = malloc(size * item); char *p1d = (char*)arr; char *p2d = (char*)a; //Kopiraj dvodimenzionalni niz tipa void u jednodimenzionalni za (i = 0; i< m; i++) {
memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size);
}
bubbleSort3gi(arr, item, size, cmp);
//Копируем одномерный массив обратно в двумерный
for (i = 0; i < m; i++) {
memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size);
}
}
Ako vas zbunjuje ova funkcija, upotrijebite onu upisanu. Call, iz prethodnog primjera Ne samo da se ne smatra najbržom metodom, štoviše, zatvara popis najsporijih metoda naručivanja. Međutim, ima i svojih prednosti. Dakle, razvrstavanje u obliku mjehurića je najlogičnije i najprirodnije rješenje problema ako trebate posložiti elemente određenim redoslijedom. Obična osoba, na primjer, koristit će ga ručno - jednostavno intuicijom. Naziv metode je izmišljen pomoću analogije s mjehurićima zraka u vodi. Ovo je metafora. Baš kao što se mali mjehurići zraka dižu prema vrhu - uostalom, njihova je gustoća veća od gustoće bilo koje tekućine (u ovom slučaju vode), tako svaki element niza, što je manje vrijednosti, to postupno čini svoj put do početka popisa brojeva. Sortiranje mjehurićima funkcionira ovako: Još kraće, algoritam budućeg programa može se napisati na sljedeći način: Najjednostavnija implementacija ide ovako: Postupak Sortirovka_Puzirkom;
Početak
petlja za j iz početni_indeks prije konechii_index;
petlja za ja iz početni_indeks prije konechii_index-1;
Ako masiv[i]>masiv (zamijenite vrijednosti); Kraj
Naravno, ovdje jednostavnost samo pogoršava situaciju: što je algoritam jednostavniji, to se u njemu više pojavljuju svi nedostaci. Utrošak vremena je prevelik čak i za mali niz (ovdje dolazi do izražaja relativnost: za prosječnog čovjeka količina vremena može se činiti malom, ali u poslu programera svaka sekunda ili čak milisekunda je važna). Bila je potrebna bolja implementacija. Na primjer, uzimajući u obzir zamjenu vrijednosti u nizu: Postupak Sortirovka_Puzirkom;
Početak
sortirovka
= istina; ciklus do sada sortirovka
= istina;
sortirovka
= lažno;
petlja za ja iz početni_indeks prije konechii_index-1;
Ako masiv[i]>masiv(prvi element je veći od drugog), tada: (zamjena elemenata); sortirovka
= istina; (označeno da je zamjena izvršena).
Kraj.
Glavni nedostatak je trajanje procesa. Koliko vremena je potrebno da se napravi mjehurić? Vrijeme izvršenja izračunava se iz kvadrata broja brojeva u nizu - konačni rezultat je proporcionalan tome. U najgorem slučaju, polje će se obići onoliko puta koliko ima elemenata u njemu minus jedna vrijednost. To se događa jer na kraju ostaje samo jedan element bez ičega za usporedbu, a posljednji prolaz kroz niz postaje beskorisna radnja. Osim toga, jednostavna metoda sortiranja razmjenom, kako se još naziva, učinkovita je samo za male nizove. Uz njegovu pomoć neće biti moguće obraditi velike količine podataka: rezultat će biti pogreške ili kvar programa. Bubble sortiranje prilično je jednostavno za razumjeti. U nastavnim planovima i programima tehničkih sveučilišta, kada se proučava poredak elemenata niza, on se prvo obrađuje. Metoda se lako implementira iu programskom jeziku Delphi (D) i u C/C++ (C/C plus plus), nevjerojatno jednostavan algoritam za slaganje vrijednosti ispravnim redoslijedom, a Bubble Sort je idealan za početnike. Zbog svojih nedostataka algoritam se ne koristi u izvannastavne svrhe. Početni prikaz niza 8 22 4 74 44 37 1 7 Korak 1 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 Korak 2 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. korak 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 Korak 4 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 Korak 5 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Korak 6 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Korak 7 1 4 7 8 22 37 44 74 Primjer: const kol_mas=10; var niz: niz cijelih brojeva; a, b, k: cijeli broj; writeln("ulaz", kol_mas, "elementi niza"); for a:=1 to kol_mas do readln(array[a]); za a:=1 do kol_mas-1 početi za b:=a+1 do kol_mas do početka ako masiv[a]>masiv[b] onda počni k:=niz[a]; masiv[a]:=masiv[b]; niz[b]:=k; kraj; writeln("nakon sortiranja"); for a:=1 to kol_mas do writeln(masiv[a]); #uključi #uključi int main(int argc, char* argv) int masiv = (36, 697, 73, 82, 68, 12, 183, 88),i, ff; za (; ;)( ff = 0; za (i = 7; i>0; i--)( if (niz[i]< massiv) {
zamijeni(niz[i],masiv); if (ff == 0) break; dobiti(); // odgoda zaslonaSortiranje umetanjem
Sortiranje spajanjem
Brzo sortiranje
Svi jako dobro znaju da je iz klase sortiranja razmjene najbrža metoda tzv brzo sortiranje. O tome su napisane disertacije, posvećeni su mu mnogi članci na Habréu, a na temelju njega izmišljeni su složeni hibridni algoritmi. Ali danas nećemo o tome brzo sortiranje, i o još jednom načinu razmjene - dobrom starom sortiranje mjehurića i njegova poboljšanja, modifikacije, mutacije i varijacije. Glupa vrsta
Razvrstavanje je stvarno glupo. Gledamo niz s lijeva na desno i uspoređujemo susjede. Ako naiđemo na par međusobno nerazvrstanih elemenata, mijenjamo ih i vraćamo se na početak, odnosno na sam početak. Prolazimo i ponovno provjeravamo niz, ako ponovno naiđemo na "neispravan" par susjednih elemenata, tada mijenjamo mjesta i počinjemo ispočetka. Nastavljamo dok se niz malo po malo ne sortira. Razvrstavanje mjehurića
Ili sortiranje jednostavnim razmjenama. Besmrtni klasik žanra. Princip rada je jednostavan: prelazimo niz od početka do kraja, istovremeno mijenjajući nesortirane susjedne elemente. Kao rezultat prvog prolaza, maksimalni element će "isplivati" na posljednje mjesto. Sada ponovno prelazimo nesortirani dio niza (od prvog elementa do pretposljednjeg) i usput mijenjamo nesortirane susjede. Drugi najveći element bit će na pretposljednjem mjestu. Nastavljajući u istom duhu, proći ćemo kroz sve manji nerazvrstani dio niza, gurajući pronađene maksimume do kraja. Shaker sortiranje
Ona je ista shuffle sortirati, ona je ista sortiranje koktela. Proces počinje kao u “mjehuru”: istisnemo maksimum do samog leđa. Nakon toga se okrećemo za 180 0 i idemo u suprotnom smjeru, dok se ne vraćamo na početak na maksimum, već na minimum. Nakon sortiranja prvog i zadnjeg elementa u nizu, ponovno radimo salto. Nakon što smo nekoliko puta išli naprijed i natrag, na kraju završavamo proces, završavajući na sredini popisa. Razvrstavanje par-nepar
Ovaj put nećemo juriti naprijed-natrag po nizu, već ćemo se ponovno vratiti ideji sustavnog hodanja slijeva nadesno, ali samo širim korakom. U prvom prolazu, elementi s neparnim ključem uspoređuju se sa svojim susjedima na parnim mjestima (1. se uspoređuje s 2., zatim 3. s 4., 5. sa 6. i tako dalje). Zatim, naprotiv, uspoređujemo/mijenjamo “parne” elemente s “neparnim”. Pa opet “par-nepar”, pa opet “par-nepar”. Proces se zaustavlja kada se nakon dva uzastopna prolaska kroz polje („nepar-par” i „par-nepar”) ne dogodi niti jedna razmjena. Dakle, sredili su to. 
Za sve su krive kornjače
Malo pozadine. Godine 1980. Włodzimierz Dobosiewicz objasnio je zašto sortiranje s mjehurićima i njegovi derivati rade tako sporo. Sve je to zbog kornjača. "Kornjače" su mali elementi koji se nalaze na kraju liste. Kao što ste možda primijetili, sortiranje u mjehurićima fokusirano je na "zečeve" (ne treba ih brkati s Babuškinovim "zečevima") - elemente velike vrijednosti na početku popisa. Vrlo se žustro kreću prema cilju. Ali spori gmazovi nevoljko puze do početka. Tortilju možete prilagoditi pomoću češljevi. Sortiranje češljem
U "bubble", "shaker" i "odd-even", kada se ponavlja kroz niz, susjedni elementi se uspoređuju. Glavna ideja "češlja" je da se u početku zauzme dovoljno velika udaljenost između elemenata koji se uspoređuju i, kako je niz uređen, da se ta udaljenost smanji na minimum. Na taj način nekako češljamo niz, postupno ga zaglađujući u sve urednije pramenove. 
** Poredano po žarulji ( ukrajinski) – Razvrstavanje mjehurićima
*** Razvrstavanje po češlju ( ukrajinski) – Češljasto razvrstavanje
Prednosti:
minusi:
Neka imamo određeni niz: 3 1 4 2
Uzimamo prvi element "3" i uspoređujemo ga sa sljedećim "1". Jer "3" > "1", zatim zamijenite mjesta:
1 3 4 2
Sada uspoređujemo "3" i "4", tri nije više od četiri, što znači da ne radimo ništa. Zatim usporedite "4" i "2". Četiri je više od dva - pa mijenjamo mjesta: 1 3 2 4. Ciklus je gotov. To znači da bi najveći element već trebao biti postavljen!! Vidimo da se to ovdje dogodilo. Gdje god se nalazi “4” (naš najveći element), on će i dalje biti posljednji nakon što petlja pređe cijeli niz. Analogija - kao što mjehurić zraka lebdi u vodi, tako i naš element lebdi u nizu. Zato se algoritam zove "Bubble Sort". Za pozicioniranje sljedećeg elementa potrebno je ciklus pokrenuti ispočetka, ali posljednji element se više ne može uzeti u obzir jer je na svom mjestu.
Uspoređujemo "1" i "3" - ništa ne mijenjamo.
Uspoređujemo "3" i "2" - Tri je više od dva, što znači da mijenjamo mjesta. Ispada: 1 2 3 4 . Drugi ciklus je završen. Već smo završili dva ciklusa, što znači da možemo sa sigurnošću reći da su naša zadnja dva elementa već posložena. Sve što trebamo učiniti je sortirati treći element, a četvrti će automatski pasti na pravo mjesto. Još jednom uspoređujemo prvi element i drugi - vidimo da već imamo sve na svom mjestu, što znači da se niz može smatrati poredanim uzlaznim redoslijedom elemenata.
Evo rezultata: 
Evo video vodiča
Razvrstavanje mjehurića
Prolazimo kroz niz, provjeravamo prvi broj i drugi, oni su u rastućem redoslijedu. Slijedi kršenje reda, mijenjamo te elemente
1, 2, 5, 7, 6, 3
Nastavljamo prolaziti nizom, 7 je više od 5, ali 6 je manje, pa ih mijenjamo
1, 2, 5, 6, 7, 3
3 kvari redoslijed, zamijeni mjesta sa 7
1, 2, 5, 6, 3, 7
Vraćamo se na početak niza i činimo isto
1, 2, 3, 5, 6, 7
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4Sortiranje višedimenzionalnog niza
Odakle tako neobično ime?
Opis algoritma
Pseudokod temeljen na opisanom algoritmu
Nedostaci metode
Prednosti
Princip vizualnog sortiranja
Primjer sortiranja u obliku mjehurića u Pascalu
Primjer bubble sortiranja u C jeziku