Python – Sort Dictionary by key-value Summation

Given a Dictionary, sort by summation of key and value. 

Input : test_dict = {3:5, 1:3, 4:6, 2:7, 8:1} 
Output : {1: 3, 3: 5, 2: 7, 8: 1, 4: 6} 
Explanation : 4 < 8 < 9 = 9 < 10 are increasing summation of keys and values.

Input : test_dict = {3:5, 1:3, 4:6, 2:7} 
Output : {1: 3, 3: 5, 2: 7, 4: 6} 
Explanation : 4 < 8 < 9 < 10 are increasing summation of keys and values. 

Method 1: Using sorted() + lambda + items()

In this sort operation is performed using sorted(), lambda function is used to provide additional logic. The items() is used to get both keys and values.

Output:

The original dictionary is : {3: 5, 1: 3, 4: 6, 2: 7, 8: 1}
The sorted result : {1: 3, 3: 5, 2: 7, 8: 1, 4: 6}

Time Complexity: O(n*nlogn), where n is the length of the list test_dict
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list

Method 2: Using dictionary comprehension and sorted() function

Use dictionary comprehension to create a new dictionary with sorted key-value pairs. Sort the dictionary items using the lambda function which returns the sum of key-value pairs. Finally, use sorted() method to sort the dictionary items based on the lambda function result.

The original dictionary is : {3: 5, 1: 3, 4: 6, 2: 7, 8: 1}
The sorted result : {1: 3, 3: 5, 2: 7, 8: 1, 4: 6}

Time complexity: O(n log n), where n is the number of items in the dictionary. This is because sorting the dictionary items takes O(n log n) time complexity.
Auxiliary space: O(n), where n is the number of items in the dictionary. This is because we create a new dictionary with the same number of items as the original dictionary.

Method 3: Using the sum of its keys and values (Naive Approach)

1. Initialize the dictionary.
2. Create a list of tuples containing (key+value, key, value) instead of (key, value) pairs.
3. Sort the list based on the first element of the tuple (i.e. the sum of the key and value) using the sorted() function.
4. Create a new dictionary by iterating through the sorted list of tuples and adding each (key, value) pair to a new dictionary.

The original dictionary is : {3: 5, 1: 3, 4: 6, 2: 7, 8: 1}
The sorted result : {1: 3, 3: 5, 2: 7, 8: 1, 4: 6}

Time complexity: O(n logn)

Method 4: Using list comprehension + for loop

Approach:

1. Initialize the dictionary test_dict.
2. Print the original dictionary.
3. Create a list list of tuples (key, value, key+value) using a list comprehension.
4. Sort the list lst by key+value summation using the sorted() function and a lambda function that returns the third element of each tuple.
5. Create a new dictionary res from the sorted list using dictionary comprehension.
6. Print the sorted dictionary.

The original dictionary is : {3: 5, 1: 3, 4: 6, 2: 7, 8: 1}
The sorted result : {1: 3, 3: 5, 2: 7, 8: 1, 4: 6}

Time complexity: O(n log n) due to the use of the sorted() function.
Auxiliary space: O(n) for the list.