Quick select: Select Kth smallest element in an array of size n in O(n) time.

#include <iostream>
using namespace std;

inline void swap(int arr[],int i,int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
}

int randint(int len) {
      srand(time(NULL));
    //srand((unsigned)rdtsc());
    return (rand() % (len) + 0);
}

int randomPartition(int arr[],int start , int end) {
      int pivotPos = randint(end-start) + start;
      swap(arr,start,pivotPos);
      
      int pivot = arr[start], i = start+1, j= start+1;
      pivotPos = start;
      for(;j<=end; j++) {
            if(arr[j] < pivot) {
                  swap(arr,i,j);
                  i++;
            }
      }
      swap(arr,pivotPos,i-1);
      pivotPos = i-1;
      return pivotPos;
}

int Rselect(int arr[],int start, int end, int k) {
    int pivotPos = randomPartition(arr,start,end);
    if(pivotPos == k) 
        return arr[k];
    else if(pivotPos < k)
        return Rselect(arr,pivotPos+1,end,k);
    else
        return Rselect(arr,start,pivotPos-1,k);
}

int main() {
    int arr[] = {40,1,10,70,2,5,30,9,8,6};
    int size = sizeof arr/sizeof arr[0];
    cout<<"Kth greatest = "<<Rselect(arr,0,size-1,3);
    system("pause");
    return 0;
}