Quick Select -Finding K'th Largest

Quick select is one of very popular algorithm used to find k'th largest element in a list. It can be use to find median or finding k'th smallest element etc.

Finding K'th largest element looks easy , we just need to sort & get K'th largest . But here we are dealing with time so we need fastest way to do this

 Time complexity of Quick Select (average case) =O(n)

 Quick Select is basically modified version of Quick sort. In Quick Sort we need to sort all element but Quick select just want to know pivot value that divide array in given ratio.

Quick sort 

let a example we have 10 different number in array  & we want to find 3rd largest element.(we  assume 0..9 index array) then in sorted array its position should be (10-3)th Index.



So basically we have to do is find a pivot that divide array in 2 group ,left group contain all element less then pivot and right group contain all element greater than pivot .
So if we want 3rd largest element then pivot index will be (n-3) and data at that index is third largest data .

If you did not Understand than probability you don't know Quick sort . I strongly Recommend first to understand Quick sort. Even though you did't get it then follow our code .

Quick Select -Find K'th largest element 

---

1. //Quick Selelct
2. //very useful for
3. //Find kth largest or smallest element
4. //find median
5. //O(n)
7. //this program demonstrate to find K'th largest from given list
8. //assuming all are different numbers
9. #include<iostream>
10. #include<vector>
11. using namespace std;
13. int Quick_Select(vector<int> &arr,int p,int r,int index_of_kth_largest);
14. int partition(vector<int> &arr,int p,int r,int pivot);
16. int main(){
17.         vector<int> arr;
18.         int n,k;
19.         cout<<"Enter No of element (n) :";
20.         cin>>n;
21.         cout<<"Enter Value of k :";
22.         cin>>k;
23.         cout<<"Enter array element :"<<endl;
24.         int key;
25.         for(int i=0;i<n;i++){
26.                 cin>>key;
27.                 arr.push_back(key);
28.         }
29.         int kth=Quick_Select(arr,0,n-1,n-k);
30.         cout<<"K'th largest number is "<<kth;
31.         return 0;
32. }
34. int Quick_Select(vector<int> &arr,int p,int r,int index_of_kth_largest){
35.         //We are basically finding situation when pivote == index_of_kth_largest
36.         //then all elemnt less than that is on left side and all element greter than that is in right side
37.         if(index_of_kth_largest==r)
38.                 return arr[r];
39.         int pivotI;
40.         while(1){
41.                 pivotI=(p+r)/2;
42.                 pivotI=partition(arr,p,r,pivotI);
43.                 if(pivotI== index_of_kth_largest)
44.                         return arr[pivotI];
45.                 //make sure to chhose proper sub arr where index=index_of_kth_largest reside
46.                 if(pivotI <index_of_kth_largest)
47.                         p=pivotI+1;
48.                 if(pivotI>index_of_kth_largest)
49.                         r=pivotI-1;
50.         }
51. }
52. int partition(vector<int> &arr,int p,int r,int pivotIndex){
53.         int i=p-1;
54.         //swap and move pivote  data to end
55.         int temp;
56.         int pivot=arr[pivotIndex];
57.         temp=arr[pivotIndex];
58.         arr[pivotIndex]=arr[r];
59.         arr[r]=temp;
60.        
61.         //arrange arr such that all elemnt below pivote come to left side of pivotIndex
62.         //and all elemnt greter than pivot come right side of pivotIndex
63.         for(int j=p;j<r;j++){
64.                 if(pivot<=arr[j]){
65.                         i++;
66.                         temp=arr[i];
67.                         arr[i]=arr[j];
68.                         arr[j]=temp;
69.                 }
70.         }
71.         i++;
72.         temp=arr[i];
73.         arr[i]=arr[r];
74.         arr[r]=temp;
75.         return i;
76. }