Sort dictionary by increasing length of its values

Question

Given a dictionary where the values are iterables, print the dictionary sorted by the length of its values.

def sort_dict_by_value_len(lst):
    while lst:
        min_key = min([(len(v), k) for (k, v) in lst.items()])
        print(min_key[1], lst.pop(min_key[1]))

sort_dict_by_value_len({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten'})

1 one
2 two
6 six
10 ten
4 four
5 five
9 nine
3 three
7 seven
8 eight

I feel like I'm doing too much computations, and worst of all, I'm emptying the input list. Is there any better way to achieve this, with or without using sort or sorted, and optionally keeping the dictionary intact?

Answer 1

• Calling a dictionary a list is very confusing

• Rather than using min, you could use sorted.

  This'll change the time complexity of your code from \$O(n^2)\$ to \$O(n \log n)\$, as Python uses the Timsort. And since sorted is written in C, it'll be super fast too.

  Sorted also has the keyword argument key, which lets you sort by another value, rather than the value you get.

  This also keeps the original dictionary intact.

• You can use dict and enumerate to build your input list. And to build a list to pass to enumerate you could use str.split.

And so I'd change your code to:

def sort_dict_by_value_len(dict_):
    return sorted(dict_.items(), key=lambda kv: (len(kv[1]), kv[0]))

def sort_dict_by_value_len_without_key(dict_):
    return [(k, dict_[k]) for _, k in sorted((len(v), k) for (k, v) in dict_.items())]

dict_ = dict(enumerate('one two three four five six seven eight nine ten'.split(), start=1))
for key, value in sort_dict_by_value_len(dict_):
    print(key, value)

---

If you only want \$O(1)\$ memory usage, then you could use an insertion sort. But keeps the \$O(n^2)\$ time complexity. I also cheated a bit.

• I used a generator comprehension, rather than a list comprehension to ensure \$O(1)\$ space. Alternately, you could invert the algorithm, and pop from one array to another.
• I used bisect.insort to remove most of the logic.

def sort_dict_by_value_len(dict_):
    output = []
    while dict_:
        key, value = dict_.popitem()
        bisect.insort(output, ((len(value), key), (key, value)))
    return (i[1] for i in output)

Answer 2

For me, the magic of Python is evident in this one-liner (magic line in comments):

dictionary_sorted = ({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten'})
dictionary_mixed = ({5: 'five', 3: 'three', 7: 'seven', 1: 'one', 10: 'ten', 4: 'four', 9: 'nine', 6: 'six', 2: 'two', 8: 'eight'})

dictionary = dictionary_mixed

# Begin magic line
sortedKeyList = sorted(dictionary.keys(), key=lambda s: len(dictionary.get(s)))
# End magic line

for index in xrange(len(sortedKeyList)):
    print("{}: {}".format(sortedKeyList[index], dictionary[sortedKeyList[index]]))

A few takeaways (for those reading):

1. You cannot sort a dictionary because they have no concept of order
2. Lists CAN be sorted because order is in their nature
3. The sorted() function returns an iterable (list), which by default is a list sorted by increasing value (unless you include optional reverse=True argument). Here, we are asking that value to be the length of the dict's value for each key. We sort the keys to get the values back later for printing.
4. Again, the dictionary data structure by nature has no concept of order as in Python's dict and the interviewer specifically requested the output to be printed, not returned, for this reason.
5. If you still want to satisfy your itch, you can implement a high-performance sort algorithm (i.e. merge sort) using Python's collections.OrderedDict() and then simply print in-order. Yet, again, you'd be sorting more than you need because you really just need the keys.

In any case, an interviewer should love this Pythonic one-liner approach :)

EDIT: If you want to sort the results by key in case multiple value lengths are equal, you could use a while loop. The full code would be:

dictionary_sorted = ({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten'})
dictionary_mixed = ({5: 'five', 3: 'three', 7: 'seven', 1: 'one', 10: 'ten', 4: 'four', 9: 'nine', 6: 'six', 2: 'two', 8: 'eight'})

dictionary = dictionary_mixed

# Begin magic line
sortedKeyList = sorted(dictionary.keys(), key=lambda s: len(dictionary.get(s)))
# End magic line

# BEGIN sort by keys if values are equal
beg_eq_vals_index = 0
end_eq_vals_index = 0
cur_val = -1

while end_eq_vals_index < len(sortedKeyList):
    if len(dictionary[sortedKeyList[end_eq_vals_index]]) > cur_val > -1:
        # Replace slice of key list with sorted key list slice
        sortedKeyList[beg_eq_vals_index:end_eq_vals_index] = sorted(sortedKeyList[beg_eq_vals_index:end_eq_vals_index])

        # Update beginning index to end index in order to start a new section
        beg_eq_vals_index = end_eq_vals_index

        # Update current value used to determine sub-sections with equal values
        cur_val = len(dictionary[sortedKeyList[beg_eq_vals_index]])
    else:
        if cur_val == -1:
            cur_val = len(dictionary[sortedKeyList[end_eq_vals_index]])

    # Move end of current section ahead one spot
    end_eq_vals_index += 1
# END sort by keys if values are equal

for index in xrange(len(sortedKeyList)):
    print("{}: {}".format(sortedKeyList[index], dictionary[sortedKeyList[index]]))

You could test this by adding the reverse=True optional argument to the "magic line" sorted call, which results in a sorted call that looks like:

# Begin magic line
sortedKeyList = sorted(dictionary.keys(), key=lambda s: len(dictionary.get(s)), reverse=True)
# End magic line

Which has an output of:

3: three
7: seven
8: eight
4: four
5: five
9: nine
1: one
2: two
6: six
10: ten

So, you can see that even when we reverse the list, the sub-sections are correctly sorted in ascending key order. Still, this is not the best performance approach so keep that in mind.