Skip to content
Create a gist now

Instantly share code, notes, and snippets.

@coleifer / secret
Created Aug 28, 2012

def partition(A, idx, start=0, end=None):
if end is None:
end = len(A)
pivot = A[idx]
A[idx], A[end - 1] = A[end - 1], A[idx]
pos = start
for i in range(start, end):
if A[i] < pivot:
if i != pos:
A[pos], A[i] = A[i], A[pos]
pos += 1
A[pos], A[end - 1] = A[end - 1], A[pos]
return pos
def nsmallest(A, n, start=0, end=None):
if end is None:
end = len(A)
partition_idx = partition(A, start, start, end)
if partition_idx == n:
return A[:n]
elif partition_idx < n:
return nsmallest(A, n, partition_idx + 1, end)
return nsmallest(A, n, start, partition_idx)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.