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

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

1. большее время
2. большая сложность пространства
3. или делает слишком много, операции

тогда, должен быть

Так, вот мое решение:

def countInversions(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        _count = count
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                count += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if _count == count:
            break
    return count

Ответы, предоставленные the-fury и Мартином Коте, исправили проблему бесконечного цикла, но мой код все равно будет работать некорректно (для большего списка он не будет правильно отсортирован). В итоге я отказался от несортированной переменной и вместо этого использовал счетчик.

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)

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

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

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

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

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

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

Цель пузырьковой сортировки - перемещать более тяжелых элементов внизу в каждом раунде , при перемещении элементов зажигалок вверх. Во внутреннем цикле, где вы сравниваете элементы , вам не нужно перебирать весь список на каждом шаге . Самый тяжелый уже стоит последним. Переменная 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