Find Kth largest element in an unsorted array.

code:

1. Partition method (" Selection Rank " k) :

int partition (int a[], int left, int right, int pivot){
     while(true){
          while (left<= right && a[left] <= pivot){
                left ++ ;
          }
          while (left <= right && a[right] > pivot){
                right --;
          }
          if (left>right){                    //end case.
               return left-1;
          }
          swap( a+left, a+right);
      }
 }

int Kbig(int a[], int left, int right, int k){
        int pivot = a[(random()-left)%(right-left)+left] ;

        int leftEnd = partition(a, left, right, pivot);
        int leftSize = leftEnd - left +1;

        if ( leftSize == k) return Max(a+left, a+leftSize); //return pivot?                //end case.
        else if (leftSize > k) return Kbig ( a, left, leftEnd, k);
        else if (leftSize < k) return Kbig (a, leftEnd+1, right, k-leftSize);
}
 

2. Similar, using vector<int> to partition:

vector<int>  Kbig(vector<int> s, int k){
     vector<int> res, sa, sb;
     if(k<=0) return res;
     if(s.size()<=k) return s;

     // if(s.size() > k)
     Partition(s, &sa,&sb);
     return Kbig(sa, k). append (Kbig(sb, k- sa.size());
}

void Partition (vector<int> s, vector<int> &a, vector<int> &b){
   
       pos = random()%s.size();
       swap(s[0], s[pos]);
       int pivot = s[0];

       for( int i=1;i<s.size();++i){
             s[i]> pivot? a.push_back(s[i]) : b.push_back(s[i]);
       }
     
      a.size() < b.size()? a.push_back(pivot): b.push_back(pivot). // To avoid null array & more average.
}