В классе мы разрабатываем алгоритмы сортировки, и хотя я прекрасно понимаю их, когда говорю о них и пишу псевдокод, у меня возникают проблемы с написанием для них реального кода.
Это моя попытка на Python:
mylist = [12, 5, 13, 8, 9, 65]
def bubble(badList):
length = len(badList) - 1
unsorted = True
while unsorted:
for element in range(0,length):
unsorted = False
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
print badList
else:
unsorted = True
print bubble(mylist)
Теперь это (насколько я могу судить) сортируется правильно, но как только он завершается, он просто бесконечно зацикливается.
Как можно исправить этот код, чтобы функция правильно завершила свою работу и правильно отсортировала список любого (разумного) размера?
PS Я знаю, что у меня не должно быть отпечатков в функции, и у меня должен быть возврат, но я просто еще не сделал этого, так как мой код еще не работает.
python
algorithm
sorting
bubble-sort
Джош Хант
источник
источник
Ответы:
Чтобы объяснить, почему ваш скрипт сейчас не работает, я переименую переменную
unsorted
вsorted
.Сначала ваш список еще не отсортирован. Конечно, мы устанавливаем
sorted
вFalse
.Как только мы запускаем
while
цикл, мы предполагаем, что список уже отсортирован. Идея такова: как только мы обнаруживаем два элемента, которые расположены не в правильном порядке, мыsorted
возвращаемся к нимFalse
.sorted
останетсяTrue
только в том случае, если не было элементов в неправильном порядке .Есть также мелкие мелкие проблемы, которые могут помочь сделать код более эффективным или читаемым.
В
for
цикле вы используете переменнуюelement
. Техническиelement
это не элемент; это число, представляющее индекс списка. Кроме того, это довольно долго. В этих случаях просто используйте имя временной переменной, например,i
для «index».Команда
range
также может принимать только один аргумент (с именемstop
). В этом случае вы получите список всех целых чисел от 0 до этого аргумента.Руководство по стилю Python рекомендует называть переменные строчными буквами с подчеркиванием. Это очень незначительная придирка для такого маленького сценария; это больше для того, чтобы вы привыкли к тому, на что чаще всего похож код Python.
Чтобы поменять местами значения двух переменных, запишите их как присвоение кортежа. Правая часть оценивается как кортеж (скажем,
(badList[i+1], badList[i])
есть(3, 5)
), а затем присваивается двум переменным в левой части ((badList[i], badList[i+1])
).Сложите все вместе, и вы получите следующее:
(Кстати, я удалил и ваше выражение для печати.)
источник
while
цикла самый большой элемент «всплывает» в конец списка. Таким образом, после одной итерации последний элемент определенно находится в нужном месте (и не будет перемещен при последующих итерациях). Вычитая 1 из длины, вы оптимизируете алгоритм, сортируя только подсписок, который еще не отсортирован (самыеlength-n
передние элементы списка). Я решил пропустить эту оптимизацию, поскольку это скорее оптимизация, чем жизненно важная часть алгоритма.Put it all together, and you get this:
... ну, вы пропустили это:The range command can also take just one argument (named stop).
Цель пузырьковой сортировки - перемещать более тяжелые предметы внизу в каждом раунде, а более легкие перемещать вверх. Во внутреннем цикле, где вы сравниваете элементы, вам не нужно перебирать весь список на каждом шагу . Самый тяжелый уже ставится последним. Местами переменная является дополнительная проверка , поэтому мы можем отметить , что список теперь сортируется и избежать продолжения ненужных вычислений.
Ваша версия 1, исправлено:
источник
Вот что происходит, когда вы используете имя переменной с отрицательным значением, вам нужно инвертировать их значения. Было бы легче понять следующее:
С другой стороны, логика алгоритма немного неверна. Вам нужно проверить, поменялись ли два элемента местами во время цикла for. Вот как бы я это написал:
источник
Вы неправильно используете переменную Unsorted; вы хотите иметь переменную, которая сообщает вам, поменяли ли вы местами два элемента; если вы это сделали, вы можете выйти из цикла, в противном случае вам нужно будет снова выполнить цикл. Чтобы исправить то, что у вас здесь, просто поместите "unsorted = false" в тело вашего if case; удалите свой else case; и поместите "unsorted = true" перед вашим
for
циклом.источник
источник
# Очень простая функция, которую можно оптимизировать (очевидно), уменьшив проблемное пространство 2-го массива. Но такая же сложность O (n ^ 2).
источник
arr[a], arr[b] = arr[b], arr[a]
У вас там пара ошибок. Первый - по длине, а второй - в использовании вами несортированного (как указано McWafflestix). Вы, вероятно, также захотите вернуть список, если собираетесь его распечатать:
eta: Вы правы, это чертовски глючит. Плохо, что я не тестировал еще несколько примеров.
источник
Я свежий новичок, вчера начал читать о Python. Вдохновленный вашим примером, я создал что-то, может быть, больше в стиле 80-х, но тем не менее это вроде работает.
источник
Проблема с исходным алгоритмом заключается в том, что если бы у вас было меньшее число дальше в списке, он не смог бы привести его в правильную отсортированную позицию. Программе необходимо каждый раз возвращаться к началу, чтобы гарантировать, что числа отсортированы до конца.
Я упростил код, и теперь он будет работать для любого списка чисел, независимо от списка, и даже если есть повторяющиеся числа. Вот код
источник
источник
alist = [54,26,93,17,77,31,44,55,20, -23, -34,16,11,11,11]
печать пузырьков (список)
источник
источник
Более простой пример:
Это просто берет элементы от 0 до a (в основном, все несортированные элементы в этом раунде) и сравнивает их с соседним элементом, и выполняет замену, если он больше, чем его соседний элемент. В конце раунда последний элемент сортируется, и процесс снова запускается без него, пока не будут отсортированы все элементы.
Нет необходимости в условии, что
sort
истинно оно или нет.Обратите внимание, что этот алгоритм учитывает положение чисел только при замене местами, поэтому повторяющиеся числа не повлияют на него.
PS. Я знаю, что этот вопрос был опубликован очень давно, но я просто хотел поделиться этой идеей.
источник
источник
источник
источник
источник
Я рассматриваю возможность добавления своего решения, потому что любое решение здесь имеет
тогда должно быть
Итак, вот мое решение:
источник
Если кого-то интересует более короткая реализация с использованием списка:
источник
Вот другой вариант пузырьковой сортировки без
for
петли. В основном вы рассматриваетеlastIndex
изarray
и медленноdecrementing
, пока она первый индекс массива.Он
algorithm
будет продолжать движение по массиву таким образом, пока не будет выполнен весь проход без каких-либоswaps
происшествий.Пузырь в основном проявляется,
Quadratic Time: O(n²)
когда дело доходит до производительности.источник
Ответы, предоставленные the-fury и Мартином Коте, устранили проблему бесконечного цикла, но мой код по-прежнему работал некорректно (для большего списка он не сортировался бы правильно). В итоге я отказался от
unsorted
переменной и вместо этого использовал счетчик.Если бы кто-нибудь мог указать в комментариях, как улучшить мой код, я был бы очень признателен.
источник
Попробуй это
источник
idk, если это может помочь вам через 9 лет ... это простая программа пузырьковой сортировки
источник
источник
источник
источник
def bubbleSort(a): def swap(x, y): temp = a[x] a[x] = a[y] a[y] = temp #outer loop for j in range(len(a)): #slicing to the center, inner loop, python style for i in range(j, len(a) - j):
#find the min index and swap if a[i] < a[j]: swap(j, i) #find the max index and swap if a[i] > a[len(a) - j - 1]: swap(len(a) - j - 1, i) return a
источник