Python — проблема с сортировкой вставками

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

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

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


python insertion-sort
person Denise    schedule 06.05.2020    source источник

Ответы (3)


arrow_upward
1
arrow_downward

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

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

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

Вне:

1
2
3
4
5
6
7
8
9

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

из

indexingRange = range(1, len(inventory))

to 

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

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

Вне:

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

arrow_upward
0
arrow_downward

Я бы предложил пару изменений. Поскольку вы эмулируете массив, индексация которого начинается с индекса = 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

person Booboo    schedule 06.05.2020

arrow_upward
0
arrow_downward

На вашем месте я бы попытался использовать другой макет структуры данных, мне не нравится использовать так много [] фрагментов для доступа к элементам в словаре. Функция 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}
person bherbruck    schedule 06.05.2020