Неправильная сортировка пузырьков с использованием рекурсии на срезах;список не заканчивается - PullRequest
Новая
       6

Неправильная сортировка пузырьков с использованием рекурсии на срезах;список не заканчивается

0 голосов
/ 23 ноября 2018 
def bubble_sort(l):
    if len(l) == 1:
      return
    for i in range(len(l) - 1):
        if l[i] > l[i + 1]:
            l[i], l[i + 1 ] = l[i + 1], l[i]
    bubble_sort(l[:-1])

l = [3, 2, 1]
bubble_sort(l)
print(l)

выдает 

[2,1,3]

Я пытаюсь отсортировать список в порядке возрастания с помощью рекурсивной сортировки по пузырькам.Полученный список не отсортирован.Пожалуйста, игнорируйте ошибки отступа, если они найдены.

1 Ответ

0 голосов
/ 23 ноября 2018

Проблема с вашим кодом в том, что в python оператор нарезки возвращает новую копию среза, а не ссылку.То есть, если мы выполним следующие операции 

lst = [1, 2, 3, 4]
slice = lst[2:]
slice[0] = -5
print(lst)

, вы получите [1, 2, 3, 4].Первоначальный список не изменится.Это проблема в вашем коде;когда вы передаете часть списка в функцию рекурсии, вы не сортируете исходный список.Способ преодолеть эту проблему - передать индекс вместо слайсов.Возможное решение может быть следующим: 

from random import shuffle


def bubble_sort(lst, n):
    if n == 1:
        return
    for i in range(n - 1):
        if lst[i] > lst[i+1]:
            lst[i], lst[i+1] = lst[i+1], lst[i]
    bubble_sort(lst, n - 1)


n = 50
x = [i for i in range(50)]
shuffle(x)
bubble_sort(x, n)
print(x)

Мы передаем индекс подсписка для сортировки нашей рекурсивной функции и всегда выполняем операции с исходным списком без срезов.Приведенный выше код должен вывести отсортированный список, как и ожидалось.

...