Bubble Сортировать домашние задания

В классе мы выполняем алгоритмы сортировки и, хотя я прекрасно их понимаю, когда говорю о них и пишу псевдокод, у меня возникают проблемы с написанием реального кода для них.

Это моя попытка в 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 Я знаю, что на самом деле у меня не должно быть отпечатков в функции, и у меня должно получиться возвращение, но я просто еще этого не сделал, так как мой код еще не работает.

    15 Solutions collect form web for “Bubble Сортировать домашние задания”

    Чтобы объяснить, почему ваш скрипт не работает прямо сейчас, я переименую переменную unsorted для sorted .

    Сначала ваш список еще не отсортирован. Конечно, мы настроили False .

    Как только мы начнем цикл while, мы предположим, что список уже отсортирован. Идея такова: как только мы найдем два элемента, которые находятся не в правильном порядке, мы sorted обратно в False . sorted останется True только если в неправильном порядке не было элементов .

     sorted = False # We haven't started sorting yet while not sorted: sorted = True # Assume the list is now sorted for element in range(0, length): if badList[element] > badList[element + 1]: sorted = False # We found two elements in the wrong order hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold # We went through the whole list. At this point, if there were no elements # in the wrong order, sorted is still True. Otherwise, it's false, and the # while loop executes again. 

    Есть также незначительные проблемы, которые помогут коду быть более эффективным или читаемым.

    • В цикле for вы используете переменный element . Технически element не является элементом; это число, представляющее индекс списка. Кроме того, это довольно долго. В этих случаях просто используйте временное имя переменной, например i для «index».

       for i in range(0, length): 
    • Команда range также может принимать только один аргумент (named stop ). В этом случае вы получите список всех целых чисел от 0 до этого аргумента.

       for i in range(length): 
    • Руководство по стилю Python рекомендует, чтобы переменные назывались в нижнем регистре с символами подчеркивания. Это очень незначительная нить для маленького скрипта, подобного этому; это больше, чтобы вы привыкли к тому, что код Python чаще всего напоминает.

       def bubble(bad_list): 
    • Чтобы поменять значения двух переменных, напишите их как назначение кортежа. Правая часть оценивается как кортеж (скажем, (badList[i+1], badList[i]) есть (3, 5) ), а затем присваивается двум переменным в левой части ( (badList[i], badList[i+1]) ).

       bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i] 

    Поместите все это вместе, и вы получите следующее:

     my_list = [12, 5, 13, 8, 9, 65] def bubble(bad_list): length = len(bad_list) - 1 sorted = False while not sorted: sorted = True for i in range(length): if bad_list[i] > bad_list[i+1]: sorted = False bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i] bubble(my_list) print my_list 

    (Кстати, я тоже удалил ваше заявление о печати).

    Цель создания пузырьков состоит в том, чтобы перемещать более тяжелые предметы в нижней части каждого раунда, перемещая более светлые предметы вверх. Во внутреннем цикле, где вы сравниваете элементы, вам не нужно перебирать весь список за каждый ход . Самый тяжелый уже размещен последним. Измененная переменная является дополнительной проверкой, поэтому мы можем отметить, что список теперь отсортирован и не позволяет выполнять ненужные вычисления.

     def bubble(badList): length = len(badList) for i in range(0,length): swapped = False for element in range(0, length-i-1): if badList[element] > badList[element + 1]: hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold swapped = True if not swapped: break return badList 

    Ваша версия 1 исправлена:

     def bubble(badList): length = len(badList) - 1 unsorted = True while unsorted: unsorted = False 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 unsorted = True #print badList #else: #unsorted = True return badList 

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

     sorted = False while not sorted: ... 

    С другой стороны, логика алгоритма немного разряжена. Вам нужно проверить, менялись ли два элемента во время цикла for. Вот как я написал бы это:

     def bubble(values): length = len(values) - 1 sorted = False while not sorted: sorted = True for element in range(0,length): if values[element] > values[element + 1]: hold = values[element + 1] values[element + 1] = values[element] values[element] = hold sorted = False return values 

    Неправильное использование переменной Unsorted; вы хотите иметь переменную, которая сообщает вам, если вы заменили два элемента; если вы это сделали, вы можете выйти из цикла, иначе вам нужно снова зациклиться. Чтобы исправить то, что у вас здесь, просто поместите «unsorted = false» в тело вашего случая if; удалите свой другой случай; и поставьте «unsorted = true» перед циклом for .

     def bubble_sort(l): for passes_left in range(len(l)-1, 0, -1): for index in range(passes_left): if l[index] < l[index + 1]: l[index], l[index + 1] = l[index + 1], l[index] return l 

    # Очень простая функция, может быть оптимизирована (очевидно) путем уменьшения проблемного пространства 2-го массива. Но такая же O (n ^ 2) сложность.

     def bubble(arr): l = len(arr) for a in range(l): for b in range(l-1): if (arr[a] < arr[b]): arr[a], arr[b] = arr[b], arr[a] return arr 

    У вас есть пара ошибок. Первый – в длине, а второй – в использовании unsorted (как указано McWafflestix). Возможно, вам также захочется вернуть список, если вы собираетесь его распечатать:

     mylist = [12, 5, 13, 8, 9, 65] def bubble(badList): length = len(badList) - 2 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 unsorted = True return badList print bubble(mylist) 

    eta: Вы правы, выше это багги, как черт. Мне плохо, потому что я не тестировал несколько примеров.

     def bubble2(badList): swapped = True length = len(badList) - 2 while swapped: swapped = False for i in range(0, length): if badList[i] > badList[i + 1]: # swap hold = badList[i + 1] badList[i + 1] = badList[i] badList[i] = hold swapped = True return badList 

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

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

     mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2] print mylist def bubble(badList): length = len(badList) - 1 element = 0 while element < length: if badList[element] > badList[element + 1]: hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold element = 0 print badList else: element = element + 1 print bubble(mylist) 
     def bubble_sort(l): exchanged = True iteration = 0 n = len(l) while(exchanged): iteration += 1 exchanged = False # Move the largest element to the end of the list for i in range(n-1): if l[i] > l[i+1]: exchanged = True l[i], l[i+1] = l[i+1], l[i] n -= 1 # Largest element already towards the end print 'Iterations: %s' %(iteration) return l в def bubble_sort(l): exchanged = True iteration = 0 n = len(l) while(exchanged): iteration += 1 exchanged = False # Move the largest element to the end of the list for i in range(n-1): if l[i] > l[i+1]: exchanged = True l[i], l[i+1] = l[i+1], l[i] n -= 1 # Largest element already towards the end print 'Iterations: %s' %(iteration) return l 
     def bubbleSort(alist): if len(alist) <= 1: return alist for i in range(0,len(alist)): print "i is :%d",i for j in range(0,i): print "j is:%d",j print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j]) if alist[i] > alist[j]: alist[i],alist[j] = alist[j],alist[i] return alist 

    alist = [54,26,93,17,77,31,44,55,20, -23, -34,16,11,11,11]

    print bubbleSort (alist)

     def bubble_sort(a): t = 0 sorted = False # sorted = False because we have not began to sort while not sorted: sorted = True # Assume sorted = True first, it will switch only there is any change for key in range(1,len(a)): if a[key-1] > a[key]: sorted = False t = a[key-1]; a[key-1] = a[key]; a[key] = t; print a 

    Простой пример:

     a = len(alist)-1 while a > 0: for b in range(0,a): #compare with the adjacent element if alist[b]>=alist[b+1]: #swap both elements alist[b], alist[b+1] = alist[b+1], alist[b] a-=1 

    Это просто берет элементы от 0 до (в основном, всех несортированных элементов в этом раунде) и сравнивает их со своим смежным элементом и делает обмен, если он больше, чем его соседний элемент. В конце раунда последний элемент сортируется, и процесс запускается без него, пока все элементы не будут отсортированы.

    Нет необходимости в условии, является ли sort истинным или нет.

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

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

    Я свежий новичок, начал читать о Python вчера. Вдохновленный вашим примером, я создал что-то, возможно, больше в стиле 80-х, но, тем не менее, он работает

     lista1 = [12, 5, 13, 8, 9, 65] i=0 while i < len(lista1)-1: if lista1[i] > lista1[i+1]: x = lista1[i] lista1[i] = lista1[i+1] lista1[i+1] = x i=0 continue else: i+=1 print(lista1) 
     def bubble_sort(li): l = len(li) tmp = None sorted_l = sorted(li) while (li != sorted_l): for ele in range(0,l-1): if li[ele] > li[ele+1]: tmp = li[ele+1] li[ele+1] = li [ele] li[ele] = tmp return li 

    Ответы, высказанные the-fury и Martin Cote, фиксировали проблему бесконечного цикла, но мой код все равно не работал бы корректно (для большего списка он не будет правильно сортироваться.). Я закончил тем, что отбросил unsorted переменную и вместо этого использовал счетчик.

     def bubble(badList): length = len(badList) - 1 n = 0 while n < len(badList): for element in range(0,length): if badList[element] > badList[element + 1]: hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold n = 0 else: n += 1 return badList if __name__ == '__main__': mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99] print bubble(mylist) 

    Если бы кто-нибудь мог указать какие-то указания на то, как улучшить код в комментариях, это было бы очень признательно.

     
    Interesting Posts for Van-Lav

    Как удаленно выполнить процесс с помощью python

    Как загрузить python из командной строки?

    pandas dataframe groupby: сумма / подсчет только положительных чисел

    ImportError: нет модуля с именем «matplotlib» – использование среды Contacflow Anaconda

    Мой каждый код python дает NZEC в SPOJ

    Выполните проверку WebDriverWait () или аналогичную проверку регулярного выражения в Python

    Каковы параметры URL? (элемент в позиции № 3 по результату urlparse)

    Как преобразовать список Python в массив C с помощью ctypes?

    Python / Suds: Тип не найден: 'xs: complexType'

    Используйте OpenPyXL для итерации по листам и ячейкам и обновления ячеек с континенацией строки

    Модуль тестирования приложения python, использующего библиотеку запросов

    Escape входные данные для postgres

    Невозможно предоставить пользователю вход в консоль PyDev на Eclipse с помощью Jython

    Сравнение скорости с Project Euler: C против Python против Erlang vs Haskell

    зачем использовать os.path.join над конкатенацией строк

    Python - лучший язык программирования в мире.