SelectionSearch

int partitionRandom(int* arr, int start, int end) {
    int temp;
    do {
        temp = rand()%end;
    } while (temp < start);
    int pivot = arr[temp];
    int left = start;
    int right = end;
 
    while (left <= right) {
 
        while (arr[left] < pivot && left < end)
            left++;
        while (arr[right] > pivot && right > start)
            right--;
 
        if (right < left)
            Swap(&arr[left], &arr[right]);
    }
 
    Swap(&arr[right], &arr[start]);
 
    return right;
}
 
void SelectionSearch(int* arr, int start, int end, int pos) {
        
    int pivot = partitionRandom(arr, start, end);
    int S = pivot - 1 - start + 1;
    if ( pos == S + 1) return;
    if (  pos < S + 1) return SelectionSearch(arr, start, pivot-1, pos);
    else return SelectionSearch(arr, pivot + 1, end, pos - S - 1 );
}