Python - ошибка сортировки при вставке

Question

Привет Итак, у меня есть такой словарь

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

Я пытаюсь отсортировать его по a[key][1], которое является числами в списке, используя Insertion Sort Algorithm.

Вот мой код для сортировки вставкой:

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

Однако, когда я запускаю этот код, все but the last элементы в словаре сортируются.

Итак, мой результат выглядит следующим образом:

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

Понятия не имею, что делаю не так. Я почти уверен, что это проблема с индексированием, но я не могу ее решить. Может кто-нибудь поможет, пожалуйста. Спасибо!

Answer 1

Давайте пренебрежем эффективностью, которая, похоже, не является тем, что вы здесь ищете, python имеет нулевой индекс, что означает, что range(1, len(inventory) для len(inventory) в этом случае равно 7, итерация останавливается на 6, а не на 7. В другом случае слова:

попробуйте запустить это:

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

Out:

1
2
3
4
5
6
7
8
9

Поэтому измените эту строку:

from

indexingRange = range(1, len(inventory))

на

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

устраняет проблему:

Выход:

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

Answer 2

Я бы попытался использовать другой макет структуры данных, если бы я был вами, мне не нравится использовать так много [] срезов для доступа к элементам в словаре. Отличная функция sorted:

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)

Вывод:

[{'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}]

Или ваш макет:

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

Вывод:

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

Answer 3

Я бы предложил пару изменений. Поскольку вы эмулируете массив, индексирование которого начинается с index = 1, вам необходимо изменить спецификацию диапазона. Кроме того, изменив порядок проверки в операторе while, вам никогда не придется беспокоиться об исключении KeyError:

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

Выводит:

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

Python Демо