webentwicklung-frage-antwort-db.com.de

Bubble Sort Hausaufgaben

Im Unterricht machen wir Sortieralgorithmen und obwohl ich sie gut verstehe, wenn ich darüber spreche und Pseudocode schreibe, habe ich Probleme, Code zu schreiben.

Dies ist mein Versuch in 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)

Nun, dies wird (soweit ich das beurteilen kann) korrekt sortiert, aber wenn es fertig ist, wird es einfach endlos wiederholt.

Wie kann dieser Code korrigiert werden, damit die Funktion ordnungsgemäß beendet wird und eine Liste mit (angemessener) Größe sortiert wird?

P.S. Ich weiß, ich sollte eigentlich keine Abzüge in einer Funktion haben und ich sollte eine Rückgabe haben, aber ich habe das noch nicht getan, da mein Code noch nicht wirklich funktioniert.

128
Josh Hunt

Um zu erklären, warum Ihr Skript momentan nicht funktioniert, benenne ich die Variable unsorted in sorted um.

Zunächst ist Ihre Liste noch nicht sortiert. Natürlich setzen wir sorted auf False.

Sobald wir die while-Schleife starten, gehen wir davon aus, dass die Liste bereits sortiert ist. Die Idee ist folgende: Sobald wir zwei Elemente finden, die nicht in der richtigen Reihenfolge sind, setzen wir sorted zurück auf False. sorted bleibt Truenur dann, wenn keine Elemente in der falschen Reihenfolge vorhanden sind.

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.

Es gibt auch kleinere Probleme, die dazu beitragen, dass der Code effizienter oder lesbarer wird.

  • In der for-Schleife verwenden Sie die Variable element. Technisch gesehen ist element kein Element; Es ist eine Zahl, die einen Listenindex darstellt. Es ist auch ziemlich lang. Verwenden Sie in diesen Fällen einfach einen temporären Variablennamen, wie i für "Index".

    for i in range(0, length):
    
  • Der Befehl range kann auch nur ein Argument (mit dem Namen stop) enthalten. In diesem Fall erhalten Sie eine Liste aller ganzen Zahlen von 0 bis zu diesem Argument.

    for i in range(length):
    
  • Der Python Style Guide empfiehlt, dass Variablen mit Unterstrich in Kleinbuchstaben benannt werden. Dies ist ein sehr kleiner Nitpick für ein kleines Skript wie dieses; Es ist mehr, Sie daran zu gewöhnen, was Python-Code am häufigsten ähnelt.

    def bubble(bad_list):
    
  • Um die Werte von zwei Variablen auszutauschen, schreiben Sie sie als Tuple-Zuweisung. Die rechte Seite wird als Tupel ausgewertet (beispielsweise (badList[i+1], badList[i]) ist (3, 5)) und wird dann den beiden Variablen auf der linken Seite ((badList[i], badList[i+1])) zugewiesen.

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

Alles zusammen und du bekommst folgendes:

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

(Ich habe übrigens auch Ihre gedruckte Erklärung entfernt.)

123
Wesley

Das Ziel der Blasensortierung besteht darin, die heavyier - Elemente in jeder Runde unten zu verschieben, während die heller - Elemente nach oben verschoben werden. In der inneren Schleife, in der Sie die Elemente vergleichen, Sie müssen nicht in jeder Runde die gesamte Liste durchlaufen. Das schwerste wird bereits als letztes platziert. Die Variable swapped ist eine zusätzliche Prüfung, sodass wir markieren können, dass die Liste jetzt sortiert ist und nicht mit unnötigen Berechnungen fortfahren.

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

Ihre Version 1, korrigiert:

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
11

Wenn Sie einen Variablennamen mit negativer Bedeutung verwenden, müssen Sie deren Werte invertieren. Folgendes wäre einfacher zu verstehen:

sorted = False
while not sorted:
    ...

Andererseits ist die Logik des Algorithmus etwas abwegig. Sie müssen prüfen, ob zwei Elemente während der for-Schleife ausgetauscht wurden. So würde ich es schreiben:

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
9
Martin Cote

Ihre Verwendung der unsortierten Variablen ist falsch. Sie möchten eine Variable haben, die Ihnen mitteilt, wenn Sie zwei Elemente ausgetauscht haben. Wenn Sie das getan haben, können Sie die Schleife beenden, andernfalls müssen Sie die Schleife erneut ausführen. Um zu korrigieren, was Sie hier haben, fügen Sie einfach den "unsorted = false" in den Körper Ihres if-Falls ein. entferne den anderen Fall; und setzen Sie "unsorted = true" vor Ihre for-Schleife.

8
Paul Sonier
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
5
mtasic85

#Eine sehr einfache Funktion kann (offensichtlich) durch Verringerung des Problembereichs des 2. Arrays optimiert werden. Aber die gleiche O (n ^ 2) -Komplexität.

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

Ein einfacheres Beispiel:

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

Dadurch werden die Elemente einfach von 0 bis a (im Allgemeinen alle unsortierten Elemente in dieser Runde) genommen und mit dem benachbarten Element verglichen. Wenn es größer ist als das angrenzende Element, wird ein Swap ausgeführt. Am Ende der Runde wird das letzte Element sortiert, und der Prozess läuft wieder ohne, bis alle Elemente sortiert wurden.

Es ist keine Bedingung erforderlich, ob sort wahr ist oder nicht.

Beachten Sie, dass dieser Algorithmus die Position der Zahlen nur beim Tauschen berücksichtigt, sodass sich wiederholte Zahlen nicht darauf auswirken.

PS. Ich weiß, es ist sehr lange her, seit diese Frage veröffentlicht wurde, aber ich wollte diese Idee nur teilen.

2
txsaw1
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
2
Zile Rehman

Ich bin ein frischer Anfänger und habe gestern angefangen, über Python zu lesen ... ___ Inspiriert von Ihrem Beispiel habe ich etwas mehr im 80er-Jahre-Stil entworfen, aber trotzdem funktioniert es irgendwie

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

Das Problem mit dem ursprünglichen Algorithmus ist, dass eine niedrigere Nummer in der Liste nicht zur richtigen sortierten Position führen würde. Das Programm muss jedes Mal vom Anfang zurückgehen, um sicherzustellen, dass die Zahlen vollständig sortiert sind.

Ich habe den Code vereinfacht und funktioniert nun mit jeder Liste von Nummern, unabhängig von der Liste und selbst wenn sich Nummern wiederholen. Hier ist der Code

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)
2
weinberg
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
2
pinkopink
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) 

2
pythonnewbie

Sie haben da ein paar Fehler. Die erste ist lang, und die zweite besteht in der Verwendung von unsortiertem (wie von McWafflestix angegeben). Sie möchten die Liste wahrscheinlich auch zurückgeben, wenn Sie sie ausdrucken möchten:

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: Du hast recht, das obige ist so verdammt schlecht. Mein Nachteil, dass ich einige Beispiele nicht mehr getestet habe.

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
2
Trevor Oke
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
1
Rocky
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 __== '__main__':
    # test list
    a = [ 67, 45, 39, -1, -5, -44 ];

    print ( a )
    bubbleSort ( a )
    print ( a )
1
aldo núñez
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]))
1
Luke Willey
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
0
Amandeep Singh
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 
0
user11689497

Versuche dies

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)
0
vivek shinde

idk wenn dir das nach 9 jahren helfen könnte ... es ist ein einfaches blasensortierprogramm

    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]
0
carl

Die Antworten von the-fury und Martin Cote haben das Problem der Endlosschleife behoben, aber mein Code würde immer noch nicht richtig funktionieren (für eine größere Liste würde er nicht richtig sortiert.) Am Ende habe ich die Variable unsorted aufgegeben und stattdessen einen Zähler verwendet.

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 __== '__main__':
    mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99]
    print bubble(mylist)

Wenn jemand Hinweise dazu geben könnte, wie ich meinen Code in den Kommentaren verbessern kann, wäre das sehr dankbar.

0
Josh Hunt

Ich möchte meine Lösung teilen:

def bubble_sort(list_):
    for i in range(len(list_)):
        for j in range(i, len(list_)):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]
return list_

Testbeispiel:

a = [8,1,2,4,1,3,5,1,5,6,1,8]
bubble_sort(a)

Ergebnis:

[1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 8, 8]
0
Artiom Kozyrev