Пузырь Сортировать Домашнее Задание

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

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 = false" в тело вашего случая if; удалите свой случай else; и поместите "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 

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

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

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

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

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

нет необходимости в состоянии ли sort Это правда или нет.

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

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

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(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]))

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

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

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 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