Bubble Sortowanie zadań domowych

Na zajęciach zajmujemy się algorytmami sortowania i chociaż dobrze je rozumiem, kiedy o nich mówię i piszę pseudokod, mam problemy z napisaniem dla nich właściwego kodu.

Oto moja próba w Pythonie:

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)

Teraz to (o ile mogę powiedzieć) sortuje poprawnie, ale po zakończeniu po prostu zapętla się w nieskończoność.

W jaki sposób można naprawić ten kod, aby funkcja zakończyła się poprawnie i poprawnie sortuje listę dowolnego (rozsądnego) rozmiaru?

PS Wiem, że tak naprawdę nie powinienem mieć wydruków w funkcji i powinienem mieć zwrot, ale jeszcze tego nie zrobiłem, ponieważ mój kod jeszcze nie działa.

Aby wyjaśnić, dlaczego twój skrypt teraz nie działa, zmienię nazwę zmiennej unsortedna sorted.

Na początku Twoja lista nie jest jeszcze posortowana. Oczywiście, możemy ustawić sortedsię False.

Gdy tylko uruchomimy whilepętlę, zakładamy, że lista jest już posortowana. Pomysł jest taki: gdy tylko znajdziemy dwa elementy, które nie są we właściwej kolejności, sortedwracamy do False. sortedpozostanie True tylko wtedy, gdy nie będzie elementów w złej kolejności .

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.

Istnieją również drobne, drobne problemy, które pomogłyby kodowi być wydajniejszym lub bardziej czytelnym.

• W forpętli używasz zmiennej element. Technicznie elementnie jest elementem; jest to liczba reprezentująca indeks listy. Poza tym jest dość długi. W takich przypadkach wystarczy użyć tymczasowej nazwy zmiennej, na przykład i„indeks”.

  for i in range(0, length):
  

• rangeKomenda może także wziąć tylko jeden argument (nazwie stop). W takim przypadku otrzymasz listę wszystkich liczb całkowitych od 0 do tego argumentu.

  for i in range(length):
  

• Przewodnik po stylach Pythona zaleca, aby nazywać zmienne małymi literami z podkreśleniami. To bardzo drobna dziura w takim małym scenariuszu; bardziej przyzwyczaisz się do tego, co najczęściej przypomina kod w Pythonie.

  def bubble(bad_list):
  

• Aby zamienić wartości dwóch zmiennych, zapisz je jako przypisanie krotki. Prawa strona jest oceniana jako krotka (powiedzmy (badList[i+1], badList[i])jest (3, 5)), a następnie jest przypisywana do dwóch zmiennych po lewej stronie ( (badList[i], badList[i+1])).

  bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]
  

Połącz to wszystko razem, a otrzymasz to:

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

(Nawiasem mówiąc, usunąłem też twoje wydrukowane oświadczenie.)

Celem sortowania bąbelkowego jest przesuwanie cięższych przedmiotów na dole w każdej rundzie, podczas gdy lżejsze elementy w górę. W pętli wewnętrznej, w której porównujesz elementy, nie musisz powtarzać całej listy po każdym kroku . Najcięższym jest już umieszczony na końcu. Zamienione zmienna jest dodatkowa kontrola, dzięki czemu możemy zaznaczyć, że lista jest teraz sortowane i uniknąć kontynuowaniem niepotrzebnych obliczeń.

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

Twoja wersja 1, poprawiona:

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

Tak się dzieje, gdy używasz nazwy zmiennej o negatywnym znaczeniu, musisz odwrócić ich wartości. Poniższe informacje byłyby łatwiejsze do zrozumienia:

sorted = False
while not sorted:
    ...

Z drugiej strony logika algorytmu jest nieco zła. Musisz sprawdzić, czy dwa elementy zostały zamienione podczas pętli for. Oto jak bym to napisał:

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

Twoje użycie zmiennej Unsorted jest nieprawidłowe; chcesz mieć zmienną, która mówi ci, czy zamieniłeś dwa elementy; jeśli już to zrobiłeś, możesz wyjść z pętli, w przeciwnym razie będziesz musiał ponownie wykonać pętlę. Aby naprawić to, co tu masz, po prostu umieść "unsorted = false" w treści swojego if case; usuń swój inny przypadek; i umieść „unsorted = true” przed forpętlą.

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

# Bardzo prosta funkcja, którą można zoptymalizować (oczywiście), zmniejszając przestrzeń problemową drugiej tablicy. Ale ta sama złożoność 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 

Masz tam kilka błędów. Pierwsza jest długa, a druga jest używana przez Ciebie jako nieposortowane (jak stwierdził McWafflestix). Prawdopodobnie zechcesz również zwrócić listę, jeśli zamierzasz ją wydrukować:

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: Masz rację, powyższe jest buggy jak diabli. Moja wina, że ​​nie testowałem więcej przykładów.

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

Jestem świeżo upieczonym początkującym, wczoraj zacząłem czytać o Pythonie. Zainspirowany twoim przykładem stworzyłem coś może bardziej w stylu lat 80-tych, ale mimo wszystko to działa

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)

Problem z oryginalnym algorytmem polega na tym, że gdybyś miał niższą liczbę dalej na liście, nie doprowadziłaby ona do poprawnej posortowanej pozycji. Program musi za każdym razem cofać się do początku, aby zapewnić sortowanie wszystkich liczb.

Uprościłem kod i będzie teraz działał dla dowolnej listy liczb, niezależnie od listy, a nawet jeśli są liczby powtarzające się. Oto kod

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

Prostszy przykład:

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

To po prostu przenosi elementy od 0 do a (w zasadzie wszystkie nieposortowane elementy w tej rundzie) i porównuje je z sąsiednim elementem i dokonuje zamiany, jeśli jest większa niż sąsiedni element. Na koniec rundy sortowany jest ostatni element, a proces przebiega ponownie bez niego, aż wszystkie elementy zostaną posortowane.

Nie ma potrzeby ustalania warunku, czy sortjest prawdziwy, czy nie.

Zauważ, że ten algorytm bierze pod uwagę pozycję liczb tylko podczas zamiany, więc powtarzające się liczby nie wpłyną na to.

PS. Wiem, że minęło bardzo dużo czasu, odkąd opublikowano to pytanie, ale chciałem tylko podzielić się tym pomysłem.

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

arr = [5,4,3,1,6,8,10,9] # array not sorted

for i in range(len(arr)):
    for j in range(i, len(arr)):
        if(arr[i] > arr[j]):
            arr[i], arr[j] = arr[j], arr[i]

            print (arr)

Rozważam dodanie mojego rozwiązania, ponieważ zawsze tutaj jest rozwiązanie

1. większy czas
2. większa złożoność przestrzeni
3. lub wykonywanie zbyt wielu operacji

to powinno być

Oto moje rozwiązanie:

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

Jeśli ktoś jest zainteresowany krótszą implementacją z wykorzystaniem listy:

def bubble_sort(lst: list) -> None:
    [swap_items(lst, i, i+1) for left in range(len(lst)-1, 0, -1) for i in range(left) if lst[i] > lst[i+1]]


def swap_items(lst: list, pos1: int, pos2: int) -> None:
    lst[pos1], lst[pos2] = lst[pos2], lst[pos1]

Oto inna odmiana sortowania bąbelkowego bez forpętli. Zasadniczo rozważają lastIndexz arrayi powoli decrementinggo aż do pierwszego indeksu tablicy.

algorithmBędzie nadal poruszać się po tablicy jak to aż cały karnet jest wykonany bez swapswystępujących.

Bańka jest sortowana w zasadzie, Quadratic Time: O(n²)jeśli chodzi o wydajność.

class BubbleSort: 
  def __init__(self, arr):
    self.arr = arr;

  def bubbleSort(self):
    count = 0;
    lastIndex = len(self.arr) - 1;
    
    while(count < lastIndex):
      if(self.arr[count] > self.arr[count + 1]):
        self.swap(count)  
      count = count + 1;

      if(count == lastIndex):
        count = 0;
        lastIndex = lastIndex - 1;   

  def swap(self, count):
    temp = self.arr[count];
    self.arr[count] = self.arr[count + 1];
    self.arr[count + 1] = temp;
    
arr = [9, 1, 5, 3, 8, 2]
p1 = BubbleSort(arr)

print(p1.bubbleSort())

Odpowiedzi dostarczone przez the-fury i Martina Cote rozwiązały problem nieskończonej pętli, ale mój kod nadal nie działał poprawnie (w przypadku większej listy nie byłby on poprawnie sortowany). Skończyło się na tym, że porzuciłem unsortedzmienną i zamiast tego użyłem licznika.

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)

Gdyby ktoś mógł podać jakieś wskazówki, jak ulepszyć mój kod w komentarzach, byłoby to bardzo wdzięczne.

Spróbuj tego

a = int(input("Enter Limit"))


val = []

for z in range(0,a):
    b = int(input("Enter Number in List"))
    val.append(b)


for y in range(0,len(val)):
   for x in range(0,len(val)-1):
       if val[x]>val[x+1]:
           t = val[x]
           val[x] = val[x+1]
           val[x+1] = t

print(val)

idk, czy to może ci pomóc po 9 latach ... to prosty program do sortowania bąbelkowego

    l=[1,6,3,7,5,9,8,2,4,10]

    for i in range(1,len(l)):
        for j in range (i+1,len(l)):
            if l[i]>l[j]:
                l[i],l[j]=l[j],l[i]

def merge_bubble(arr):
    k = len(arr)
    while k>2:
        for i in range(0,k-1):
            for j in range(0,k-1):
                if arr[j] > arr[j+1]:
                    arr[j],arr[j+1] = arr[j+1],arr[j]

        return arr
        break
    else:
        if arr[0] > arr[1]:
            arr[0],arr[1] = arr[1],arr[0]
        return arr 

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

def bubble_sorted(arr:list):
    while True:
        for i in range(0,len(arr)-1):
            count = 0
            if arr[i] > arr[i+1]:
                count += 1
                arr[i], arr[i+1] = arr[i+1], arr[i]
        if count == 0:
            break
    return arr
arr = [30,20,80,40,50,10,60,70,90]
print(bubble_sorted(arr))
#[20, 30, 40, 50, 10, 60, 70, 80, 90]

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