Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Lazy sorter - an iterator that yields items in sorted order, lazily
from itertools import tee
def lazy_sort(v, key=lambda x: x):
v = iter(v)
try:
pivot = next(v)
except StopIteration:
return
v_pre, v_pos = tee(v)
yield from lazy_sort((item for item in v_pre if key(item) < key(pivot)), key)
yield pivot
yield from lazy_sort((item for item in v_pos if key(item) >= key(pivot)), key)
"""
This is exactly the same as above - but using the fresh "extradict.Grouper" class,
published with extradict 0.5.0;
(Actually, when writting the snippet above I missed this "tee like" functionality,
and wrote the new class in the package)
"""
from itertools import tee
from extradict import Grouper
def lazy_sort(v, key=lambda x: x):
v = iter(v)
try:
pivot = next(v)
except StopIteration:
return
kpivot = key(pivot)
groups = Grouper(v, key= lambda item: key(item) < kpivot)
yield from lazy_sort(groups.get(True, ()), key=key)
yield pivot
yield from lazy_sort(groups.get(False, ()), key=key)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment