Python – Sort Dictionary key and values List

Sometimes, while working with Python dictionaries, we can have a problem in which we need to perform the sorting of it, wrt keys, but also can have a variation in which we need to perform a sort on its values list as well. Let’s discuss certain way in which this task can be performed.

Input : test_dict = {‘c’: [3], ‘b’: [12, 10], ‘a’: [19, 4]} 
Output : {‘a’: [4, 19], ‘b’: [10, 12], ‘c’: [3]} 

Input : test_dict = {‘c’: [10, 34, 3]} 
Output : {‘c’: [3, 10, 34]}

Sort Dictionary key and values List Using sorted() + loop

The combination of above functions can be used to solve this problem. In this, we initially sort all the values of keys, and then perform the keys sorting after that, in brute manner. 

Output : 

The original dictionary is : {‘gfg’: [7, 6, 3], ‘is’: [2, 10, 3], ‘best’: [19, 4]} The sorted dictionary : {‘best’: [4, 19], ‘gfg’: [3, 6, 7], ‘is’: [2, 3, 10]}

Time Complexity: O(nlogn)
Auxiliary Space: O(n)

Sort Dictionary key and values List Using dictionary comprehension + sorted()

The combination of above functions can be used to solve this problem. In this, we perform the task of dual sorting inside dictionary comprehension construct. 

Output : 

The original dictionary is : {‘gfg’: [7, 6, 3], ‘is’: [2, 10, 3], ‘best’: [19, 4]} The sorted dictionary : {‘best’: [4, 19], ‘gfg’: [3, 6, 7], ‘is’: [2, 3, 10]}

Time complexity: O(n log n), where n is the total number of values in the input dictionary test_dict. 
Auxiliary space: O(n), where n is the total number of values in the input dictionary test_dict. 

Sort Dictionary key and values List Using lambda function with sorted()

Sorts a dictionary by its keys and also sorts the values for each key using the sorted() function with a lambda function as the key. initializes a dictionary with some key-value pairs, sorts it, and then prints both the original and sorted dictionaries.

The original dictionary is: {'gfg': [7, 6, 3], 'is': [2, 10, 3], 'best': [19, 4]}
The sorted dictionary: {'best': [4, 19], 'gfg': [3, 6, 7], 'is': [2, 3, 10]}

Time complexity: O(n log n), where n is the number of keys in the dictionary.
Auxiliary space: O(n), where n is the number of keys in the dictionary.

Sort Dictionary key and values List Using the zip() function with sorted() function.

Step-by-step approach:

• Initialize the dictionary.
• Get the list of keys and values separately.
• Use the zip() function to create a list of tuples, where each tuple contains a key and its corresponding value list.
• Sort the list of tuples using the sorted() function and a lambda function that sorts the tuples based on the first element of each tuple (i.e., the key).
• Use a dictionary comprehension to create a new dictionary from the sorted list of tuples.
• Print the sorted dictionary.

Below is the implementation of the above approach:

The original dictionary is: {'gfg': [7, 6, 3], 'is': [2, 10, 3], 'best': [19, 4]}
The sorted dictionary: {'best': [4, 19], 'gfg': [3, 6, 7], 'is': [2, 3, 10]}

Time complexity: O(n log n) due to sorting, where n is the number of keys in the dictionary.
Auxiliary space: O(n) because we are using additional space to store the list of tuples.

Sort Dictionary key and values List Using Recursive method.

Algorithm:

1. Base Case: If the input dictionary is empty, return an empty dictionary.
2. Recursive Case: Find the key with the minimum value list length in the input dictionary. Call it min_key.
3. Sort the value list associated with min_key.
4. Remove min_key from the input dictionary and call the resulting dictionary rest_dict.
5. Recursively call sort_dict_recursive on rest_dict and call the resulting dictionary sorted_rest_dict.
6. Return a new dictionary with min_key as the key and the sorted value list as the value, merged with sorted_rest_dict.

The original dictionary is: {'gfg': [7, 6, 3], 'is': [2, 10, 3], 'best': [19, 4]}
The sorted dictionary : {'best': [4, 19], 'gfg': [3, 6, 7], 'is': [2, 3, 10]}

Time Complexity: O(n log n) – The function makes n recursive calls, and each call sorts a list of length m, where m is the length of the smallest values list in the remaining dictionary. Sorting a list has a time complexity of O(m log m), so the overall time complexity is dominated by the sorting operations, which gives us O(n log n).
Auxiliary Space: O(n) – The recursive function creates a new dictionary and list for each recursive call, so the space complexity is proportional to the size of the input dictionary. In the worst case, where all values lists are of equal length, the size of the output dictionary is the same as the size of the input dictionary, so the space complexity is O(n).

manjeet_04

Follow

Improve