I thought of a one-liner to sort a list in Python, but it hasn't been working. I thought that I could use reduce to go through the list and swap elements as needed, like in bubble sort. But the interpreter is being frustrating today:
from functools import reduce
def reduce_sort(*lst):
sorter = lambda x, y: y, x if x > y else x, y
return reduce(sorter, lst)
reduce_sort(5, 4, 6, 7, 1)
This is giving me NameError: name 'x' is not defined
Does anyone have any idea why this is happening?
Sorting with functools.reduce is a good idea.
However, once you start combining two or more elements from the initial list into a sorted sublist, your function sorter = lambda x, y: y, x if x > y else x, y is no longer adequate: it only knows how to combine two elements into a length-2 list; it doesn't know how to combine two sorted lists into a sorted list.
Example:
initial list = [17, 45, 100, 96, 29, 15, 0, 32, 4, 100, 61, 11, 85, 96, 2, 75, 88, 51, 16, 27, 68, 74, 99, 27, 83, 38, 96, 40, 73, 99, 33, 36, 86, 54, 50, 36, 44, 56, 0, 62, 62, 87, 64, 14, 63, 78, 98, 64, 60, 57, 56, 80, 80, 32, 40, 51, 64, 29, 21, 43, 63, 44, 35, 25, 37, 10, 13, 9, 34, 10, 39, 70, 14, 33, 49, 16, 80, 50, 14, 82, 51, 82, 67, 10, 20, 6, 59, 5, 31, 62, 83, 92, 13, 59, 71, 65, 1, 25, 78, 45]
began reducing = [[17, 45], [96, 100], [15, 29], [0, 32], 4, 100, 61, 11, 85, 96, 2, 75, 88, 51, 16, 27, 68, 74, 99, 27, 83, 38, 96, 40, 73, 99, 33, 36, 86, 54, 50, 36, 44, 56, 0, 62, 62, 87, 64, 14, 63, 78, 98, 64, 60, 57, 56, 80, 80, 32, 40, 51, 64, 29, 21, 43, 63, 44, 35, 25, 37, 10, 13, 9, 34, 10, 39, 70, 14, 33, 49, 16, 80, 50, 14, 82, 51, 82, 67, 10, 20, 6, 59, 5, 31, 62, 83, 92, 13, 59, 71, 65, 1, 25, 78, 45]
sorter([15, 29], [0, 32]) = ???
How to fix this sorter function? What we want is to be able to merge two sorted lists into a sorted list. Does this ring a bell? Yes! It's the merge function from mergesort.
We could implement it ourselves... Or we can look in the python standard modules if it isn't already implemented somewhere. It is. It's called heapq.merge.
sorter with heapq.mergeLet's replace your sorter with heapq.merge:
import random
import functools
import heapq
ll = [random.randint(0,100) for i in range(100)]
list(functools.reduce(heapq.merge, ll))
# TypeError: 'int' object is not iterable
Oops! heapq.merge expects two iterables. Initially our list doesn't contains lists, it contains single elements. We need to replace these single elements with singleton lists or singleton tuples:
import random
import functools
import heapq
ll = [(random.randint(0,100),) for i in range(100)]
list(functools.reduce(heapq.merge, ll))
# [3, 3, 4, 5, 5, 5, 7, 8, 8, 10, 11, 13, 15, 15, 15, 15, 16, 16, 17, 18, 19, 20, 20, 20, 24, 25, 25, 27, 27, 28, 30, 30, 30, 30, 31, 32, 33, 33, 38, 38, 39, 39, 41, 42, 43, 43, 43, 46, 46, 47, 49, 50, 51, 52, 53, 55, 62, 63, 63, 64, 64, 64, 65, 66, 67, 68, 69, 71, 72, 72, 72, 72, 73, 73, 73, 74, 78, 79, 82, 82, 83, 83, 86, 86, 86, 86, 89, 91, 92, 93, 95, 96, 96, 96, 97, 98, 99, 99, 100, 100]
It works! Note the ( ,) construct inside of ll that makes singleton tuples. If you don't like tuples and would prefer lists, you can use [ ] instead of ( ,).
Of course, you want to be able to sort a list that contains numbers, not singleton tuples. So let's add lambda x: (x,) or lambda x: [x] to our mix:
import functools
import heapq
def reduce_sort(ll):
list(functools.reduce(heapq.merge, map(lambda x: (x,), ll)))
import random
ll = [random.randint(0,100) for i in range(100)]
reduce_sort(ll)
# [3, 3, 4, 5, 5, 5, 7, 8, 8, 10, 11, 13, 15, 15, 15, 15, 16, 16, 17, 18, 19, 20, 20, 20, 24, 25, 25, 27, 27, 28, 30, 30, 30, 30, 31, 32, 33, 33, 38, 38, 39, 39, 41, 42, 43, 43, 43, 46, 46, 47, 49, 50, 51, 52, 53, 55, 62, 63, 63, 64, 64, 64, 65, 66, 67, 68, 69, 71, 72, 72, 72, 72, 73, 73, 73, 74, 78, 79, 82, 82, 83, 83, 86, 86, 86, 86, 89, 91, 92, 93, 95, 96, 96, 96, 97, 98, 99, 99, 100, 100]