BubbleSort

Sortarea prin interschimbare BubbleSort

Informaţii generale:

Metoda de sortare BubbleSort porneşte de la o proprietate evidentă a unui şir sortat: oricare două elemente alăturate respectă relaţia de ordine. Astfel, dacă oricare pereche de elemente alăturate respectă relaţia de ordine, atunci, conform tranzitivităţii relaţiei, întreg şirul va fi ordonat. Cele două elemente consecutive ale şirului de sortat vor forma “bulele” pe care se va verifica relaţia de ordine cerută. Este cea mai simplă metodă de sortare şi nu necesită cunoaşterea detaliată a limbajului de programare.

Prezentarea algoritmului:

Se parcurge vectorul de sortat şi se compară elementele consecutive. Dacă acestea nu se află în ordinea dorită, se interschimbă. Când se va ajunge la ultimul element al vectorului, parcurgerea se reia şi se vor verifica din nou elementele vecine, cu realizarea interschimbărilor acolo unde sunt necesare, până când, la o ultimă parcurgere nu mai este necesară nici o interschimbare, prin urmare, vectorul este ordonat.

Se va folosi o variabilă de tip logic, care va marca dacă la o parcurgere se fac interschimbări (se iniţializează la începutul parcurgerii, iar dacă se face măcar o interschimbare, i se va schimba valoarea). Algoritmul se opreşte atunci când această variabilă îşi păstrează valoarea primită la începutul parcurgerii (nu au mai fost necesare interschimbări).

Exemplu : şirul iniţial este {5, 8, 4, 7, 6}

i	x[1]	x[2]	x[3]	x[4]	x[5]
x[1],x[2]	5	8	4	7	6
Compar 5 cu 8: ordinea e cea dorită
x[2],x[3]	5	8	4	7	6
Compar 8 cu 4: ordinea nu e cea dorită ; se interschimbă
x[3],x[4]	5	4	8	7	6
Compar 8 cu 7: ordinea nu e cea dorită ; se interschimbă
x[4],x[5]	5	4	7	8	6
Compar 8 cu 6: ordinea nu e cea dorită ; se interschimbă ; se reia parcurgerea
x[1],x[2]	5	4	7	6	8
Compar 5 cu 4: ordinea nu e cea dorită ; se interschimbă ;
x[2],x[3]	4	5	7	6	8
x[3],x[4]	4	5	7	6	8
x[4],x[5]	4	5	6	7	8
La următoarea parcurgere, nu se mai realizează interschimbări

Varianta pseudocod a algoritmului:

repetă

ok←fals;

pentru i←1, n-1 execută

dacă x[i]>x[i+1] atunci

x[i]↔x[i+1];

ok←adevarat;

sfârşit dacă;

sfârşit pentru;

până când ok=fals;

Observaţii :

Ultima parcurgere a vectorului se face fără interschimbări.
După prima parcurgere, elementul maxim s-a deplasat către ultima poziţie, după a doua, maximul dintre primele n-1 elemente s-a deplasat către penultima poziţie, etc; deci, la fiecare nouă parcurgere ar fi suficient să mergem cu un pas mai puţin decât la parcurgerea anterioară. Se poate construi, astfel, un algoritm îmbunătăţit:

index←n;

repetă

ok←fals;

pentru i←1, index-1 execută

dacă x[i]>x[i+1] atunci

x[i]↔x[i+1];

ok←adevarat;

sfârşit dacă;

sfârşit pentru;

index←index-1;

până când ok=fals;

Numărul de comparaţii efectuate nu depinde de gradul de sortare al şirului iniţial, fiind în orice situaţie .

În schimb, numărul de interschimbări depinde de proprietăţile şirului iniţial, astfel:

- în cazul cel mai favorabil (şir sortat crescător) sunt necesare 0 interschimbări;

- în cazul cel mai defavorabil (şir sortat descrescător), se vor efectua interschimbări, deci atribuiri.

Aşadar, algoritmul prezentat mai sus aparţine clasei O(n²).

Implementare C++:

{ok=0;

for( i=1;i<n;i++)

if (x[i]>x[i+1])

{aux=x[i];

x[i]=x[i+1];

x[i+1]=aux;

ok=1;

}

}while(ok);

Implementare Pascal:

repeat

ok:=true;

for i:=1 to n do

if x[i]>x[i+1] then

begin

aux:=x[i];

x[i]:=x[i+1];

x[i+1]:=aux;

ok:=false;

end;

until ok;

Mergi la pagina METODE DE SORTARE

Aplicatii

Aplicaţie1: Se citeşte un vector a cu n elemente numere întregi.

Să se ordoneze crescător elementele vectorului folosind metoda bulelor.

Program C++:

#include <iostream.h>

#include <conio.h>

int n,i, a[20];

void citire(){

cin>>n;

for(i=1; i<=n; i++) cin>>a[i];}

void afis(){

for(i=1; i<=n; i++) cout<<a[i]<<” ”;}

void bule (int a[20], int n){

int aux, gata;

do {

gata=1;

for(i=1; i<n; i++)

if (a[i]>a[i+1]){

aux=a[i]; a[i]=a[i+1]; a[i+1]=aux;

gata=0;}

} while (!gata); }

void main() {

citire();

bule (a,n);

afis();

getch(); }

Program Pascal:

PROGRAM BubbleSort1;

TYPE vector= ARRAY[1..20] OF INTEGER;

VAR a:vector;

i, n: INTEGER;

PROCEDURE citire;

BEGIN

READLN(n);

FOR i:= 1 TO n DO READLN(a[i]);

END;

PROCEDURE afis;

BEGIN

FOR i:= 1 TO n DO WRITELN(a[i], ’ ’);

END;

PROCEDURE bule (VAR a:vector; VAR n:INTEGER);

VAR aux:INTEGER; gata:BOOLEAN;

BEGIN

REPEAT

gata:=TRUE;

FOR i:= 1 TO n-1 DO

IF a[i]>a[i+1] THEN

BEGIN

aux:=a[i]; a[i]:=a[i+1]; a[i+1]:=aux;

gata:=FALSE;

END;

UNTIL gata;

END;

BEGIN

citire;

bule(a.n);

afis;

END.

Aplicaţie2: Se citeşte un vector a cu n elemente numere naturale.

Să se ordoneze descrescător elementele vectorului după valoarea inversatului fiecărui element.

Program C++:

#include <iostream.h>

#include <conio.h>

int n,i, a[20];

void intersch(int &x, int&y){

int aux=x; x=y; y=aux;}

int inversat (int n) {

int inv=0;

while (n) {

inv=inv*10+n%10;

n=n/10; }

return inv; }

void sortare (int a[20], int n){

int gata;

do {

gata=1;

for(i=1; i<n; i++)

if (inversat(a[i])<inversat(a[i+1])){

intersch(a[i], a[i+1]);

gata=0;}

} while (!gata); }

void main() {

cin>>n;

for(i=1; i<=n; i++) cin>>a[i];

sortare (a,n);

for(i=1; i<=n; i++) cout<<a[i]<<” ”;

getch(); }

Program Pascal:

PROGRAM BubbleSort2;

TYPE vector= ARRAY[1..20] OF INTEGER;

VAR a:vector;

i, n: INTEGER;

PROCEDURE intersch (VAR x,y:INTEGER);

VAR aux:INTEGER;

BEGIN

aux:=x; x:=y; y:=aux;

END;

FUNCTION inversat (n:INTEGER):INTEGER;

VAR inv:INTEGER;

BEGIN

inv:=0;

WHILE n<>0 DO

BEGIN

inv:=inv*10 +n mod 10;

n:=n div 10;

END;

inversat:=inv;

END;

PROCEDURE SORTARE (VAR a:vector; VAR n:INTEGER);

VAR gata:BOOLEAN;

BEGIN

REPEAT

gata:=TRUE;

FOR i:= 1 TO n-1 DO

IF inversat(a[i])<inversat(a[i+1]) THEN

BEGIN

intersch(a[i], a[i+1])

gata:=FALSE;

END;

UNTIL gata;

END;

BEGIN

READLN(n);

FOR i:= 1 TO n DO READLN(a[i]);

sortare(a.n);

FOR i:= 1 TO n DO WRITELN(a[i], ’ ’);

END.

Aplicaţie3: Din fişierul text clasa.in se citesc următoarele informaţii despre fiecare elev din clasă: numele, prenumele, media. Să se afişeze elevii din clasă ordonaţi descrescător după medie.

Program C++:

#include <iostream.h>

#include <conio.h>

#include

ifstream f(”clasa.in”);

struct elev {

char nume[20], prenume[20];

double media} c[30];

void main() {

int i, n;

f>>n;

for(i=1; i<=n; i++)

f>>c[i].nume>>c[i].prenume>>c[i].media;

int gata;

do {gata=1;

for(i=1; i<n; i++)

if (c[i].media<c[i+1].media) {

elev aux=c[i];c[i]=c[i+1];

c[i+1]=aux; gata=0;}

} while (!gata);

for(i=1; i<=n; i++)

cout<<c[i].nume<<” ”<<c[i].prenume<<” ”c[i].media<<endl;

f.close();

getch(); }

Program Pascal:

PROGRAM BubbleSort3;

TYPE elev=RECORD

nume, prenume: STRING[20]

media:REAL; END;

vector= ARRAY[1..30] OF elev;

VAR c:vector; aux:elev; gata:BOOLEAN;

i, n: INTEGER; f:TEXT;

BEGIN

ASSIGN( f, ’clasa.in’);

RESET(f);

READLN(f,n);

FOR i :=1 TO n DO

READ (f, c[i]. nume, c[i].prenume, c[i].media);

REPEAT

gata:=true;

FOR i:= 1 TO n-1DO

IF c[i].media<c[i+1].media THEN

BEGIN

aux:=c[i];c[i]:=c[i+1];

c[i+1]:=aux;gata:=FALSE;

END;

UNTIL gata;

FOR i:=1 TO n DO

WRITELN(c[i]. nume, ’ ’, c[i].prenume, ’ ’c[i].media) ;

CLOSE(f);

END.

Aplicaţie4: Se consideră o listă liniară simplu înlănţuită. Scrieţi o funcţie care să ordoneze crescător nodurile din listă. Funcţia va primi ca parametru adresa primului nod al listei.

Observaţie:

Vom folosi o structură numită nod de forma:

-info de tip întreg;

-urm de tip pointer către un nod.

Funcţie C++:

void bubblesortasc (nod *prim) {

int gata; nod *p;

do {

gata=1;

for (p=prim;p->urm;p=p->urm )

//parcurg lista, începând cu primul nod

if (p->info > p->urm->info) {

int aux=p->info;

p->info=p->urm->info;

p->urm->info=aux;

gata=0;}

while (!gata); }

Funcţie Pascal:

PROCEDURE bubblesortasc(prim: adresa);

VAR p:adresa; gata:BOOLEAN; aux:INTEGER;

BEGIN

REPEAT

gata:=TRUE;

p:=prim;

WHILE p^.urm<>NIL DO

BEGIN

IF p^.info> p^.urm^.info THEN

BEGIN

aux:=p^. info; p^. info:= p^.urm^.info;

p^.urm^.info:=aux; gata:=FALSE;

END;

UNTIL gata;

END;

Mergi la pagina METODE DE SORTARE