CODEWITHSUNDEEP
pythondictionary
eskoka
eskoka

Reputation: 97

sort a dictionary without using built-in functions

If I had a dictionary:

mydict = {'a':1, 'b':4, 'c':9, 'd':3, 'e':1}

How can I sort the dictionary by value from largest-smallest with out using built-in methods like sorted?

Upvotes: 1

Views: 6362

Answers (3)

Nir Alfasi
Nir Alfasi

Reputation: 53525

Bubble sort is the easiest to implement:

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

Disclaimer: Since I got a second comment now about this, it seems that SO members have hard feelings for bubble sort. I, personally don't have anything in favor, as well as against, using bubble-sort. That said, it might be worth mentioning that bubble-sort is an inefficient sorting algorithm that has a runtime complexity of O(n^2).

Upvotes: 2

Michael Laszlo
Michael Laszlo

Reputation: 12239

Here is a program that implements quicksort and uses it to sort the dictionary values. This is a recursive, in-place implementation of quicksort.

def quicksort(data, left, right):
    if left+1 >= right:
        return
    tail = left
    for i in range(left, right-1):
        if data[i] < data[right-1]:
            data[tail], data[i] = data[i], data[tail]
            tail += 1
    data[right-1], data[tail] = data[tail], data[right-1]
    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)

The above code uses the last element in the range as the pivot. If you want better performance and you're willing to put up with more code, you can select the pivot element by taking the median of the first, middle, and last values.

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)

Upvotes: 0

kylieCatt
kylieCatt

Reputation: 11039

A very simple quick sort implementation:

def quick(lst):
    if len(lst) < 2:
        return lst
    pivot = lst[0]
    l = quick([x for x in lst[1:] if x < pivot])
    u = quick([x for x in lst[1:] if x >= pivot])
    return l + [pivot] + u

Upvotes: 0

Related Questions