fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. static int hit=0;
  4.  
  5. int partition(vector<int> &a, int l, int r){
  6.  
  7. 	srand(time(NULL));
  8. 	int idx = l + rand() % (r - l + 1);
  9.  
  10. 	swap(a[l], a[idx]);
  11.  
  12. 	int i = l, j = i+1;
  13.  
  14. 	while(j <= r){
  15. 		if(a[j] < a[l])
  16. 			swap(a[++i], a[j]);
  17. 		++j;
  18. 	}
  19.  
  20. 	if(i ^ l)
  21. 		swap(a[l], a[i]);
  22.  
  23. 	return i;
  24. }
  25.  
  26. void quickSrt(vector<int> &a, int l, int r, int &k){
  27.  
  28. 	if(l < r){
  29. 		int i = partition(a, l, r);
  30.  
  31. 		if(i > k-1)
  32. 			quickSrt(a, l, i-1, k);
  33. 		else if(i < k-1)
  34. 			quickSrt(a, i+1, r, k);
  35. 		else
  36. 			return;
  37. 	}
  38. }
  39.  
  40. int main() {
  41. 	vector<int> arr = {42,10,23,5,12,9,3,1,2,35};
  42. 	int k = 6; /* 1 2 3 5 9 10 12 23 35 42 */
  43.  
  44. 	quickSrt(arr, 0, arr.size()-1, k);
  45.  
  46. 	cout<<k<<"th largest element: "<<arr[k-1]<<"\n";
  47.  
  48. 	for(auto val: arr)
  49. 	cout<<val<<" ";
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6th largest element: 10
1 2 3 5 9 10 12 23 42 35
https://ideone.com/EdYSh6
Quick select Kth largest element using randomization
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!