Quickselect. Find the i-th order statistics in Python using Quicksort's randomized selection. This is a solution for https://www.hackerrank.com/challenges/find-median Note it is probably a better idea to pass the indices around instead of slicing (quicksort is an in-place sorting algorithm). But for simplicity, let's just use slice (which create…

qselect.py

import random
def q_select(numbers, ith):
    if len(numbers) < 2:
        return numbers[0]
    # Chooses a pivot uniformly from random
    p_index = random.randint(0, len(numbers)-1)
    pivot = numbers[p_index]

    # Before the partition, swap the pivot with the last element
    numbers[p_index], numbers[-1] = (
        numbers[-1], numbers[p_index])

    # i is always the last element smaller than your pivot
    # j is always the first element larger than your pivot
    i = -1
    for j in xrange(0, len(numbers)):
        if numbers[j] < pivot:
            numbers[j], numbers[i+1] = (
                numbers[i+1], numbers[j]
            )
            i += 1

    # After partition swap back the pivot to its rightful position
    numbers[i+1], numbers[-1] = (
        numbers[-1], numbers[i+1]
    )

    # Update the new pivot index (where it should be belong now)
    p_index = i + 1

    # Since we are using zero-indexed list, subtract 1 from everything
    if p_index == ith - 1:
        return numbers[p_index]
    # When the ith order statistics is to the right of pivot
    elif ith > p_index:
        return q_select(numbers[p_index+1:], ith - p_index - 1)
    else:
        return q_select(numbers[:p_index], ith)

if __name__ == "__main__":
    n = int(raw_input().strip())
    numbers = raw_input().strip().split()
    numbers = map(int, (s for s in numbers))
    print(q_select(numbers, (n//2)+1))