SORTAREA TABLOURILOR UNIDIMENSIONALE PRIN METODA

BULELOR-BUBBLE SORT-

Prof. Sofroni Iulia

SEMNIFICAŢIA NOŢIUNII DE SORTARE

A sorta un tablou înseamnă a rearanja elementele tabloului astfel încât între acestea să existe o relaţie de ordine (crescătoare sau descrescătoare)

DESCRIEREA METODEI

Prin această metodă se parcurge tabloul şi se compară fiecare element cu succesorul său. Dacă nu sunt în ordine, cele două elemente se interschimbă între ele. Tabloul se parcurge de mai multe ori, până când, la o parcurgere completă, nu se mai execută nici o interschimbare între elemente (adică tabloul este sortat).

ENUNŢUL PROBLEMEI:Se dă un tablou a cu n elemente întregi. Să se realizeze sortarea crescătoare a elementelor tabloului.

Parcurgere I

7 25108

21 43

5

5

a:

f=1; f=0;

f==0?DA SE REIA PARCURGEREA TABLOULUI

Parcurgere II

7 25108

21 43

5

5

a:

f=1; f=0;

f==0DA SE REIA PARCURGEREA TABLOULUI

Parcurgere III

7 2558

21 43

10

5

a:

f=1; f=0;

f==0DA SE REIA PARCURGEREA TABLOULUI

Parcurgere IV

7 2585

21 43

10

5

a:

f=1; f=0;

f==0DA SE REIA PARCURGEREA TABLOULUI

Parcurgere V

5 2587

21 43

10

5

a:

f=1;

f==0 ?NU TABLOUL ESTE ORDONAT CRESCĂTOR

VARIABILE NECESAREa – tabloul unidimensional;n – lungimea tabloului;aux – pentru interschimbul

elementelor (de acelaşi tip cu elementele tabloului);

i – contor (utilizat pentru parcurgerea tabloului);

f – variabilă care indică dacă s-au realizat interschimbărif=1 (fără interschimbări)f=0 (s-au realizat interschimbări)

ALGORITM C++Do{ f=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; f =0;}While (!f);

Variabile necesare a – tabloul

unidimensional; n – lungimea tabloului; aux – pentru

interschimbul elementelor (de acelaşi tip cu elementele tabloului);

i – contor (utilizat pentru parcurgerea tabloului);

f – variabilă care indică dacă s-au realizat interschimbări f=1 (fără

interschimbări) f=0 (s-au realizat

interschimbări)

METODA BULELOR - OPTIMpoz=n;Do{ f=1; for(i=1;i<poz;i++) if(a[i]>a[i+1]) { aux =a[i]; a[i] =a[i+1]; a[i+1]=aux; f =i;

} poz=f;}while (f>1);

variabile poz – pentru a memora

pozitia la care s-a realizat ultimul interschimb

f – variabilă care va memora pozitia la care s-a realizat interschimbarea

Parcurgere I de la pozitia 1->4

8 7525

21 43

10

5

a:

poz=5; f=2;

f>1?DA SE REIA PARCURGEREA TABLOULUI

f=1;f=3f=4Poz=4

Parcurgere II

8 2575

21 43

10

5

a:

f=1; f=2;

f>1 ?DA SE REIA PARCURGEREA TABLOULUI

Parcurgere I de la pozitia 1->3

poz=2

Parcurgere III de la pozitia 1->2

7 2558

21 43

10

5

a:

f=1; f=2; poz=2;

f>1 ?DA SE REIA PARCURGEREA TABLOULUI

Parcurgere IV

5 2587

21 43

10

5

a:

f=1;

f>1?NU TABLOUL ESTE SORTAT

APLICATIA 11. Dându-se un tablou cu n elemente numere

naturale, şi o variabilă p naturală (p<n), să se sorteze crescător tabloul până la elementul p şi de la elementul p descrescător.

APLICATIA 2(PROB 16/199) Să se memoreze într-un vector n cifre. Să se

afișeze cel mai mic număr care se poate obține cu aceste cifre.

Exemplu: Daca vectorul este 4 0 0 0 2 1 atunci numarul cerut este 100024.

TEMA1. Dându-se un tablou cu n elemente numere

naturale, să se localizeze elementul maxim şi toate elementele dinaintea lui să se sorteze crescător, iar cele de după el descrescător.

2. Problema 9/1983. Se introduc n numere de câte una sau

două cifre. Să se afişeze aceste numere în ordinea crescătoare a primei lor cifre. Exemplu: pentru n=5 şi numerele 34 2 5 62 25 se va afişa

2 25 34 5 62 sau 25 2 34 5 62.