Hilfe, insertion sort dauerloop

Code-Stücke können hier veröffentlicht werden.
Antworten
sarapheus12
User
Beiträge: 2
Registriert: Montag 30. November 2020, 12:19

Montag 30. November 2020, 12:29

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))
Sirius3
User
Beiträge: 14207
Registriert: Sonntag 21. Oktober 2012, 17:20

Montag 30. November 2020, 14:24

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.
Benutzeravatar
__blackjack__
User
Beiträge: 8430
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Montag 30. November 2020, 15:15

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.
“For every complex problem, there is a solution that is simple, neat, and wrong.” — H. L. Mencken
Sirius3
User
Beiträge: 14207
Registriert: Sonntag 21. Oktober 2012, 17:20

Montag 30. November 2020, 15:39

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
sarapheus12
User
Beiträge: 2
Registriert: Montag 30. November 2020, 12:19

Dienstag 1. Dezember 2020, 03:23

Dankeschön für die tipps!
Hab den code jetzt optimiert :)
Benutzeravatar
snafu
User
Beiträge: 6311
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Dienstag 1. Dezember 2020, 07:33

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. :)
Antworten