Divide et impera

Incep cu un algoritm destul de simplu, care se face in liceu. Celebrul Divide et Impera... dezbina si cucereste. Think of it this way... esti la un party cu mult alcool. Daca combini toate bauturile si le dai pe gat, va fi foarte greu sa ramai treaz dupa, dar daca le imparti in paharele mici si le bei incet pe rand, atunci e mult mai usor si mai placut :)

Asa e si cu divide et impera... avem o problema grea, pe care o impartim in mai multe probleme mai mici, pana ajungem la o problema elementara care nu ne creeaza dificultati. Impartirea se face recursiv.

Sa luam ca exemplu MergeSort... un algoritm foarte dragalas de sortare a numerelor dintr-un vector... Care e ideea de baza? Pai tot impartim vectorul in jumate pana cand ajungem la 1 element.. care e sortat... dupa unim 2 jumatati de cate 1 element si le sortam, dupa unim 2 jumatati de 2 elemente etc.

Aici avem o implementare in C a algoritmului. Algoritmul standard este enuntat in carti ca incepand de la 1, noi il vom incepe aici de la 0.

Programul il puteti downloada si de aici.

#include <stdio.h>

#define MAXINT 32767;



void MERGE(int vector[],int start,int mijloc,int sfarsit)

{
int lungime1=mijloc-start;
int lungime2=sfarsit-mijloc;

int inceput_vector[lungime1+1];
int sfarsit_vector[lungime2+1];

int i,j,k;
for (i=0;i<lungime1;i++){

inceput_vector[i]=vector[start+i];
}

for (j=0;j<lungime2;j++){

sfarsit_vector[j]=vector[mijloc+j];
}

inceput_vector[lungime1]=MAXINT;
sfarsit_vector[lungime2]=MAXINT;

i=0;
j=0;
for (k=start;k<sfarsit;k++){

if(inceput_vector[i]<sfarsit_vector[j]){
vector[k]=inceput_vector[i];

i++;
}else{
vector[k]=sfarsit_vector[j];

j++;
}
}
}


void MERGEsort(int vector[],int start,int sfarsit)

{
int mijloc;
if (start<sfarsit-1) {

mijloc=(start+sfarsit)/2;
MERGEsort(vector,start,mijloc);

MERGEsort(vector,mijloc,sfarsit);
MERGE(vector,start,mijloc,sfarsit);

}
}

int main()
{
int vector[5]={2,5,1,4,3};

MERGEsort(vector,0,5);
int i;

for (i=0;i<5;i++)
printf("%i ",vector[i]);

return 0;
}

Programul asta va rula in mare parte conform imaginii urmatoare:


Deci, ideea de baza: impartim vectorul in bucati mai mici, iar apoi unim bucatile respective in ordine...

Urmeaza intrebarea: cat este complexitatea algoritmului? Pai O(n log n), mult mai bine decat bubblesort si sortarea cu 2 foruri, care au O(n^2).


Un alt algoritm foarte folosit este Binary Search-ul. Este un algoritm care cauta un element intr-un vector sortat, avand o complexitate O(log n). Cum ajunge la complexitatea asta? Pai face asa. Vede daca elementul este la mijloc. Daca nu e, atunci... daca e mai mic decat mijlocul, cauta in jumatatea inferioara, iar daca e mai mare, in jumatarea superioara.

Programul este cam asa (fisier txt) :

#include <stdio.h>

int BinarySearch(int vector[],int start,int sfarsit,int element)

{
if (start==sfarsit) return -1;//sau -start pentru a obtine pozitia pe care ar trebui sa se afle;

int mijloc = (start+sfarsit)/2;
if (vector[mijloc]==element) return mijloc;

if (vector[mijloc]<element) return BinarySearch(vector,start,mijloc,element);

if (vector[mijloc]>element) return BinarySearch(vector,mijloc+1,sfarsit,element);

}

int main()
{
int vector[5]={1,2,3,4,6};

printf("%i\n",BinarySearch(vector,0,5,3));

printf("%i\n",BinarySearch(vector,0,5,5));

return 0;
}

Evident, sunt mult mai multe aplicatii ale acestui algoritm, dar cam asta e conceptul de baza. Si tineti minte... Daca aveti mai multi amici care se cearta, intai ii separati, dupa discutati cu fiecare in parte, dupa ii readuceti la un loc si ii puneti sa discute intre ei. ;)