Python - Insertion Sort Issue

Question

Hi So I have a dictionary like this

a = {1 : ["", 4],
     2 : ["", 2],
     3 : ["", 8],
     4 : ["", 1],
     5 : ["", 20],
     6 : ["", 3],
     7 : ["", 2]}

I'm trying to sort this by a[key][1] which is the numbers in the list using the Insertion Sort Algorithm.

Here is my code for the Insertion Sort:

def insertionSort(inventory):
    indexingRange = range(1, len(inventory))

    for i in indexingRange:
        x = inventory[i][1]

        try:
            while inventory[i-1][1] > x and i > 0:
                inventory[i-1], inventory[i] = inventory[i], inventory[i-1]
                i = i - 1
        except KeyError:
            pass

    return inventory

However when I run this code, everything but the last element in the dictionary gets sorted.

So my output becomes like this:

{1: ['', 1], 
2: ['', 2], 
3: ['', 3], 
4: ['', 4], 
5: ['', 8], 
6: ['', 20], 
7: ['', 2]}

I have no idea what i'm doing wrong. I'm pretty sure it's an indexing issue but I can't seem to solve it. Can someone help out please. Thanks!

Answer 1

I would try to use a different data structure layout if I were you, I don't like using so many [] slices to access items in a dictionary. The sorted function is great:

a_list = [{'name': 'item1', 'value': 4},
          {'name': 'item2', 'value': 2},
          {'name': 'item3', 'value': 8},
          {'name': 'item4', 'value': 1},
          {'name': 'item5', 'value': 20},
          {'name': 'item6', 'value': 3},
          {'name': 'item7', 'value': 2},
          {'name': 'item8', 'value': 40},
          {'name': 'item9', 'value': 7}]

a_list_sorted = sorted(a_list, key=lambda x: x['value'])

print(a_list_sorted)

Output:

[{'name': 'item4', 'value': 1}, {'name': 'item2', 'value': 2}, {'name': 'item7', 'value': 2}, {'name': 'item6', 'value': 3}, {'name': 'item1', 'value': 4}, {'name': 'item9', 'value': 7}, {'name': 'item3', 'value': 8}, {'name': 'item5', 'value': 20}, {'name': 'item8', 'value': 40}]

Or your layout:

# your dictionary
a = {1 : ['item1', 4],
     2 : ['item2', 2],
     3 : ['item3', 8],
     4 : ['item4', 1],
     5 : ['item5', 20],
     6 : ['item6', 3],
     7 : ['item7', 2]}

# convert to a dict like: {'': 4, '': }
a_dict = {value[0]: value[1] for value in a.values()}

a_dict_sorted = dict(sorted(a_dict.items(), key=lambda x: x[0]))

print(a_dict_sorted)

Output:

{'item4': 1, 'item2': 2, 'item7': 2, 'item6': 3, 'item1': 4, 'item3': 8, 'item5': 20}

Answer 2

I would suggest a couple of changes. Since you are emulating an array whose indexing starts from index = 1, you need to change your range specification. Also, by changing the order of checking in your while statement, you should never have to worry about having a KeyError exception:

def insertionSort(inventory):
    indexingRange = range(2, len(inventory) + 1) # 2 .. len(inventory) + 1

    for i in indexingRange:
        x = inventory[i][1]

        while i > 1 and inventory[i-1][1] > x: # check i value first and compare with 1
            inventory[i-1], inventory[i] = inventory[i], inventory[i-1]
            i = i - 1
    return inventory

print(insertionSort(
    {1: ['', 1],
    2: ['', 2],
    3: ['', 3],
    4: ['', 4],
    5: ['', 8],
    6: ['', 20],
    7: ['', 2]}
    )
)

Prints:

{1: ['', 1], 2: ['', 2], 3: ['', 2], 4: ['', 3], 5: ['', 4], 6: ['', 8], 7: ['', 20]}

Python Demo

Answer 3

Let's neglect efficiency which does not seem to be what you're looking for here, python is zero indexed which means range(1, len(inventory) for len(inventory) being 7 in this case, iteration stops at 6 not 7. In other words:

try running this:

for i in range(1, 10):
    print(i)

Out:

1
2
3
4
5
6
7
8
9

Therefore changing this line:

from

indexingRange = range(1, len(inventory))

to

indexingRange = range(1, len(inventory) + 1)

fixes the problem:

Out:

{1: ['', 1], 2: ['', 2], 3: ['', 2], 4: ['', 3], 5: ['', 4], 6: ['', 8], 7: ['', 20]}