from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import random


def kth_smallest(nums, k):
	"""Kth smallest element selection.

    Just select the kth element, without caring about the 
    relative ordering of the rest of them.

    Time complexity: O(n).
    Space complexity: O(n).
	"""
	pivot = random.choice(nums)

	pos_middle = [pos for pos, x in enumerate(nums) if x == pivot]
	pos_smaller = [pos for pos, x in enumerate(nums) if x < pivot]
	pos_bigger = [pos for pos, x in enumerate(nums) if x > pivot]

	n_smaller = len(pos_smaller)
	n_middle = len(pos_middle)

	if k <= n_smaller:
		nums_smaller = [nums[pos] for pos in pos_smaller]
		return kth_smallest(nums_smaller, k)
	elif n_smaller < k <= n_smaller + n_middle:
		return pivot
	elif k > n_smaller + n_middle:
		nums_bigger = [nums[pos] for pos in pos_bigger]
		return kth_smallest(nums_bigger, k - n_smaller - n_middle)


def main():
	n = 100
	nums = list(range(1, n))
	random.shuffle(nums)

	print('Median: {}'.format(kth_smallest(nums, n // 2)))
	print('Min: {}'.format(kth_smallest(nums, 1)))
	print('Max: {}'.format(kth_smallest(nums, len(nums))))


if __name__ == '__main__':
	main()

@@ -377,26 +377,23 @@
 nums)%0A%0A%09
-pos_middle
+mid_pos
  = %5Bpos 
@@ -438,27 +438,25 @@
 pivot%5D%0A%09
-pos_
 small
-er
+_pos
  = %5Bpos 
@@ -500,26 +500,25 @@
 pivot%5D%0A%09
-pos_bigger
+large_pos
  = %5Bpos 
@@ -574,36 +574,32 @@
 mall
-er
  = len(
-pos_
 small
-er
+_pos
 )%0A%09n_mid
 dle 
@@ -598,28 +598,22 @@
 _mid
-dle
  = len(
-pos_middle
+mid_pos
 )%0A%0A%09
@@ -631,26 +631,22 @@
 mall
-er
 :%0A%09%09
-nums_smaller
+small_nums
  = %5B
@@ -670,19 +670,17 @@
  in 
-pos_
 small
-er
+_pos
 %5D%0A%09%09
@@ -703,20 +703,18 @@
 est(
-nums_smaller
+small_nums
 , k)
@@ -727,18 +727,16 @@
  n_small
-er
  %3C k %3C= 
@@ -738,34 +738,32 @@
 k %3C= n_small
-er
  + n_mid
 dle:%0A%09%09retur
@@ -746,27 +746,24 @@
 mall + n_mid
-dle
 :%0A%09%09return p
@@ -788,18 +788,16 @@
 mall
-er
  + n_mid
 dle:
@@ -796,26 +796,22 @@
 _mid
-dle
 :%0A%09%09
-nums_bigger
+large_nums
  = %5B
@@ -835,18 +835,17 @@
  in 
-pos_bigger
+large_pos
 %5D%0A%09%09
@@ -868,19 +868,18 @@
 est(
-nums_bigger
+large_nums
 , k 
@@ -891,18 +891,16 @@
 mall
-er
  - n_mid
 dle)
@@ -899,11 +899,8 @@
 _mid
-dle
 )%0A%0A%0A

Revise var names