Bubble Sort Домашнее задание

Question

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

Это моя попытка в 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)

Теперь, это (насколько я могу судить) сортирует правильно, но как только оно завершается, оно просто зацикливается бесконечно.

Как исправить этот код, чтобы функция правильно и правильно завершила сортировку списка любого (разумного) размера?

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

Answer 1

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

Сначала ваш список еще не отсортирован. Конечно, мы устанавливаем 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 также может принимать только один аргумент (с именем 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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

# Очень простая функция, которая может быть оптимизирована (очевидно) путем уменьшения проблемного пространства 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 

Answer 7

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

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

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)

Answer 8

Я новичок в свежем виде, начал читать о 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)

Answer 9

У вас там есть пара ошибок. Первый - длиной, а второй - вашим несортированным (как заявлено в 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

Answer 10

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