How to sort a python list using 2 conditional attributes

Question

Lets say I want to sort a list that looks like this:

arr = ['45621', '78124', '24613']

The above list stores the IDs for various employees at a company. I don't want to sort based on the IDs alone, but based on attributes that correspond to the IDs, using the following dictionary:

employees = {
    '45621' : { 'rating' : 3, 'hours_worked' : 42 },
    '78124' : { 'rating' : 4, 'hours_worked' : 78 },
    '24613' : { 'rating' : 3, 'hours_worked' : 51 }
}

So its something like this: if an employee has a higher rating, his/her ID will come first. However, if 2 employees have the same rating, then we compare the hours_worked, and whoever has worked more will come before the other.

Right now, I am thinking about 2 different sorting methods: insertion, and merge. I edited a few code samples from the web, but I am struggling to compare the second condition, that is, when 2 ratings are equal for the algorithms. For instance, the edited versions of my insertion sort looks like this:

InsertionSort

def insertionSort(arr):
    for i in range(1, len(arr)): 
        key = employees[ arr[i] ]['rating']
        j = i-1
        # Falls apart after this part
        while j >=0 and key < arr[j] : 
            arr[j+1] = arr[j] 
            j -= 1
        arr[j+1] = key 

The merge sort seems even more complex, but I am trying to at least understand one to get an idea.

Any help with these sorting methods will be greatly appreciated. Thanks.

Note: I don't want to use a built in sorting mechanism, as this is mainly for learning, so it is not a duplicate.

Answer 1

You can use python list.sort or sorted based on a custom key:

arr = ['45621', '78124', '24613']

employees = {
    '45621' : { 'rating' : 3, 'hours_worked' : 42 },
    '78124' : { 'rating' : 4, 'hours_worked' : 78 },
    '24613' : { 'rating' : 3, 'hours_worked' : 51 }
}

arr.sort(key=lambda x: (employees[x]["rating"], employees[x]["hours_worked"]))
print(arr)

result:

['45621', '24613', '78124']

Also, since you need the ones with higher ranting first, you should reverse the order.

arr.sort(key=lambda x: (employees[x]["rating"], employees[x]["hours_worked"]), reverse=True)

Here you have a live example

Answer 2

First, I think it's better to organized data into a single list, you don't need 2 of them. Something like this:

employees = [
    {'user_id': '45621', 'rating' : 3, 'hours_worked' : 42 },
    {'user_id': '78124', 'rating' : 4, 'hours_worked' : 78 },
    {'user_id': '24613', 'rating' : 3, 'hours_worked' : 51 }]

after that you can use built-in sort function of list, combine with operator.itemgetter twice with corresponding keys you want.

Let say you value rating over hours_worked, you need to sort by the less important key first. reverse=False to put high value on top.

This way provide you more control, because sometime not both sort are in the same order. i.e: you want to sort rating descending but hours_worked ascending (user with high rating, but less work, mean more efficient)

import operator
employees.sort(key=operator.itemgetter('hours_worked'), reverse=True)
employees.sort(key=operator.itemgetter('rating'), reverse=True)

Result:

[{'user_id': '78124', 'rating': 4, 'hours_worked': 78},
 {'user_id': '24613', 'rating': 3, 'hours_worked': 51},
 {'user_id': '45621', 'rating': 3, 'hours_worked': 42}]

After sorting, you can get the id in order by a list comprehension

[u['user_id'] for u in employees]

Which gives:

['78124', '24613', '45621']

Answer 3

Or sorted:

arr=sorted(arr,key=lambda x: (employees[x]["rating"], employees[x]["hours_worked"]))

If need high to low on sorting:

arr=sorted(arr,key=lambda x: (employees[x]["rating"], employees[x]["hours_worked"]), reverse=True)