Seite 1 von 1
Merge-Sort-Algorithmus
Verfasst: Mittwoch 17. Juni 2015, 18:29
von MarWill11
Hallo,
ich habe ein kleines Problem mit meinem Programm.
Ich soll einen Merge-Sort-Algorithmus programmieren, der die Anzahl der durchgeführten Vergleiche ausgibt und die sortierte Liste.
Ich kriege aber bei meiner Programmierung lediglich die Zufallsliste ausgespuckt...wenn ich "print Ergebnis" eingebe, dann gibt er mir gar nichts aus.
Was muss ich da verbessern, dass das gewünschte geliefert wird?
(Bitte einfache Erklärungen bzw Hinweise, da ich mit Python und allgemein mit Programmieren nicht wirklich vertraut bin.)
...außerdem lautet die Aufgabe weiter:
"Führen Sie damit eine (größere) Anzahl Sortierungen von verschiedenen Feldern gleicher Größe durch! Bestimmen Sie die Anzahl der durchschnittlich notwendigen Tausch-Aktionen, die geringste Anzahl sowie die größte Anzahl notwendiger Tausch-Aktionen!"
...wie würde man dies realisieren können?
Danke schon mal im Voraus für jede Hilfe.!!!
Mein bisheriges Programm:
___
Code: Alles auswählen
import random
a=input("Range untere Grenze: ")
b=input("Range obere Grenze (ausschließlich: ")
c=input("Anzahl der Zufallszahlen: ")
z=random.sample(range(a,b),c)
zaehler = 0
def mergesort(z):
if len(z)==1:
return z
else:
m=len(z)/2
l=mergesort(z[:m])
r=mergesort(z[m:])
return mergesort(l,r)
def merge(l,r):
global zaehler
Ergebnis=[]
while len(l)>0 and len(r)>0:
if l[0] < r[0]:
Ergebnis.append(l.pop(0))
else:
Ergebnis.append(r.pop(0))
zaehler=zaehler+1
Ergebnis.extend(l)
Ergebnis.extend(r)
return Ergebnis
print z
print zaehler
Re: Merge-Sort-Algorithmus
Verfasst: Mittwoch 17. Juni 2015, 18:39
von Sirius3
Wo rufst Du Deine Sortierfunktion auf?
Re: Merge-Sort-Algorithmus
Verfasst: Mittwoch 17. Juni 2015, 18:53
von MarWill11
meinst du mit "aufrufen", dass ich vor dem print nochmal "mergesort(z)" eingebe?
oder vielleicht "merge(r,l)"?
Re: Merge-Sort-Algorithmus
Verfasst: Mittwoch 17. Juni 2015, 19:15
von Sirius3
@MarWill11: genau. Damit Funktionen ausgeführt werden, muß man sie aufrufen.
Re: Merge-Sort-Algorithmus
Verfasst: Mittwoch 17. Juni 2015, 21:40
von Lateralus
Hi, ich hab jetzt die Programm-Logik nicht genau geprüft, aber so scheint es zu funktionieren:
Ich habe deine globalen Aufrufe mal in die Funktion main verschoben, welche durch die letzten zwei Zeilen aufgerufen wird, wenn die Datei ausgeführt wird. (So kann man die Datei auch als Modul verwenden.) Wenn du das nicht verstehst, kannst du es für's erste ignorieren. Die erste Zeile ist dazu da, dem Interpreter mitzuteilen, dass der Code UTF-8 zeichen verwendet (
Ich habe zwei Zeilen geändert die fehlerhaft waren: Zeile 11 und Zeile 17 (in deinem Skript). Die erste Zeile war bei mir nötig, als ich den Code aus dem Forum kopiert habe (scheint irgendein unsichtbares Zeichen, dass kein ASCII ist, mit dabei zu sein...)
Der Aufruf der Funktion erfolgt bei mir in Zeile 15.
Code: Alles auswählen
# -*- coding: utf-8 -*-
import random
def main():
a = input("Range untere Grenze: ")
b = input("Range obere Grenze (ausschließlich): ")
c = input("Anzahl der Zufallszahlen: ")
z = random.sample(range(a,b),c)
global zaehler
zaehler = 0
print(z)
ergebnis = mergesort(z)
print(ergebnis)
print(zaehler)
def mergesort(z):
# if len(z) == 1:
if len(z) <= 1:
return z
else:
m = len(z)/2
l = mergesort(z[:m])
r = mergesort(z[m:])
# return mergesort(l,r)
return merge(l, r)
def merge(l,r):
global zaehler
Ergebnis = []
while len(l)>0 and len(r)>0:
if l[0] < r[0]:
Ergebnis.append(l.pop(0))
else:
Ergebnis.append(r.pop(0))
zaehler = zaehler + 1
Ergebnis.extend(l)
Ergebnis.extend(r)
return Ergebnis
if __name__ == '__main__':
main()
Re: Merge-Sort-Algorithmus
Verfasst: Donnerstag 18. Juni 2015, 07:21
von MarWill11
Wow. 1000 Dank.!!
Ich habe aber noch eine Frage zu den letzten beiden Zeilen: Welche Bedeutung haben die? Ohne diese Zeilen funktioniert es ja nicht, aber ich habe dieses
noch nie gesehen. :/
Hättest du vielleicht auch einen Hinweis zur Teilaufgabe:
"Führen Sie damit eine (größere) Anzahl Sortierungen von verschiedenen Feldern gleicher Größe durch! Bestimmen Sie die Anzahl der durchschnittlich notwendigen Tausch-Aktionen, die geringste Anzahl sowie die größte Anzahl notwendiger Tausch-Aktionen!"
...also keine Lösung, sondern nur eine Idee wie man es realisieren könnte?
Beste Grüße
Re: Merge-Sort-Algorithmus
Verfasst: Donnerstag 18. Juni 2015, 07:42
von DasIch
__name__ ist der Name des Moduls unter dem es importiert wurde und wird vom Interpreter gesetzt. Wenn du ein Modul direkt ausführst hast du es nicht importiert, in diesem Fall wird der spezielle Name __main__ verwendet. Die main() funktioniert wird in diesem Fall also nur dann ausgeführt wenn dieses Modul direkt ausgeführt und nicht irgendwo importiert wurde.
Dies erlaubt es das Modul z.B. in der Python Shell oder in Tests zu importieren so dass man mit einzelne Teile testen kann ohne dass das Program ausgeführt wird.
Re: Merge-Sort-Algorithmus
Verfasst: Donnerstag 18. Juni 2015, 07:52
von cofi
MarWill11 hat geschrieben:Hättest du vielleicht auch einen Hinweis zur Teilaufgabe:
"Führen Sie damit eine (größere) Anzahl Sortierungen von verschiedenen Feldern gleicher Größe durch! Bestimmen Sie die Anzahl der durchschnittlich notwendigen Tausch-Aktionen, die geringste Anzahl sowie die größte Anzahl notwendiger Tausch-Aktionen!"
...also keine Lösung, sondern nur eine Idee wie man es realisieren könnte?
Hinweis: `zaehler`.
Re: Merge-Sort-Algorithmus
Verfasst: Donnerstag 18. Juni 2015, 07:57
von Sirius3
@MarWill11: Du hast noch nie eine if-Abfrage oder einen Funktionsaufruf gesehen? Nochmal, damit Funktionen ausgeführt werden, muß man sie aufrufen. In Python hat jedes Modul einen Namen, der in der Variable __name__ steht. Das Hauptprogramm hat dabei den festen Namen '__main__'. Damit wird erreicht, dass Python-Dateien sowohl als Modul als auch als Skript verwendet werden können.
Vergiss gleich wieder, dass es soetwas wie "global" gibt. Wenn "merge" etwas zählt, dann ist das ein zusätzlicher Rückgabeparameter. "mergesort" kann dann die einzelnen Zähler zusammenfassen und auch zurückgeben.
Übrigens, Du zählst falsch.
Dass "merge" die Listen "l" und "r" verändert ist ein unerwartetes Verhalten, das zumindest dokumentiert werden muß, auch wenn es sich nur um eine interne Funktion handelt.