1
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
2
  • this has to be a duplicate of countless questions Dec 27, 2014 at 0:12
  • 1
    This question concerns printing the items contained by a dictionary sorted by its keys. The accepted answer in the question indicated as a duplicate proposes the use of OrderedDict which stores its keys in sorted order.
    – DavidRR
    Jan 22, 2015 at 15:05

4 Answers 4

4

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:-)

0
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')
0

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)
2
  • 1
    It's inefficient creating an entire new dictionary each time, you may as well sort when you print
    – jamylak
    Dec 27, 2014 at 0:05
  • Yes, that's why I said only if the order is important to the functionality, and not just for printing. Thanks for the info though.
    – kartikg3
    Dec 27, 2014 at 0:09
0

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
4
  • Admittedly, it was more for fun, but still!
    – Roberto
    Dec 27, 2014 at 1:47
  • len(str(max(self.keys()))) gives you the length of the key who's last in alphabetical order -- not that of the longest key! Rather, you need max(len(k) for k in self.keys()) or the like... Dec 27, 2014 at 2:20
  • ...why do you say so? Keys are integers in this case.
    – Roberto
    Dec 27, 2014 at 2:22
  • If they're all non-negative integers (not just more generically "numbers"), then len(str(max(self.keys()))) does happen to equal max(len(str(k)) for k in self.keys()) [had omitted the str in my previous comment and it's too late to edit]. The latter's more general, the former faster if you do happen to know that all keys are non-negative integers (a common but not universal convention for "employee IDs"). Dec 27, 2014 at 2:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.