def random_selection(a, start, end, i):
 if (start < end):
  p = choosePivot(start, end)
  (a[start], a[p]) = (a[p], a[start])
  j = partition(a, start, end)
  if (j == i):
   return a[i]
  if (j < i):
   return random_selection(a, (j + 1), end, i)
  else:
   return random_selection(a, start, (j - 1), i)
 else:
  return a[start]

def random_selection ( a , start , end , i ) : if ( start < end ) : p = choosePivot ( start , end ) ( a [ start ] , a [ p ] ) = ( a [ p ] , a [ start ] ) j = partition ( a , start , end ) if ( j == i ) : return a [ i ] if ( j < i ) : return random_selection ( a , ( j + 1 ) , end , i ) else : return random_selection ( a , start , ( j - 1 ) , i ) else : return a [ start ]
returns the ith order statistic in the array a in linear time .