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).
Wikipedia
