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
import random
import string
from lazyquicksort import lazy_sort
def chars(length):
options = string.ascii_lowercase
return ''.join([random.choice(options) for i in range(length)])
if __name__ == '__main__':
elements = chars(10)
print('Original:', elements)
print('Sorting...')
for i, e in enumerate(lazy_sort(elements), start=1):
print(f' step {i:2d}: {e}')
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))
yield pivot
yield from lazy_sort(item for item in v_pos if key(item) >= key(pivot))
@danielgoncalves

This comment has been minimized.

Copy link
Owner Author

@danielgoncalves danielgoncalves commented Oct 9, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment