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



8 Answers

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

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

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

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

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




Ответы, высказанные 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)

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




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



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




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




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



Related