Mergesort

[19mareut]

def test(r,t):

global rv

global tv

if r[rv - 1] > t[tv - 1]:

lt.append(t[tv])

t.remove(t[tv])

tv += 1

ttr = True

else:

lr.append(r[rv])

r.remove(r[rv])

rv += 1

rtr = True

ich weis nicht was hieran falsch ist. kann mir pls wer helfen? ^^ also r und t sind beides listen, gleichlang ungefähr (maximal eins größer als die andere). rtr und ttr sind variablen mit startwert 0. lt ist eine leere liste. aber es geht nicht

[__blackjack__]

@19mareut: Die Darstellung im Beitrag ist falsch, weil da die Einrückung fehlt. Verwende bitte Code-Tags. Im vollständigen Editor kann man die über die Schaltfläche mit der Beschriftung </> einfügen.

Dann sind die Namen falsch. Ernsthaft. Verwende nicht so furchtbare, kryptische Abkürzungen.

Auf jeden Fall falsch ist auch die Verwendung von ``global``. Was soll der Unsinn denn? Warum muss der *Aufrufer* diese Variablen initialisieren? Die gehen den Aufrufer doch überhaupt nichts an. Wobei ich gerade sehe das die Funktion `test()` heisst und keine Schleife enthält. Eine Funktion mit dem Namen sollte etwas *testen*, und *nichts* verändern, und einen Wahrheitswert als Rückgabewert haben. Sie ist aber weder eine einfache Testfunktion noch eine Sortiertfunktion. Also wo ist denn hier dann das eigentliche Mergesort?

Ebenfalls globale Variablen sind `lt` und `lr` — wofür stehen die denn bitte? Und es sind globale Variablen: Verwende keine globalen Variablen! Niemals nicht!

Laut Beitrag sind `rtr` und `ttr` Variablen mit dem Startwert 0 — in der Funktion werden die aber auf `True` gesetzt, und nirgends verwendet. Wieder Unsinn. Die beiden Zeilen kann man löschen ohne das sich am Programmablauf etwas ändert.

Warum werden die Elemente an den Indexen rv-1 und rt-1 verglichen, dann aber die Elemente an den Indexen rv und rt ”verschoben”? Wobei das auch wieder komplett unsinnig ist die per `remove()` aus den ursprünglichen Listen zu entfernen. Dadurch ändern sich ja die Indexwerte aller nachfolgenden Elemente. Die Indexvariablen über die Zugegriffen wird, werden aber um eins erhöht, zeigen also auf das übernächste Element statt auf das nächste.

Und an der Fehlerbeschreibung ist noch falsch das Du nicht sagst was „es geht nicht“ ganz konkret bedeutet. Da das nicht lauffähig ist, kann man das ja nicht einmal selbst ausprobieren.

[__blackjack__]

@19mareut: Warum ist da eigentlich jede zweite Zeile eine Leerzeile? Das macht keinen Sinn.

Hier mal die Funktion als richtige Funktion die alles was sie benötigt als Argumente übergeben bekommt und alles was sie (potentiell) verändert als Ergebnis an den Aufrufer zurück liefert, statt globale Variablen zu verwenden. So sieht man jetzt was die Funktion alles von aussen braucht, in dem man sich einfach die ``def``-Zeile anschaut. Was man immer noch nicht so leicht sehen kann ist was die Funktion verändert. Das sollte aus einem passenden Funktionsnamen und sprechenden Namen für die Argumente klar werden und falls das nicht reicht, sollte man es dokumentieren.

Code: Alles auswählen

def test(r, t, rv, tv, lt, lr):
    if r[rv - 1] > t[tv - 1]:
        lt.append(t[tv])
        t.remove(t[tv])
        tv += 1
    else:
        lr.append(r[rv])
        r.remove(r[rv])
        rv += 1

    return rv, tv

Die beiden `append()`/`remove()`-Kombinationen sind mindestens mal ineffizient und falls der gleiche Wert auch vor dem Index `tv` oder `rv` in der jeweiligen Liste vorkommen kann ist das ziemlich sicher auch falsch. Wenn dort der Wert an genau dem Index verschoben werden soll, dann sollte man auch genau den Wert an dem Index entfernen und nicht mit `remove()` linear nach dem Wert suchen lassen:

Code: Alles auswählen

def test(r, t, rv, tv, lt, lr):
    if r[rv - 1] > t[tv - 1]:
        lt.append(t.pop(tv))
        tv += 1
    else:
        lr.append(r.pop(rv))
        rv += 1

    return rv, tv

Auch das `pop()` ist ineffizient weil alle nachfolgenden Elemente verschoben werden müssen.

Und das ``+= 1`` riecht komisch weil das bedeutet, das `tv` beziehungsweise `rv` dann nicht mehr auf das nächste sondern auf das übernächste Element ”zeigen”. Falls das ``- 1`` in der Bedingung dem entgegenwirken soll: Das funktioniert natürlich nicht weil a) nur einer der beiden Werte in einem Aufruf verändert wird, und das b) bei jedem Aufruf von `test()` passiert. Es also nicht bei der 1 bleibt, sondern bei jedem Aufruf in dem `rv` oder `tv` verändert wird, diese Abweichung um 1 passiert.

Um näher zu beschreiben was „aber es geht nicht“ denn nun konkret heisst, müsstest Du verraten mit welchen Werten die Funktion konkret aufgerufen wird, und was am Ergebnis von dem abweicht was Du erwartet hast. Denn das wissen wir nicht und man kann das wegen der nichtssagenden Namen auch nicht wirklich erraten. Der Begriff Mergesort steht im Betreff, aber das ist kein Mergesort. Es könnte der Versuch sein ein Teilproblem von einem Mergesort zu lösen, aber da müsste man jetzt raten welches. Es sieht am ehesten nach *einem* Schritt in einem Merge von zwei sortierten Listen aus, aber da frage ich mich dann a) warum man dazu Elemente aus Listen entfernen sollte und warum es zwei verschiedene Listen gibt an die Werte angehängt werden. Denn ein Merge bekommt ja zwei Eingabelisten und liefert *eine* Ausgabeliste‽

Falls es kein Mergesort sondern ein Quicksort wäre, stellt sich die umgekehrte Frage: Da hat man zwar beim Aufteilen des Problems für den rekursiven Aufruf zwei Listen in die man die Eingabe aufteilt, da ist die Eingabe aber in *einer* Liste und nicht in zweien.

[19mareut]

a = -1

n = 1

l = []

ttr = False

rtr = False

ein = input('Element der Liste(wenn alle angegeben, j) ')

while ein != 'j':

l.append(ein)

ein = input('Element der Liste(wenn alle angegeben, j) ')

a += 1

#Alle Variablen und Listen definiert

lx = []
#halbierte Liste zum Mergen
ly = []
#eine Liste wie lx
lz= []
#eine liste zum Zwischenspeichern
r = []
#eine Seite des Mergens
t = []
#andere Seite des Megens
lt = []
#liste zum Speichern von Dingen aus Liste t
lr=[]
#liste zum Speichern von Dingen aus Liste r
nl = []
#Liste zum Speichern von l
x = 0

rv = 0

tv = 0

print(l)

def test(r,t):

global rv

global tv

global rtr

global trt

if r[rv - 1] > t[tv - 1]:

lt.append(t[tv])

t.remove(t[tv])

tv += 1

ttr = True

else:

lr.append(r[rv])

r.remove(r[rv])

rv += 1

rtr = True


def merge(r,t):

global rv

global tv

global rtr

global trt

while len(r) > 0 and len(t) > 0:

test(r,t)

if ttr == True:

ttr = False

test(r,t)

elif rtr == True:

rtr = False

test(r,t)

#x = 0

nl = l

while len(l) != 0:

if x % 2 == 0:

lx.append(l[0])

x += 1

l.remove(l[0])


else:

ly.append(l[0])

x += 1

l.remove(l[0])


print(lx)
print(ly)

r = lx

t = ly

merge(r,t)

print(lr)
print(lt)

#merge(r,t)

#print(l)
#print(r)
#print(t)

[19mareut]

ja sorry hab nur das halbe ding gesendet ^^war dumm. erstmal danke für die krass ausführliche antwort ehrenwert.

die variablen wollte ich globalisieren weil der mir iwas geasgt hatte er kenne die variablen nicht iwo außerhalb der funktion

ja das isses ja der mergerschritt geht nicht

und der test soll nur der vergleich sein

das ich den mergeschritt aufteilen kann damit das iwie einacher wird

[Jankie]

Also erstens solltest du (wie auch in den anderen Threads schon gesagt) dir passende Varaiblennamen überlegen und den Code in die Codetags packen. So wird kaum einer Lust haben dir zu helfen.

globale Variablen haben in einem sauberen Programm nichts verloren, wenn eine Funktion eine Variable braucht, dann übergibt man diese per Parameter. (was auch schon gesagt wurde)

Also erstmal die dir schon geannten Punkte umsetzen und dann noch mal lieb fragen.

[__blackjack__]

@19mareut: Funktionen bekommen alles was sie ausser Konstanten benötigen als Argument(e) übergeben und wenn sie ein Ergebnis haben dann würde das als Rückgabewert an den Aufrufer zurückgegeben.

Funktionen verändern auch keine Werte ausserhalb der Funktion. Man verwendet kein ``global``. Wenn sie Objekte verändern die sie übergeben bekommen, dann sollte das nicht überraschend für den Leser sein, also entweder sollte der Funktionsname das hergeben, oder man sollte das Dokumentieren.

Es ist einfacher sich daran zu halten wenn auf Modulebene nur Code steht der Konstanten, Funktionen, und Klassen definiert. Weil man dann nicht aus versehen auf irgendwelche globalen Variablen zugreifen kann. Nochmal: keine globalen Variablen! Weder über global, noch weil die auf Moduleben (oder Klassenebene) definiert sind. Das Hauptprogramm müsste also auch in eine Funktion und die heisst üblicherweise `main()`.

Dann habe ich Namen ja schon erwähnt: Die sind in dem Programm so ziemlich alles besch…eiden. Namen sollen dem Leser vermitteln was der Wert im Programm bedeutet. Und das tut dieser ganze Zoo aus ein- bis dreibuchstabigen Namen in dem Quelltext so gar nicht. Wenn man mit einem Kommentar erklären muss was der Wert hinter einem Namen bedeutet, ist die erste Frage die man sich stellen sollte, wie man den Namen ändern kann, so dass man den Kommentar nicht mehr braucht.

Kommentare gehören *vor* den Code auf den sich der Kommentar bezieht. Das bei den ganzen Listen am Anfang falsch herum.

Man definiert auch nicht alle Listen die irgendwo im Programm vielleicht mal gebraucht werden, am Anfang vom Modul. Wie gesagt: KEINE GLOBALEN VARIABLEN! Kann man gar nicht oft genug sagen.

Die `merge()`-Funktion sollte zwei Listen als Argumente bekommen und eine in der Funktion neu erstellte Liste zurück geben, wo die zusammengeführten Elemente aus den beiden übergebenen Listen enthalten sind. Die übergebenen Listen werden dabei nicht verändert.

Ein Grundgerüst des Programms könnte so aussehen:

Code: Alles auswählen

#!/usr/bin/env python3


def merge(items_a, items_b):
    merged_items = []

    ...

    return merged_items


def mergesort(items):

    ...

    return sorted_items


def main():
    #
    # TODO Eingabe der Werte vom Benutzer.
    # TODO Aufruf der Sortierfunktion.
    # TODO Ausgabe des Ergebnisses.
    #
    ...


if __name__ == "__main__":
    main()

Da können noch mehr (echte!) Funktionen dazu kommen, wenn man Teilaufgaben heraus ziehen möchte. Eine `test()`-Funktion bei der `merge()`-Funktion sehe ich aber nicht wirklich. Und wenn, dann sollte die einen spezifischeren, passenderen Namen bekommen, und nicht `test` im Namen haben wenn die mehr macht als nur etwas zu testen.

[19mareut]

was hat das mit diesem def main auf sich?
was ist dieses if __name__ == '__main__':
main()

[Sirius3]

Das `def` hast Du doch schon selbst benutzt, und definiert Funktionen.
Und dieses `if` sorgt einfach dafür, dass main nur dann aufgerufen wird, wenn man die Python-Datei als Skript startet und nicht wenn es als Modul importiert wird.

[__blackjack__]

Die beiden Funktionen `merge()` und `mergesort()` mal mit Inhalt gefüllt:

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import starmap

from more_itertools import grouper, peekable


def merge(items_a, items_b):
    items_a = peekable(items_a)
    items_b = peekable(items_b)
    merged_items = []
    while True:
        try:
            item_a = items_a.peek()
        except StopIteration:
            merged_items.extend(items_b)
            break

        try:
            item_b = items_b.peek()
        except StopIteration:
            merged_items.extend(items_a)
            break

        merged_items.append(next(items_a if item_a < item_b else items_b))

    return merged_items


def mergesort(items):
    sorted_sequences = [[item] for item in items]
    if not sorted_sequences:
        return []

    while len(sorted_sequences) != 1:
        sorted_sequences = list(
            starmap(merge, grouper(2, sorted_sequences, []))
        )

    return sorted_sequences[0]


def main():
    #
    # TODO Eingabe der Zahlen vom Benutzer.
    # TODO Aufruf der Sortierfunktion.
    # TODO Ausgabe des Ergebnisses.
    #
    ...


if __name__ == "__main__":
    main()