sort a dictionary without using built-in functions

Question

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?

Dictionaries are unsorted by nature. You can't sort them. You could however use an `collections.OrderedDict` — kylieCatt, Nov 23 '14 at 05:35
How do you want to sort the values if you don't allow yourself to do sorting? It sounds like you really want to do this: `sorted([value for key, value in h.items()])` — Michael Laszlo, Nov 23 '14 at 05:47
@eskoka: Have you written a sort function of any kind? If not, step 1 is to write your own version of `list.sort` or `sorted`. — user2357112, Nov 23 '14 at 05:48
@eskoka, you need to write your own sort function. For how python does it see http://stackoverflow.com/questions/1517347/about-pythons-built-in-sort-method — user3885927, Nov 23 '14 at 05:51
So you want to extract the values from the dictionary and sort them with a function that you've defined yourself? And your end result is a list of the sorted values? — Michael Laszlo, Nov 23 '14 at 05:51
I assume you can't use built-in functions/methods because this is homework. And if so, your classes should have given you enough info to at least get started on writing some kind of sorting function... — PM 2Ring, Nov 23 '14 at 06:26

Nir Alfasi · Answer 1 · 2014-11-23T18:46:06.013

2

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

edited Nov 23 '14 at 18:46

answered Nov 23 '14 at 06:07

Nir Alfasi

53,191
11
86
129

1

Selection sort, or insertion sort if you need a stable sort, are almost as easy to implement, and generally superior to bubble sort. [Knuth said](http://en.wikipedia.org/wiki/Bubble_sort#In_practice): `"the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems"`. [This page](http://cs.lmu.edu/~ray/notes/sorting/) has a nice comparison of various sorting algorithms. – PM 2Ring Nov 23 '14 at 06:21
1

Not particularly; I'm worried about encouraging newbies to use bubble sort when almost any other (sane) sort is generally superior to it. :) But for some reason, it's often the first sorting algorithm new programmers get exposed to, so they tend to use it when they don't have access to a sort function from a library. Sure, it's easy to understand how bubble sort works, but it's pretty easy to explain selection or insertion sort using playing cards. And I bet nobody would ever choose to sort a hand of cards using bubble sort. :) – PM 2Ring Nov 23 '14 at 06:45
@PM2Ring The reason I chose bubble was its simplicity. It's simpler to explain in words than any other sort I know, and the code reflects it. That said, thank you for posting the links, I believe that they'll be valuable for someone that reads this question and wants more context about the different comparison-based sorts. – Nir Alfasi Nov 23 '14 at 08:49
Please do not recommend Bubblesort. Ease of implementation is not a sufficient argument. Do recommend both Quicksort and Heapsort. – Nov 23 '14 at 09:05
@YvesDaoust There is no "argument" here and I did not recommend using bublesort. This question does not deal with sort-recommendations. When I'll answer a question about sort recommendations I'm actually inclined to recommend radix & bucket sort (assuming the input has known-limited range of values of course). Again, the question deals with sorting a dictionary by its values, not about different sorts and their pros/cons. – Nir Alfasi Nov 23 '14 at 09:21
You implicitly recommend it (and even provide an implementation). Rarely a good choice, except sometimes for nearly sorted input. – Nov 23 '14 at 09:54
@Yves I explicitly chose bubble for *this* solution. It is not a good choice if you're looking for efficiency (hence the disclaimer above) and assuming that efficiency is not the issue (since the OP didn't state so) bubble sort is a good sorting algorithm as any other comparison algorithm. – Nir Alfasi Nov 23 '14 at 10:00

Michael Laszlo · Answer 2 · 2014-11-23T08:58:46.370

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)

score 0 · Answer 3 · answered Nov 23 '14 at 06:12

0

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

answered Nov 23 '14 at 06:12

kylieCatt

10,672
5
43
51

sort a dictionary without using built-in functions

3 Answers3

Linked