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.
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 True
nur 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.)
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
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
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.
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
#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
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.
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
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)
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)
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 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)
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
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 __== '__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]))
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 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
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)
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]
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.
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]