Mergesort und Heapsort

[Bagti]

Hallo leute,

ich muss leider sagen das ich mit den Implementieren von Mergesort und Heapsort nicht weiter komme, besser gesagt weiß ich nicht wie ich nach dem def. weiter machen kann/soll.

Wir müssen ein Algorithmus erstellen wo wir die Mergesort und Heapsort implementieren sollen. Mir geht es hier in dem Post nicht darum von euch die Lösung zubekommen und damit die Aufgabe zu bestehen. Ich muss denn Vorgang einer solchen implemention verstehen. Wie Mergsort und Heapsort in der Theorie Funktionen habe ich im groben verstanden, allerdings wenn es ums implementieren geht blick ich nicht so ganz durch.

Wie gesagt in mit Theorie und Syntax komm ich klar. :K

Wie mach ich das jetzt.

Der Wert des letzten Blattes (größter Tiefe) soll mit dem der Wurzel vertauscht werden und somit aufzulösen. Der Algorithmus soll stoppen wenn die Wurzel Heap-Eigenschaft(muss ich das vorher noch mal definieren?) hat, wenn nicht soll das Wurzelelement mit maximalem
Element an den Kindern vertauscht werden.

So habe ich das Heapsort verstanden wenn da was falsch ist bitte sagen. Ich habe eine Liste bekommen diese soll nun in form von absteigenden Heapsort und Mergsort sortiert werden.

Wie gehe ich jetzt beim implementieren vor?

Danke schon mal für eure Zeit und für Lesen.

Bin absoluter Anfänger wie ihr sicherlich bemerkt habt

[BlackJack]

@Bagti: Du scheinst nicht der Einzige mit dieser Aufgabe zu sein: Vor zehn Tagen wurde dieses Thema eröffnet: Sortieren in Python.

Die Beschreibung vom Heapsort ist unverständlich. Wie kann beispielsweise die Wurzel Heap-Eigenschaft haben? Was soll das bedeuten?

Als ersten Schritt müsste man beschreiben wie der Algorithmus abläuft, in Worten, in Form einer detaillierten Handlungsanweisung. Denn so eine Handlungsanweisung muss man dann ja für den Rechner in Form von Quelltext formulieren. Und eine Gesamtbeschreibung ist hier zu umfangreich, man müsste das also in die Beschreibung von mehreren, in sich abgeschlossenen Arbeitsschritten aufteilen. So wie man die Implementierung auch in mehrere Funktionen aufteilt.

Das gilt für beide Sortieralgorithmen. Wenn das eine Hausaufgabe ist auf die es Punkte gibt, solltest Du eventuell auch erst einmal darüber nachdenken in welcher Reihenfolge Du die beiden Algorithmen implementierst. Denn Heapsort ist komplexer als Mergesort. Nicht das Du die ganze Zeit am Heapsort hängst und am Ende keinen der beiden implementiert hast, wo der Mergesort doch relativ einfach ist.

Wie sehen denn die Anforderungen an die Lösungen aus? Reicht es wenn man sieht das der Algorithmus verstanden wurde, oder muss es auch möglichst Laufzeit- und Speichereffizient sein? Bei Mergesort könnte man nämlich den Algorithmus auf relativ hohem Abstraktionsniveau implementieren, ziemlich nah an der üblichen Beschreibung des Algorithmus. Dann entstehen alerdings viele Teilkopien beim rekuriven Abstieg. Oder aber man kann das auch effizienter ohne rekursive Aufrufe und mit nur der doppelten Speichermenge der Ausgangsdaten lösen.

[Bagti]

Dankeschön für deine Antwort BlackJack

Also ich habe durch das Internet und paar Feunden Mergsort geschafft zu Implementieren und kann tatsächlich den Algorithmus nach vollzieren

Aber ich verstehe jetzt nicht so ganz wie ich Heapsort machen soll? Mit Heap-Eingenschaften meinte ich das die Kinder größer als der Vater sind.
Wichtig für die Aufgabe ist eigentlich nur das der Algorithmus folgendes ausgibt [17, 9, 4, 3, 2, 1, 0, -1] für den Heapsort. Der prof. will nur ausführen und dann muss die Sortierung ausgeben werden ^^.

Wie gesagt bei Mergsort hat es geklappt aber mir fehlt jetzt das wissen wie ich das mit Heapsort mache

Mergsort hab ich so gelöst :

Code: Alles auswählen

def sortMerge(a):
    print('Parameter a:')
    print(a)
    if len(a)>1: # hier soll Ihre Implementierung des Mergesort - Verfahrens stehen.
        mid = len(a)//2
        lefthalf = a[:mid]
        righthalf = a[mid:]

        sortMerge(lefthalf)
        sortMerge(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                a[k]=lefthalf[i]
                i=i+1
            else:
                a[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            a[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            a[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",a)
    result = a  # durch das Ergebnis Ihrer Implementierung ersetzen
    return result

Heapsort ist wirklich viel komplexer glaub ich als Mergsort ^^

[BlackJack]

@Bagti: Was an dem Mergesort sehr unschön ist, ist das `a` verändert wird *und* zurückgegeben wird. Das ist sehr unerwartet, denn entweder hat man eine Funktion im mathematischen Sinne, die das Ergebnis als Rückgabewert hat, aber die Argumente nicht verändert, oder man hat eine Funktion die das Argument verändert, aber es nicht zusätzlich zurück gibt. Macht ja auch gar keinen Sinn, denn der Aufrufer hat die Liste ja bereits, denn er hat sie beim Aufruf ja übergeben.

Und ja, Heapsort ist komplexer als Mergesort.

Wenn es nur auf die Ausgabe ankommt:

Code: Alles auswählen

def heap_sort(_):
    print([17, 9, 4, 3, 2, 1, 0, -1])

Ich würde da aber keine Punkte für erwarten.

[Bagti]

hahahaha ok nein das ist zu Simple das kann ich nicht bringen. Weißt du was mit der Fehlermeldung gemeint ist.

Und ich glaub das ich das vorgegebene print nicht änder darf. Das wäre zu schön ^^

TypeError: 'float' object cannot be interpreted as an integer

[BlackJack]

@Bagti: Wie würdest Du die Fehlermeldung denn übersetzen? Und wo genau kommt die?

[Bagti]

wenn ich denn durchlaufen lasse kommt die Fehlermeldung

Code: Alles auswählen

def sortHeapDesc(a):
    print('Parameter a:')
    print(a)
    for start in range((len(a)-2)/2, -1, -1):# hier soll Ihre Implementierung von absteigendem HeapSort stehen.
        siftdown(a, start, len(lst)-1)

    for end in range(len(a)-1, 0, -1):
        a[end], a[0] = a[0], a[end]
        siftdown(a, 0, end - 1)
    result = a  # durch das Ergebnis Ihrer Implementierung ersetzen
    
def siftdown(a, start, end):
  root = start
  while True:
    child = root * 2 + 1
    if child > end: break
    if child + 1 <= end and a[child] < a[child + 1]:
      child += 1
    if a[root] < a[child]:
      a[root], a[child] = a[child], a[root]
      root = child
    else:
      break

was will er mir genau sagen damit

Objekt kann nicht als Ganzzahl interpretiert werden? wenn ja warum

[BlackJack]

@Bagti: Du bekommst ja nicht nur die letzte Zeile mit der Meldung sondern auch den Traceback, der Dir genau die Zeile verrät in der die Ausnahme ausgelöst wird. Und auch die letzte Zeile in dem von Dir geschriebenen Quelltext, falls das nicht die gleiche Zeile sein sollte. Und dann schaust Du mal was in dieser Zeile gemacht wird, und welche Werte da überhaupt nur gemeint sein können die ganze Zahlen sein müssen. Und dann kannst Du heraus finden warum ein Wert dort keine ganze Zahl ist. Wenn Du es so nicht siehst, dann schreib dir vor diese Zeile ein `print()` hin was die Werte und Zwischenergebnisse von den Ausdrücken mal ausgibt.

Ein weiterer Hinweis in der Fehlermeldung ist ja das es eine *Gleitkommazahl* ist, die nicht als ganze Zahl interpretiert werden kann. Also wo in der Zeile wird eine ganze Zahl benötigt, aber ein Ausdruck verwendet der eine gebrochene Zahl ergeben kann? Die Frage nach dem Warum, also warum zum Beispiel 42.23 nicht als ganze Zahl funktioniert, sollte hoffentlich klar sein.

[Bagti]

ok danke aber ich komme trotzdem nicht zum richtigen Ergebnis das gib der ganze Algorithmus beim durchlaufen lass aus

Parameter a:
[-1, 0, 1, 2, 3, 4, 9, 17]
berechnet:
[0, 1, 2, 3, 4, 9, 17, -1]
None

[Bagti]

bin jetzt richtig verwirrt wenn ich den Algorithmus durchlaufen lasse (run) kommt

Parameter a:
[3, 2, 1, 9, 17, 4, -1, 0]
Parameter a:
[3, 2, 1, 9]
Parameter a:
[3, 2]
Parameter a:
[3]
Parameter a:
[2]
Parameter a:
[1, 9]
Parameter a:
[1]
Parameter a:
[9]
Parameter a:
[17, 4, -1, 0]
Parameter a:
[17, 4]
Parameter a:
[17]
Parameter a:
[4]
Parameter a:
[-1, 0]
Parameter a:
[-1]
Parameter a:
[0]
Parameter a:
[-1, 0, 1, 2, 3, 4, 9, 17]
berechnet:
[-1, 0, 2, 17, 3, 4, 9, 1]
None

Also irgendwie klappt Heapsorts nicht. also das Ergebnis ist falsch

[BlackJack]

@Bagti: Wo kommen die ganze Ausgaben denn her? Im Code gibst Du doch nur das Argument und das Ergebnis aus‽  Was sind jetzt die ganzen anderen Ausgaben? Rätst Du jetzt wild rum und versuchst irgendwie rekursive Aufrufe in den Heapsort einzubauen?

[Bagti]

Also mergsorts ist richtig bekomme [-1, 0, 1, 2, 3, 4, 9, 17] ausgeben. Aber bei Hearpsort schaffe ich das nicht das die absteigend wiedergegeben werden. Hast du da noch ein Tipp oder so. Will die Punkte ^^

[BlackJack]

@Bagti: Der Tipp wäre Heapsort korrekt zu implementieren. Aus welchen Teilen besteht der Algorithmus? Und wo ist der Fehler? Was hast Du gemacht um den Fehler zu finden? Wenn Du den Algorithmus von Hand mit Papier und Bleistift mit den Eingabedaten durchgehst, kommt dann das richtige Ergebnis heraus?

[darktrym]

Wenn aufsteigend funktioniert dann dreh doch die Liste.

[BlackJack]

@darktrym: Wenn aufsteigend sortieren funktioniert, dann braucht man nur die im Algorithmus enthaltenen Vergleiche umdrehen. Ist auch sehr einfach, und sieht weniger nach Hack aus.

[darktrym]

Für Mitleidspunkte würde es wohl reichen aber klar damit zeigt man seinen Dozenten nur das man das Prinzip nicht verstanden hat.