Elementul Median Divide et Impera

Problema Elementului Median se reduce defapt la calcularea celui mai mare/mai mic k element dintr-o secventa(de exemplu, in sirul [1 8 4 2 5] al treilea cel mai mic element este 4) problema ce se poate rezolva folosind Divide et Impera.

Ideea:selectia unui element dintr-un sir se poate reduce la sortarea sirului, ca mai apoi sa se extraga elementul dorit.
♣ Aceasta metoda este eficienta cand mai multe selectii trebuiesc facute intr-o lista, pentru ca exista doar O sortare initiala SCUMPA, urmata de operatii IEFTINE de extractie.

Algoritmul ineficient pentru extragerea celui mai mic/mai mare k element are complexitate temporala O(kn), si presupune alegerea celei mai "extreme" valori (cea mai mare/mica) si mutarea acesteia spre "inceputul" vectorului, pana ajungem la elementul dorit.

function select(list[1..n], k)
     for i from 1 to k
         minIndex = i
         minValue = list[i]
         for j from i+1 to n
             if list[j] < minValue
                 minIndex = j
                 minValue = list[j]
         swap list[i] and list[minIndex]
     return list[k]

Sursa cod:Wikipedia

ALGORITMUL DE SELECTIE GENERAL BAZAT PE PARTITIONARE

Algoritm creat de Hoare, inventatorul quicksort. Se mai numeste si quickselect.
Asemenea lui quicksort, acest algoritm foloseste o functie de paritionare care poate, in timp liniar (luand indecsii elementelor din vector de la stanga la dreapta), sa grupeze vectorul in doua parti:

• elementele mai mici decat un anumit element ales, numit PIVOT si
• elementele mai mari sau egale cu pivotul.

Adica o secventa [4 7 3 8 2 5 0], dupa calcularea pivotului, ar arata asa: [0 3 2 4 7 5 8], unde 4 este pivotul.

Iata codul in C++ (varianta mea)

//ELEMENT MEDIAN by Iulix

#include<iostream>
#include<stdint.h>
#include<math.h>
#include<vector>


using namespace std;

void interschimbare(int &a, int &b){
int aux;
aux = a;
a = b;
b = aux;
}

int partition_secv(vector<int> &secv, int left, int right, int indexPivot){
//patitionare quicksort
	int pivotValue, storeIndex;
	int i;
	pivotValue = secv[indexPivot];
	interschimbare(secv[indexPivot], secv[right]); //duc pivotul la sfarsitul vectorului
	storeIndex = left;
	
	for(i=left; i <=right-1; i++)
		if(secv[i]<pivotValue){
								interschimbare(secv[i], secv[storeIndex]);
								storeIndex++;
								}
	interschimbare(secv[right], secv[storeIndex]);

return storeIndex;
} 

int select_secv(vector<int> &secv, int left, int right, int k){
//algoritmul quickselect al lui Hoare	
	int newIndexPivot, indexPivot, pivotDistance=0;	
		
	if(left==right)
		return secv[left];
	indexPivot = secv[left]; //aleg pivotul initial ca fiind cel mai din stanga element
	newIndexPivot = partition_secv(secv, left, right, indexPivot); //noul pivot
	/*calculam pivotDistance, ceea ce inseamna distanta pivotului "maxim sortat" fata de cel mai din stanga 
	element al vectorului - in acest moment, deoarece a fost executata functia partition_secv, 
	vectorul va fi de forma (elemente mai mici decat pivot sortate)(pivot)(elemente mai mari decat pivot sortate)
	*/
	pivotDistance = newIndexPivot - left;
	//apoi comparam cu indexul cautat, k, ca sa vedem unde ne situam (in stanga pivotului sau in dreapta lui?)
	if(pivotDistance==k) return secv[newIndexPivot];
		else if(k > pivotDistance) //trebuie sa ma duc in dreapta
				return select_secv(secv, newIndexPivot+1, right, k - pivotDistance + 1);
			else //trebuie sa ma duc in stanga
				return select_secv(secv, left, newIndexPivot-1, k);
}

int main(){

vector<int> secventa;
int myint;
int k;
cout<<"Introduceti numerele din secventa:\nTastati 0 la sfarsitul secventei\n";

do{
	cin>>myint;
	secventa.push_back(myint);
}while(myint);

cout<<"Secventa pe care ati introdus-o: ";
int i;
for(i=0; i<secventa.size(); i++)
	cout<<secventa[i]<<" ";
cout<<"\n";

cout<<"introduceti k:\n"; cin>>k;

cout<<"Al "<<k<<"-lea cel mai mic element este "<<select_secv(secventa, 0, secventa.size()-1, k)<<"\n";


return 0;
}

Complexitatea temporala este in cel mai bun caz O(n), iar in cel mai rau caz, O(n^2).
Complexitatea acestui algoritm depinde in mare masura de alegerea pivotilor - de aceea s-a implementat un algoritm asemanator, BFPRT, in care vectorul este impartit in bucati de cate cinci elemente, carora apoi li se calculeaza elementul "median" (adica pivotul).

Resurse:
Wikipedia

Syntax Highlighters

Syntax Highlighters

Vrei sa transformi un cod ce arata asa:

#include<stdio.h>
#include<stdlib.h>

int main(){
 printf("Hello World");
 return 0;
}

...intr-un cod care arata asa:

#include<stdio.h>
#include<stdlib.h>

int main(){
 printf("Hello World");
 return 0;
}

Nimic mai simplu! Pentru HTML, poti folosi hilite.me , un site unde introduci codul tau (nu neaparat ceva in C, exista o gramada de optiuni) si care ti-l transforma in cod html.

Pentru mai multe Syntax Highlighters poti incerca acest site.

Have fun!

Merge Sort Divide et Impera

Divide et Impera - Merge Sort

Algoritmii Divide et Impera:

• impart problema in subprobleme asemanatoare cu cea initiala, mai mici ca dimensiune pe care apoi le rezolva recusiv si apoi combina solutiile pentru a crea o solutie pentru problema originala;
• 3 pasi:
  • Divide: problema data este divizata intr-un set de subprobleme;
  • Impera: subproblemele sunt rezolvate recursiv (daca sunt suficient de mici, sunt rezolvate direct);
  • Combina: solutiile problemelor sunt combinate pentru a obtine solutia problemei initiale;
• Avantaje: algoritmi eficienti; faciliteaza paralelizarea algoritmului;
• Dezavantaje: overheaddatorat recusivitatii.

Merge Sort

1.Divide: divide cele n elemente ce trebuie sortate in n/2, pana se ajunge la submultimi de UN element -care sunt deja sortate.
2.Impera: sorteaza recursiv secventele folosind Merge Sort.
3.Combina: se asambleaza solutiile initiale.

Lucrurile vor evolua cam asa:


Sursa Imaginii: Wikipedia

Si acum, codul meu...



Codul (in C):

// Mergesort in C
  #include<stdio.h>
  #include<stdlib.h>

#define INF 3200

int p=1; int r=7;
int A[100];


int initialize_vector(int A[]){
A[1]=10 ;A[2]=1 ;A[3]=17 ;A[4]=0 ;A[5]=2 ;A[6]=1 ;A[7]=0 ;
}

int MERGE_eu(int A[],int p, int q, int r){
 int n1, n2; //n1 = nr elem din stanga, n2 = nr elem din dreapta
 n1 = q-p+1;
 n2 = r-q;
//S[] = vector elem stanga, D[] = vector elem dreapta - alocare dinamica
 int *S, *D;
 S = (int *)calloc(n1+1, sizeof(int));
 D = (int *)calloc(n2+1, sizeof(int));
//acum initializam vectorii, S preia valorile din A-ul stang, D din A-ul drept
 int i, j;
 for(i=1; i<=n1; i++)
  S[i]=A[p+i-1];
 for(j=1; j<=n2; j++)
  D[j]=A[q+j];
 
 S[n1+1]=INF; D[n2+1]=INF;
 i=1; j=1;
 
 int k;
 for(k=p; k<=r; k++)
  if(S[i]<=D[j]){
   A[k]=S[i]; i=i+1;}
  
  else {
   A[k]=D[j]; j=j+1; } 
}

int MERGE_SORT_eu(int A[], int p, int r){
     if(p<r){ //daca p>=r, inseamna ca vectorul are maxim 1 element -e sortat deja
 int q = (p+r)/2; //mijlocul vectorului
 MERGE_SORT_eu(A, p, q); //stanga
 MERGE_SORT_eu(A, q+1, r); //dreapta
 MERGE_eu(A, p, q, r); //combinarea subsecventelor
 }

}

int main(){
 printf("test\n");
 initialize_vector(A);
 MERGE_SORT_eu(A,p,r);
int i;
for(i=p; i<=r; i++)
 printf("%d ", A[i]);
printf("\n");

return 0;
}

Surse:

• Wikipedia - Merge Sort Divide and Conquer
• Cormen - Introducere in Algoritmi
• Cursul de Proiectarea Algoritmilor