K番目の大きい要素を探します

#include <iostream>
#include <vector>

using namespace std;

#define EXCHANGE(a,b)                           \
  ({typeof(a) _tmp;                             \
    _tmp=a;                                     \
    a=b;                                        \
    b=_tmp;})

template <typename T>
int Partition(vector<T>& arr,int p,int r){

  int x=arr[r];
  int i=p-1;
  int j=0;

  for(j=p;j<=r-1;j++){
    if(arr[j]<=x){
      i=i+1;
      EXCHANGE(arr[i],arr[j]);
    }
  }

  EXCHANGE(arr[i+1],arr[r]);

  return i+1;
}

template <typename T>
void FIND_K(vector<T>& arr,int first,int last,int K){

  int index;

  index = Partition(arr,first,last-1);

  if(index == K)
    return;
  else if(K < index)
    FIND_K(arr,first,index,K);
  else
    FIND_K(arr,index+1,last,K);

  return;
}


int main()
{
  int arr[] = {250,300,350,400,400,\
               450,500,500,550,650,\
               655,700,725,735,750};
  int K;
  int N = sizeof(arr)/sizeof(int);
  vector<int> Arry(arr,arr+N);

  K = N/2;
  FIND_K(Arry,0,N,K);
  cout<<Arry[K]<<endl;

  return 0;
}

ソートされていない配列のセットからK番目の大きな要素を見つけるには、迅速なソートの考え方でソート量を半分に減らすことができます.