Программа неправильно сортирует самое низкое значение в списке в алгоритме сортировки выбора - PullRequest
Новая
       42

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

0 голосов
/ 09 декабря 2018

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

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

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

Ответы [ 2 ]

0 голосов
/ 09 декабря 2018

Логика алгоритма сортировки выбора (в порядке убывания): перебирать таблицу 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]
0 голосов
/ 09 декабря 2018

Это должно работать.Он также использует 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]
...