Sortarea prin interclasare MergeSort 

Informaţii generale:

            Definim interclasarea a două liste sortate ca fiind operaţia prin care obţinem o listă sortată ce conţine toate elementele listelor de intrare. 

    Sortarea prin interclasare utilizeaza metoda Divide et Impera: 

-se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie uşor ordonată la un moment dat, apoi interclasată cu o altă secvenţă din vector, de asemenea ordonată. 

-practic, interclasarea va începe când se ajunge la o secvenţă formată din doua elemente. Cele doua secvente se vor interclasa şi vor alcătui un subşir ordonat din vector, mai mare, care, la rândul lui se va interclasa cu subşirul corespunzator obţinut în acelaşi mod, ş.a.m.d. 

Prezentarea algoritmului: 

         Ideea este de a utiliza interclasarea în etapa de asamblare a soluţiilor: în urma rezolvării recursive a subproblemelor obţinute prin aplicarea tehnicii de programare “Divide et Impera” rezultă liste ordonate şi prin interclasarea lor obţinem lista iniţială sortată. 

Algoritmul de sortare implică trei etape: 

Problema interclasării a doi vectori sortaţi a şi b se rezolvă astfel: 

-se utilizează un vector intermediar, c; 

-se compară elementul de pe poziţia întâi din primul vector cu elementul de pe poziţia întâi din al doilea vector; dacă este mai mic elementul primului vector, acesta se copiază în vectorul c, apoi se creşte indicele de parcurgere astfel încât la următoarea comparaţie să indice cel de-al doilea element; dacă este mai mic elementul din b, se va copia el în c, iar indicele de parcurgere al lui b se incrementează pentru a selecta al doilea element din b; 

-prin comparaţii succesive, se construieşte vectorul c ordonat, până se termină elementele din a sau b; elementele rămase în b, sau a, după caz, se vor copia în ordine în c;

 

Exemplu1: Fie vectorul de sortat 2,  9,  5,  3,  7,  1,  6,  4

 

Şirul de intrare

  2,  9,  5,  3 --- 7,  1,  6,  4

Împărţire (1)

  2,  9 --- 5,  3         si      7,  1 --- 6,  4

Împărţire(2)

  2 --- 9  si 5 --- 3       si       7 --- 1  si 6 --- 4

Sortare(2) – se face direct,

deoarece subşirurile au

maxim 2 elemente fiecare

 

 2 --- 9  si 3 --- 5        si       1 --- 7  si 4 --- 6

Interclasare (2)

 2 , 3, 5, 9           si            1 ,4 ,6 ,7

 

Interclasare(1)

  1 ,  2 ,  3 ,  4 ,  5 ,  6  , 7 , 9

Şirul final

1   2   3   4   5   6   7  9

 

Exemplu2: Reamintesc interclasarea.

 

a: 1 2 4 7 8 9

Se compară a[1] cu b[1]; se va copia în c elementul cel mai mic, respectiv a[1]; se va indica următorul element din vectorul a

b: 3 5 6

c: 1

a: 1 2 4 7 8 9

Se compară a[2] cu b[1]; se va copia în c elementul  a[2] şi se va indica în continuare a[3]

b: 3 5 6

c: 1 2

a: 1 2 4 7 8 9

Se compară a[3] cu b[1]; se va copia în c elementul b[1] şi se va indica b[2] pentru următoarea comparaţie

b: 3 5 6

c: 1 2 3

a: 1 2 4 7 8 9

Se compară a[3] cu b[2]; se va copia în c elementul a[3], şi se indică a[4]

b: 3 5 6

c: 1 2 3 4

a: 1 2 4 7 8 9

Se compară a[4] cu b[2]; se trece în c elementul b[2]; se indică b[3]

b: 3 5 6

c: 1 2 3 4 5

a: 1 2 4 7 8 9

Se compară a[4] cu b[3]; se trece în c b[3]; se termină vectorul b, deci se copiază în c toate elementele rămase neparcurse în a;

b: 3 5 6

c: 1 2 3 4 5 6

c: 1 2 3 4 5 6 7 8 9

 

 

Varianta pseudocod a  algoritmului:

procedura mergeSort(x,st,dr); 

dacă st  < dr atunci

                  m←[(st+dr)/2] 

                  mergeSort(x,st,m); 

                  mergeSort(x,m+1,dr) 

                  interclasează subvectorii (x[st],…,x[m]),(x[m+1],…x[dr]) ; 

         sfârşit dacă; 

sfârşit mergeSort;

   Pentru a stabili complexitatea algoritmului de sortare prin interclasare, remărcam urmatoarele: 

- pentru un vector cu n elemente, numărul de înjumătăţiri succesive până se ajunge la subvectori de lungime 1 sau 2 este de aproximativ log2n şi nu depinde de valorile din vector; 

- la fiecare din aceste divizări succesive, se mută din x într-un vector auxiliar pentru interclasare şi invers în total n elemente. 

   În consecinţă, numarul de operaţii elementare executate este de ordinul O(n∙log2n).

          Constatăm deci că, pentru tablouri cu număr mare de componente, timpul de calcul este mult mai mic în cazul sortării prin interclasare, decât în cazul folosirii algoritmilor simpli, cum ar fi cel al selecţiei, inserţiei sau al bulelor, a căror complexitate este O(n2). 

          Algoritmul de sortare prin interclasare consumă însă de două ori mai multă memorie decât cei simpli mentionaţi, deoarece necesită spaţiu suplimentar pentru vectorul auxiliar .

Implementare C++: 

int x[20], n; 

void sort(int st, int dr, int x[20]){

int aux; 

if (x[st]>x[dr]) { 

aux=x[st]; 

x[st]=x[dr]; 

x[dr]=aux;} 

} 

void interclasare(int st, int dr, int m, int x[20]){

int b[20], i, j, k; 

i=st; j=m+1; k=1; 

while(i<=m && j<=dr) 

        if(x[i]<=x[j]){ 

  b[k]=x[i];   i++;  k++;

else    {b[k]=x[j];   j++; k++;  }

 

if(i<=m) 

         for(j=i;j<=m;j++)   { b[k]=x[j];     k++;       } 

else 

         for(i=j;i<=dr;i++)  { b[k]=x[i];     k++;        }

k=1; 

for(i=st;i<=dr;i++){ 

           x[i]=b[k]; 

           k++; } 

}

 void divimp(int st, int dr, int x[20]){ 

 int m; 

  if((dr-st)<=1)    sort(st, dr, x); 

  else  {m=(st+dr)/2; 

            divimp(st,m,x); 

            divimp(m+1,dr,x); 

            interclasare(st, dr, m, x); 

   } 

} 

void main(){

int i; 

cin>>n; 

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

divimp(1, n, x); 

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

}

Implementare Pascal:

type vector=array [1..20] of integer; 

var i,n:integer; x,b:vector; 

procedure sort(st,dr:integer); 

var aux:integer; 

begin 

if x[st]>x[dr] then 

begin 

aux:=x[st];   x[st]:=x[dr];  x[dr]:=aux; 

end; 

end; 

procedure interclasare(st,dr,m:integer); 

var i, j, k:integer; 

begin 

i:=st; j:=m+1; k:=1; 

while (i<=m) and( j<=dr) do 

if x[i]<=x[j] then 

       begin 

b[k]:=x[i]; i++;  k++;

end 

       else     begin 

                    b[k]:=x[j];  j++;   k++;

     end; 

if i<=m then 

         for j:=i to m do   begin 

b[k]:=x[j]; k++;            

end; 

else 

         for i:=j to dr do    begin 

b[k]:=x[i]; k++;           

end; 

k:=1; 

for i:=st to dr do begin   x[i]:=b[k];      k++; end; 

end; 

procedure divimp(st, dr:integer); 

var m:integer; 

begin 

if (dr-st)<=1 then  sort(st, dr); 

                     else    begin 

     m:=(st+dr) div 2; 

                            divimp(st,m); 

                            divimp(m+1,dr); 

                            interclasare(st, dr, m); 

   end; 

end; 

begin 

readln(n); 

for  i:=1 to n do readln(x[i]); 

divimp(1,n); 

for  i:=1 to n do write(x[i] ,’ ’) ; 

end.

  Mergi la pagina METODE DE SORTARE

 

Aplicatii

Aplicaţie1: Se citesc n numere complexe din fişierul date.in si două numere reale a,b. 

Să se scrie în fişierul date.out în ordine crescătoare modulele numerelorcomplexe care nu aparţin intervalului [a,b].

Program C++:

#include <fstream.h>

#include <iomanip.h>

ifstream fin(“date.in”);

ofstream fies(“date.out”);

struct complex{float re, im;};

void citirec (complex &c){

fin>>c.re>>c.im; }

void citire(int &n, complex x[100], float &a, float &b){

int i;

fin>>n;

for(i=1; i<=n; i++) citirec(x[i]);

fin>>a>>b; }

float modul (complex c) {

return sqrt(c.re*c.re +c.im*c.im); }

void intercl(int a[100], int s, int m, int d){

int i,j,k, b[100];

i=s; j=m+1; k=1;

while (i<=m && j<=d)

            if (a[i]<a[j]) b[k++]=a[i++];

            else b[k++]=a[j++];

while (i<=m) b[k++]=a[i++];

while (j<=d) b[k++]=a[j++];

k=1;

for (i=s; i<=d; i++) a[i]=b[k++];}

void mergesort (int a[100], int s, int d) {

int m;

if (s<d) {

m=(s+d)/2;

mergesort(a,s,m);

mergesort(a, m+1, d);

intercl(a,s,m,d); } }

void scriere (float a[1000], int n){

int i;

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

fies<<fixed<<setprecision(3)<<a[i]<<” “; }

void main () {

complex c[100];

float a, b, x[100];

int i, k=0, n;

citire (n, c, a, b);

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

            if (modul(c[i]) modul(c[i]>b))

                        x[++k]=modul(c[i]);

mergesort(x,1,k);

scriere (x, k);

fin.close();

fies.close(); }

Program Pascal:

PROGRAM MergeSort1;

TYPE complex=RECORD

            re, im : REAL;

                        END;

vectorc=ARRAY[1..100] OF complex;

vectorr=ARRAY[1..100] OF REAL;

VAR c:vectorc; x:vectorr; a,b:REAL; i, k, n:INTEGER;

PROCEDURE citire (VAR n:INTEGER; VAR x:vectorc; VAR a,b:REAL);

VAR i:INTEGER; fin:TEXT;

BEGIN

ASSIGN (fin, ‘date.in’);

RESET(fin);

READ(fin, n);

FOR i:=1 TO n DO READ(fin, x[i].re, x[i].im);

READ(fin, a, b); CLOSE (fin); END;

FUNCTION modul (c: complex):real;

BEGIN

modul:=sqrt(c.re*c.re+c.im*c.im); END;

PROCEDURE intercl(VAR a:vectorr; s,m,d:INTEGER);

VAR i,j,k:INTEGER; b:ARRAY[1..100] OF INTEGER;

BEGIN

i:=s; j:=m+1; k:=1;

WHILE (i<=m) AND (j<=d) DO

            IF a[i]<a[j] THEN

                        BEGIN

                        b[k]:=a[i]; i:=i+1; k:=k+1;

                        END

            ELSE

                        BEGIN

                        b[k]:=a[j]; j:=j+1; k:=k+1;

                        END;

WHILE i<=m DO

                        BEGIN

b[k]:=a[i]; i:=i+1; k:=k+1;

                        END;

WHILE j<=d DO

                        BEGIN

b[k]:=a[j]; j:=j+1; k:=k+1;

                        END;

k:=1;

FOR i:=s TO d DO a[i]:=b[k]; END;

PROCEDURE MergeSort(a:vectorr; s,d:INTEGER);

VAR m: INTEGER;

BEGIN

IF s

            BEGIN

m:=(s+d) DIV 2;

MergeSort(a,s,m);

MergeSort(a,m+1,d);

intercl(a,s,m,d);

END;

END;

PROCEDURE scriere (a:vectori; n:INTEGER);

VAR i:INTEGER; fies:TEXT;

BEGIN

ASSIGN (fies, ‘date.out’);

REWRITE(fies);

FOR i:=1 TO n DO WRITE(fies, a[i], ‘ ‘);

CLOSE(fies); END;

BEGIN

citire (n,c,a,b);

FOR i:=1 TO n DO

            IF (modul(c[i])<a) OR (modul(c[i]>b) THEN

                        BEGIN

                        k:=k+1; x[k];=modul(c[i]);

                        END;

MergeSort (x,1,k);

scriere (x,k);

END.

 

 

 Mergi la pagina METODE DE SORTARE

 

 

 

 

 
Propriul site simplu, rapid, Gratuit
Designed by Free CSS Templates.