Блог

Новичок в программировании и алгоритмах. Пробуем самый простой — жевательный сорт. Но, похоже, последнее число не сортируется? Не могу толком понять, почему.

Исходный список выглядит следующим образом — list = [4, 5, 3, 10, 17, 6, 2, 22, 76, 99, 18, 7] но мой вывод выглядит следующим образом — [99, 2, 3, 4, 5, 6, 7, 10, 17, 18, 22, 76]

По какой-то причине 99 не заменяется на задний план, и я не могу точно определить, почему.

 list = [4, 5, 3, 10, 17, 6, 2, 22, 76, 99, 18, 7]

def bblSort(list):
    for i in range(len(list)):
        print(list[i])
        for j in range(len(list) - 1):
            if list[i] <list[j 1]:
                list[i], list[j 1] = list[j 1], list[i]

    print(list)
 

Пузырьковая сортировка может быть реализована с помощью двух циклов for или цикла while и цикла for. Вот реализация, которая использует while и цикл for и ее легче понять.

Эта функция просматривает список с помощью внутреннего цикла for, сравнивает каждый объект с объектом после него и при необходимости меняет их местами. Внешний цикл while гарантирует, что он повторяет цикл for снова и снова по всему списку, пока дальнейшая замена не потребуется.

 def bubble_sort(unsorted_list):
    my_list = list(unsorted_list) # create a copy to avoid mutating the original list
    unsorted = True
    while unsorted:
        unsorted = False
        for i in range (len(my_list)-1):
            if my_list[i] > my_list[i 1]:
                unsorted = True
                my_list[i] , my_list[i 1] = my_list[i 1], my_list[i]
    return my_list

unsorted_list = [5,2,4,90,140,23,554,32,98,12,15,0,43,-34,10]
print(bubble_sort(unsorted_list))
 

С принтами:
[-34, 0, 2, 4, 5, 10, 12, 15, 23, 32, 43, 90, 98, 140, 554]

Вам нужен только один цикл, так как пузырьковая сортировка сравнивает соседние значения. Попробуйте выполнить один цикл с i, а затем просто сравнить list[i] и list[i 1] (следите за концом списка)

Кстати, рекомендуется не вызывать ваши переменные с именами типов, здесь выберите другое имя для переменной ‘list’.

Для сортировки пузырьков вам нужно выполнить несколько проходов по списку, чтобы убедиться, что он отсортирован. Каждый проход гарантированно перемещает наибольшее число в конец сортируемой части списка. Это означает, что вам не нужно снова сортировать эту позицию, поэтому вам нужно только отсортировать до этой позиции на следующем проходе.

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

 bubblesort(list myList)
  for (hi <- myList.length - 1 downto 0) do
    for (lo <- 1 to hi) do
      if (myList[lo - 1] > myList[lo]) then
        swap(myList[lo - 1], myList[lo]) 
      endif
    endfor
  endfor
end bubblesort()
 

Каждый проход сортирует часть списка между началом и hi с hi уменьшением на единицу для каждого прохода.

Для получения дополнительного кредита подумайте о том, как закончить игру раньше, если пас не приводит к каким-либо свопам. В этом случае список уже отсортирован по порядку.

В вашем коде есть несколько проблем, если вашей целью было реализовать пузырьковую сортировку:

• Сортировка пузырьков сравнивает и меняет местами только соседние элементы, поэтому сравнение между lst[j] и lst[j 1] .
• Затем сравнение должно быть соответствующим образом адаптировано к lst[j] > lst[j 1] , что указывает на то, что эти два значения отображаются в неправильном порядке.
• Хотя это и не обязательно для его работы, хороший алгоритм пузырьковой сортировки не будет проверять пары, которые наверняка уже находятся в правильном порядке. Это означает, что внутреннему циклу действительно требуется на одну итерацию меньше при каждом i увеличении времени, поскольку в конце списка будет (растущая) часть, которая уже отсортирована.

Итак:

 def bblSort(lst):
    for i in range(len(lst)):
        for j in range(len(lst) - 1 - i):
            if lst[j] > lst[j 1]:
                lst[j], lst[j 1] = lst[j 1], lst[j]