How to apply sorting algorithms on a dictionary?

Question

I have a dictionary d as:

d = {3: 'a', 5: 'g', 1: 't', 4: 'y'}

I want to sort it so the result is:

d = {1: 't', 3: 'a', 4: 'y', 5: 'g'}

To get that result, I need to apply a sorting algorithm on the list like insertion sort or selection sort. How can it be implemented?

If you mean you shouldn't use in-built `sorted`, and implement insertion-sort algorithm , iterate through items in the dictionary and compare the keys as you would compare integers in the insertion sort of an integer array. — SomeDude, May 15 '21 at 13:58

Anant Arun · Answer 1 · 2021-05-15T14:45:46.103

If you want to try without using the inbuilt function, below is the example of quicksort:

def quicksort(data, left, right):
    if left+1 >= right:
        return
    ai, bi, ci = left, (left+right)//2, right-1
    a, b, c = data[ai], data[bi], data[ci]
    if a < b:
        if c < a:
            pos = ai
        elif c < b:
            pos = ci
        else:
            pos = bi
    else:
        if c < b:
            pos = bi
        elif c < a:
            pos = ci
        else:
            pos = ai
    pivot = data[pos]
    data[pos] = data[right-1]
    tail = left
    for i in range(left, right-1):
        if data[i] < pivot:
            data[tail], data[i] = data[i], data[tail]
            tail += 1
    data[right-1], data[tail] = data[tail], pivot
    quicksort(data, left, tail)
    quicksort(data, tail+1, right)

mydict = { 'a': 1, 'b': 4, 'c': 9, 'd': 3, 'e': 1 }
values = [value for key, value in mydict.items()]
quicksort(values, 0, len(values))
print(values)

Bubble sort, sorting on item not key here, though not recommended due to runtime complexity of O(n^2):

def order(x, y):    
    if x[1] < y[1]:
        return x, y
    else:
        return y, x

def bubble(mydict):
    d_items = mydict.items()
    for j in range(len(d_items) - 1):
        for i in range(len(d_items) - 1):
            d_items[i], d_items[i+1] = order(d_items[i], d_items[i+1])
    return d_items


mydict = {'a':1, 'b':4, 'c':9, 'd':3, 'e':1}
sorted_tuples = bubble(mydict)
print sorted_tuples  # prints [('a', 1), ('e', 1), ('d', 3), ('b', 4), ('c', 9)]

You just need to iterate through items after creating code for any type of sorting algorithm.

Rivers · Answer 2 · 2021-05-15T14:57:55.650

You want to sort you dict by keys. And if I understand you well, you want to sort them with a sorting algorithm of your choice (not the built-in algorithm).

So you should:

implement your sorting algorithm
apply it on the dict keys
create the new dictionary sorted by keys

Pseudocode:

d = {3: 'a', 5: 'g', 1: 't', 4: 'y'}

# Get the keys as list
d_keys = list(d.keys()) # [3, 5, 1, 4]

# Here, you implement your sorting algorithm on 'd_keys'
# ...
# At the end, you get 'sorted_keys' ('d_keys' sorted): sorted_keys == [1, 3, 4, 5]

# Here you create the new dictionary: (via dictionary comprehension):
sorted_dict = {k:d[k] for k in sorted_keys}

print(sorted_dict)

Output:

d = {1: 't', 3: 'a', 4: 'y', 5: 'g'}

You will find an insertion sort algorithm implementation in Python here: How does Python insertion sort work?

And selection sort here: Selection Sort Python

But if what you're asking for is something like "can I pass my own algorithm to the built-in sorted method", the answer is no. However, sorted allows you you to chose how to compare the elements. You will find more informations about this here: https://docs.python.org/3/howto/sorting.html and Sort a list of lists with a custom compare function and How to use a custom comparison function in Python 3?.

How to apply sorting algorithms on a dictionary?

2 Answers2