sortarea tablourilor de date
DESCRIPTION
- sortarea prin interschimbare ( bubblesort) - sortarea prin metoda bulelorTRANSCRIPT
Sortarea tablourilor de date
Sortarea prin interschimbare (sau metoda bulelor – bubblesort)
Un algoritm de sortare presupune ordonarea crescatoare sau descrescatoare a valorilor
unui tablou unidimensional (vector) de numere (intregi sau reale), sau chiar de siruri de
caractere, caz in care ordonarea este cea alfabetica ( asa cum sunt ordonate cuvintele intr-un
dictionar).
Exista mai multi algoritmi de sortare, mai mult sau mai putin eficienti din punctual de
vedere a timpului de executie.
In continuare vom invata algoritmul de sortare prin interschimbare (bubble sort) sau
sortarea prin metoda bulelor.
Principiu: se considera tabloul a[1],...,a[N] care se parcurge ( de la primul pana la
ultimul element), comparand si interschimband perechile de elemente alaturate care nu
satisfac relatia de ordine, procedeul repetandu-se pana cand in timpul unei parcurgeri
nu se face nicio interschimbare.
Exemplu:
Se parcurge vectorul
In timpul parcurgerii s-au facut doua interschimbari, deci se parcurge dinnou vectorul
7 21 -4 -7 0 1 5 4 2 10
0 1 2 4 3 5 6 7 8 9
v
7 21 -4 -7 0 1 5 4 2 10
0 1 2 4 3 5 6 7 8 9
v
In timpul parcurgerii s-au facut trei interschimbari, deci se parcurge dinnou vectorul
In timpul parcurgerii s-au facut trei interschimbari, deci se parcurge dinnou vectorul
In timpul parcurgerii s-au facut trei interschimbari, deci se parcurge dinnou vectorul
In timpul parcurgerii s-au facut doua interschimbari, deci se parcurge dinnou vectorul
7 -4 21 -7 0 1 4 5 2 10
0 1 2 4 3 5 6 7 8 9
v
-4
7 -7 21 0 1 4 2 5 10
0 1 2 4 3 5 6 7 8 9
v
-4 -7 7 0 21 1 2 4 5 10
0 1 2 4 3 5 6 7 8 9
v
-7 -4 0 7 1 21 2 4 5 10
0 1 2 4 3 5 6 7 8 9
v
-7 -4 0 1 7 2 21 4 5 10
0 1 2 4 3 5 6 7 8 9
v
In timpul parcurgerii s-au facut doua interschimbari, deci se parcurge dinnou vectorul
In timpul parcurgerii s-au facut doua interschimbari, deci se parcurge dinnou vectorul
In timpul parcurgerii s-au facut doua interschimbari, deci se parcurge dinnou vectorul
In timpul parcurgerii nu s-a facut nicio interschimbare, algoritmul se opreste si vectorul contine
elementele sortate.
PROBLEMA:
Sa se scrie un program C++ care citeste un sir de n elemente intr-un vector de numere intregi,
unde n<=100 este un numar natural introdus de la tastatura, sorteaza prin interscimbare
elementele acestui vector, dupa care le afiseaza.
-7 -4 0 1 2 7 4 21 5 10
0 1 2 4 3 5 6 7 8 9
v
-7 -4 0 1 2 4 7 5 21 10
0 1 2 4 3 5 6 7 8 9
v
-7 -4 0 1 2 4 5 7 10 21
0 1 2 4 3 5 6 7 8 9
v
IMPLEMENTARE:
# include <iostream.h>
# include <conio.h>
int v[100], i, n, inters, aux;
void main(){
clrscr();
cout<<”n=”;
cin>>n;
for( i=0; i<n; i++ ){
cout<< ”v[” << i << “]=”;
cin >> v[i];
}
do {
inters=0;
for(i=0; i<n-1; i++)
if( v[i] > v[i+1] ){
aux = v[i];
v[i] = v[i+1];
v[i+1] = aux;
inters++;
}
} while(inters!=0);
cout<<” v = { ”<<v[0];
for( i=1; i<n; i++ )
cout<<”, ”<<v[i];
cout<<” }”;
getch();
}
TEMA:
1) Modificati programul anterior astfel incat vectorul sa fie ordonat descrescator.
2) Sa se scrie programul care sorteaza un vector, al carui elemente se citesc di fisierul
TABLOU.IN, il sorteaza crescator si scrie rezultatul in fisierul TABLOU.OUT.
3) Sa se scrie programul care sorteaza un vector, al carui elemente se citesc di fisierul
TABLOU.IN, il sorteaza descrescator si scrie rezultatul in fisierul TABLOU.OUT.