Printing a Dictionary Items Sorted by Its Keys

Question

class Company(object):
    def __init__(self, name):
        self.name = name
        self.employees = {}

    def addEmployee(self, id, name):
        self.employees[id] = name

    def displayEmployees(self):
        tmp = [ (k,v) for k,v in self.employees.items() ]
        tmp.sort()
        for k,v in tmp:
            print(k, '\t', v)

a = Company('The Company')
a.addEmployee(111, 'Employee1')
a.addEmployee(222, 'Employee2')
a.addEmployee(333, 'Employee3')
a.displayEmployees()

Is there another way to sort a dictionary by its keys to keep having the following output without using a new variable?:

111      Employee1  
222      Employee2  
333      Employee3

Answer 1

For a large number of employees, near-optimal might be:

class Company(object):
    def __init__(self, name):
        self.name = name
        self.employee_ids = []
        self.employees = {}
        self.sorted = True

    def addEmployee(self, id, name):
        self.employee_ids.append(id)
        self.employees[id] = name
        self.sorted = False

    def displayEmployees(self):
        if not self.sorted:
            self.employee_ids.sort()
            self.sorted = True
        for k in self.employee_ids:
            print k, '\t', self.employees[k]

This takes O(N) to insert N employees -- while keeping the self.employee_ids sorted with each insertion would make such an operation O(N squared). In exchange, this approach makes displayEmployees worst-case O(N log N) -- but often better because of the preternaturally good performance of "timsort", Python's sorting algorithm (a variant on natural mergesort) in the real world. For example, if you add just one employee (with a random id that may need to go in the middle) then call displayEmployees, that's just O(N) -- timsort magic.

Josh Bloch of "Effective Java" fame, then a Google employee, was at a tech-talk presenting Python's timsort and got, metaphorically speaking:-), struck by lightning on the road to Damascus -- pulled out his laptop (I remember we were both sitting in the front row) and started hacking. Soon after, timsort became the way Java sorts an array of objects, too (alas, not an array of primitives -- for technical reasons, that had to remain a less robust variant of "quicksort").

BTW, timsort is named after its inventor, Tim Peters, also known as "the timbot" in Python circles (being "a bot" in the Python community involves being able to respond to a lot of technical questions, very fast, and usually correctly; Tim was the first one so honored). The second one was F.Lundh, "the effbot". I was later honored to be named the third (and as far as I know last) one, as "the martellibot". However, I've never developed any algorithm one tenth as cool as timsort!-)

TL;DR: using bisect to maintain a list in sorted order is a classic and apparently cool idea, but, don't do it. I don't recall ever seeing a situation where it was a clear win. Usually, it's best to just append new stuff to the list, and sort as needed; occasionally, module heapq in the standard library (with insertions being O(log N), not O(N) like in bisect) may be better for a peculiar application.

One more note: the self.sorted flag is a tiny (?) optimization only worth it if you're likely to call displayEmployees repeatedly with no addEmployee call in-between; you may well simplify the code by omitting it with no ill effects if such a pattern is not going to happen -- that doesn't change big-O behavior, anyway:-)

Answer 2

Sort just the keys and look up the values using the sorted() function:

def displayEmployees(self):
    for key in sorted(self.employees):
        print(key, self.employees[key], sep='\t')

or sort the items inline:

def displayEmployees(self):
    for key, value in sorted(self.employees.items()):
        print(key, value, sep='\t')

Answer 3

Regular dicts don't remember order. If keeping your dict's order is important to you for the rest of your code, one alternative is to use the OrderedDict from Python's collections module. You can do this while adding your employees:

from collections import OrderedDict

# ...

def addEmployee(self, id, name):
    self.employees[id] = name
    self.employees = OrderedDict(sorted(self.employees.items()))

This will always keep your self.employees dict ordered and will reduce your display code to:

def displayEmployees(self):
    for k,v in self.employees.items():
        print(k, '\t', v)

Answer 4

A few time ago I made a dict class with a __str__ method that would show items more or less the way you wanted it. See if you're interested:

class EmployeeDict(dict):
    '''Just a dictionary, but with a better display of data.

    '''

    def __str__(self):
        str_output = ""
        maxlen = len(str(max(self.keys())))
        for key in sorted(self.keys()):
            str_output += "{} | {}\n".format(str(key).rjust(maxlen), self[key])
        return str_output


class Company(object):
    def __init__(self, name):
        self.name = name
        self.employees = EmployeeDict()

    def addEmployee(self, id, name):
        self.employees[id] = name

    def displayEmployees(self):
        print(str(self.employees))

a = Company('The Company')
a.addEmployee(111, 'Employee1')
a.addEmployee(222, 'Employee2')
a.addEmployee(333, 'Employee3')
a.displayEmployees()

The output:

111 | Employee1
222 | Employee2
333 | Employee3