Пузырь Python не сортирует весь список [дубликат]

def bubbleSort ( arr ):
    swapped = True 
    length = len ( arr )
    j = 0

    while swapped:
        swapped = False
        j += 1 
        for i in range ( length  - j ):
            if arr [ i ] > arr [ i + 1 ]:
                # swap
                tmp = arr [ i ]
                arr [ i ] = arr [ i + 1]
                arr [ i + 1 ] = tmp 

                swapped = True

if __name__ == '__main__':
    # test list
    a = [ 67, 45, 39, -1, -5, -44 ];

    print ( a )
    bubbleSort ( a )
    print ( a )

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

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

def bubblesort(array):
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return(array)

print(bubblesort([3,1,6,2,5,4]))

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

Ответы, предоставленные 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)

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

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

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

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

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

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

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

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)

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

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

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)

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

Более простой пример:

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

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

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

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

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

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