Программа неправильно сортирует наименьшее значение в списке в алгоритме сортировки выбором

Я пишу программу на Python, которая реализует алгоритм сортировки выбором и сортирует элементы списка в порядке убывания.

Допустим, мой ввод l = [242, 18, 44, 201, 1111].

Моя логика такова:

  • l = [242, 18, 44, 201, 1111] # switch l[0] (242) and l[len(l)-1] (1111)
  • l = [1111, 18, 44, 201, 242] # switch l[1] (18) and l[len(l)-1] (242)
  • l = [1111, 242, 44, 201, 18] # switch l[2] (44) and l[len(l)-2] (201)

Результат будет [1111, 242, 201, 44, 18].

Итак, вот код, который я реализую на основе приведенной выше логики:

def selSort(l):
    '''Sorts the list in descending order using a selection sort algorithm.

    Params: l (list): unsorted list
    Sorts: unsorted list in descending order
    '''
    start = len(l)-1
    while start != 0:
        for i in range(len(l)):
            if l[i] < l[start]:
                l[i], l[start] = l[start], l[i]
        start -= 1

Похоже, я переоценил свою логику, потому что алгоритм выдает [1111, 18, 242, 201, 44].

После некоторой отладки я смог обнаружить, что после пары обходов l правильно отсортирован, но цикл while все еще не соответствует условию завершения. Это означает, что между start и i будет нежелательное совпадение. Например, когда start = 3 и i = 4, l[i] < l[start] получается l = [1111, 242, 201, 18, 44]. После дополнительного обхода мы пришли к неверному результату, который я показал выше.

Что было бы элегантным (я знаю, что сортировка выбора - не самый эффективный алгоритм) и Pythonic решением этой проблемы? Я пытаюсь добиться этого без использования каких-либо встроенных функций (за исключением len и range), методов или внешних библиотек (если это возможно).

Я проверил алгоритм сортировки выбором Python и Алгоритм сортировки выбором в Java публикуется здесь, на SO. Первый использует методы списка (которых я стараюсь избегать), и я недостаточно хорошо понимаю синтаксис Java, чтобы использовать последний.


python-3.x python algorithm selection-sort
person new_user_who_this    schedule 09.12.2018    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Это должно работать. Он также использует range(), чтобы избежать использования цикла while.

def selSort(l):
'''Sorts the list in descending order using a selection sort algorithm.

Params: l (list): unsorted list
Sorts: unsorted list in descending order
'''
for i in range(len(l)):

    # Find the largest element in list
    max_index = i
    for j in range(i + 1, len(l)):
        if l[max_index] < l[j]:
            max_index = j

    # Swap the first and max item
    l[i], l[max_index] = l[max_index], l[i]
person Noah B. Johnson    schedule 09.12.2018

arrow_upward
2
arrow_downward

Логика алгоритма сортировки выбора (в порядке убывания): состоит в том, чтобы перебирать таблицу n-1 раз (n - количество элементов в списке). на i-й итерации мы выбираем самый высокий элемент между индексами i+1 и n и меняем этот элемент на элемент в позиции i в списке. Это приводит к следующему коду:

def selSort(l):
    '''Sorts the list in descending order using a selection sort algorithm.

    Params: l (list): unsorted list
    Sorts: unsorted list in descending order
    '''
    for i in range(len(l)-1) :
        posMax = i
        for j in range(i+1,len(l)):
            if l[j] > l[posMax]:
                posMax = j
        l[posMax], l[i] = l[i], l[posMax]
    return l

l = selSort([242, 18, 44, 201, 1111])
print(l) #prints [1111, 242, 201, 44, 18]
person florex    schedule 09.12.2018