Seite 1 von 1
Hilfe, insertion sort dauerloop
Verfasst: Montag 30. November 2020, 12:29
von sarapheus12
Hey, ich verstehe nicht wieso ich in einer for-schleife gefangen bin.
Eventuell kann mir jemand bei der Logik dahinter helfen.
Ich will eine " Insertion Sort" programmieren um Zahlen aus einer Liste in der richtigen reihenfolge zu sortieren.
Danke schonmal im Vorraus.
Code: Alles auswählen
def insertion_sort(liste):
neue_liste = []
neue_liste.append(liste[0])
for item in liste[1:]:
if item < neue_liste[0]:
neue_liste.insert(0,item)
if item > neue_liste[-1]:
neue_liste.append(item)
else:
for index, i in enumerate(neue_liste):
if item > i:
continue
else:
neue_liste.insert(index-1,item)
return neue_liste
liste = [5,6,1,2,87,3]
print(insertion_sort(liste))
Re: Hilfe, insertion sort dauerloop
Verfasst: Montag 30. November 2020, 14:24
von Sirius3
Man darf eine Liste, über die man aktuell iteriert, nicht verändern. Du mußt also erst den Index heraussuchen und erst dann einfügen.
Re: Hilfe, insertion sort dauerloop
Verfasst: Montag 30. November 2020, 15:15
von __blackjack__
Hier kann man das schon machen, aber nach dem einfügen sollte man halt aufhören weiter einen Index zu einfügen zu suchen. Wenn man das *eine* Element eingefügt hat, dann ist man ja fertig und muss/darf mit der Schleife nicht weiter machen.
@sarapheus12: Das ``continue`` kann und sollte man sich sparen in dem man das ``if``/``else`` so umformuliert das man mit einem ``if`` auskommt. Dann ist der Algorithmus auch verständlicher zu lesen.
Die ersten beiden Zeilen kann man vereinfachen in dem man nicht erst eine leere Liste erstellt und da dann ein Element anhängt, sondern gleich eine Liste mit einem Element erstellt.
Du brauchst mehr Testfälle: Deine Funktion kann beispielsweise eine leere Liste nicht sortieren.
Re: Hilfe, insertion sort dauerloop
Verfasst: Montag 30. November 2020, 15:39
von Sirius3
Bei der Regel, generell keine solchen Listen zu ändern, fährt man halt immer richtig, und das ist hier ja auch kein so großer Aufwand.
Code: Alles auswählen
def insertion_sort(liste):
neue_liste = []
for item in liste:
if not neue_liste or item > neue_liste[-1]:
neue_liste.append(item)
else:
for index, item2 in enumerate(neue_liste):
if item < item2:
break
neue_liste.insert(index, item)
return neue_liste
Re: Hilfe, insertion sort dauerloop
Verfasst: Dienstag 1. Dezember 2020, 03:23
von sarapheus12
Dankeschön für die tipps!
Hab den code jetzt optimiert
Re: Hilfe, insertion sort dauerloop
Verfasst: Dienstag 1. Dezember 2020, 07:33
von snafu
Das Ermitteln des Index zum Einfügen könnte man auch auslagern:
Code: Alles auswählen
def get_insertion_index(item, comparatives):
if item > comparatives[-1]:
return len(comparatives)
for index, other in enumerate(comparatives):
if item < other:
return index
def insertion_sort(items):
result = items[:1]
for item in items[1:]:
index = get_insertion_index(item, result)
result.insert(index, item)
return result
def main():
print(insertion_sort([5, 6, 1, 2, 87, 3]))
print(insertion_sort([-10, 5, 16, 0, -123]))
print(insertion_sort([]))
if __name__ == "__main__":
main()
Alternativ dazu hat Python auch schon was in der Standard-Bibliothek:
Code: Alles auswählen
from bisect import insort_left
def insertion_sort_bisect(items):
result = items[:1]
for item in items[1:]:
insort_left(result, item)
return result
Tut was es soll, aber für den Einstieg zum Lernen natürlich nicht so praktisch.