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