rekursion bzw Mergeosrt

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
otttim
User
Beiträge: 1
Registriert: Freitag 6. Februar 2004, 15:12

Freitag 6. Februar 2004, 15:38

Die Rekursion bringt mich etwas durcheinander. Und zwar hab ich volgende Funktion, die mir eine liste von Zahlen schön sortiert. :

Code: Alles auswählen

def merg(v):
    if len(v)>1:
        left =v[:len(v)/2]
        r=v[len(v)/2:]
        print "l:",left,len(left),":l",
        merg(left)
        merg(r)
        print "r: ",r,":r"
        r.reverse()
        merge=left+r
        print "|",merge,"|",
        lindex=0
        rindex=-1
        for count in range(len(v)):
            if merge[lindex]<merge[rindex]:
                v[count]=merge[lindex]
                lindex=lindex+1
               
            else:
                v[count]=merge[rindex]
                rindex=rindex-1
        print "v:",v,":v",

merg([12,11,5])
Ausgabe:

L: [12] 1 :L
L: [11] 1 :L
r: [5] :r
| [11, 5] | v: [5, 11] :v r: [5, 11] :r
| [12, 11, 5] | v: [5, 11, 12] :v
WARUM gibt er mir "v: [5, 11] :v" und geht danach nochmal in die Funktion um gibt mir r:[5,11]:r aus?? nach dem print "v:",v,":v" ist noch schluss und die Funktion müsste enden *verzweifel!* Und warum geht er nach der ausgabe L:[12]1:L nochmal in die Funtkion? nachdem mit merg(left) doch die 12 übergeben wurde und danach len(v) == 1 sein muesste dürfte doch nicht L: [11] 1 :L erscheinen????
Christopy
User
Beiträge: 131
Registriert: Montag 15. Dezember 2003, 22:39

Freitag 6. Februar 2004, 16:51

Hallo otttim
Vielleicht verstehst Du es besser, wenn Du die Printanweisungen anders setzt.

Code: Alles auswählen

def merg(v): 
    if len(v)>1: 
        left =v[:len(v)/2] 
        right=v[len(v)/2:] 
        print "left: ", left
        print "right: ", right
        print "----------"
        
        merg(left) 
        merg(right) 
        
        right.reverse() 
        merge=left+right
        print "zusammen: ", merge
        
        lindex=0 
        rindex=-1 
        for count in range(len(v)): 
            if merge[lindex]<merge[rindex]: 
                v[count]=merge[lindex] 
                lindex=lindex+1 
                
            else: 
                v[count]=merge[rindex] 
                rindex=rindex-1 
        print "v: ", v

merg([12,11,5])
Bernd

Dienstag 17. Februar 2004, 13:56

Hallo erstmal,

habe mich auch an diese Sortierung herangemacht und mein Quelltext ist sehr ähnlich, leider funktioniert der rekursive Funktionsaufruf bei mir nicht.

Fehler : global name 'sort' is not defined

hier der Quelltext:

Code: Alles auswählen

    def sort(LIST):
        n=len(LIST)
        if n>1:    
            sort(LIST[:n/2])  #L
            sort(LIST[n/2:])  #R
            for i in range(n/2):
                for j in range(n/2+1,n):
                    if LIST[j]>LIST[i]: break
                    elif LIST[j]<LIST[i]:
                        LIST.insert(i,LIST[j])
                        LIST.remove(LIST[j+1])
                        n+=1


    a=[3,5,8,0,1,6]
    print a
    sort(a)
    print a
was mach ich denn nun anders=falsch?
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Dienstag 17. Februar 2004, 20:23

Hi Bernd,

ich hab dein Script schnell mal ausprobiert, nach entfernen der tabs/spaces am Anfang jeder Zeile.

Code: Alles auswählen

>>> sort(a)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 8, in sort
IndexError: list index out of range
da scheint der Fehler doch wo anders zu liegen.


Gruß

Dookie
Gast

Freitag 20. Februar 2004, 14:33

Hallo Dookie,

danke erstmal - so kann ich nach weiteren Fehlern suchen,
aber ich wollte verschiedene Sortierfunktionen in einer Klasse zusammenfassen (daher die tabs).

Wie binde ich die Funktion dann richtig ein, wenn sie fehlerlos arbeitet?
Ich möchte ohne ein Klassenobjekt auskommen und nur bei Bedarf die entsprechende Funktion importieren.

Grüße aus Hannover
Bernd
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Freitag 20. Februar 2004, 15:11

Hi Bernd,

Du könntest die jeweilige Funktion auch an eine Variable zuweisen.

Code: Alles auswählen

def ausgabe(text):
    print text

def verkehrt(text):
    l = list(text)
    l.reverse()
    print "".join(l)

f = ausgabe
f("Hallo Welt!")
f = verkehrt
f("Hallo Welt!")

Gruß

Dookie
Bernd

Donnerstag 26. Februar 2004, 09:01

Hallo Dookie,

das sieht interessant aus - nur sehe ich noch nicht, wie ich's bei mir umsetzen kann.

hab' trotzdem Dank - den Trick kannte ich bis dato noch nicht.

Grüße Bernd

Hier mein Skript :

Code: Alles auswählen

from random import randint

#class ListSort:

def sort(LIST,l=0,r=-1):
    if r==-1:    r=len(LIST)
    if r-l>1:    
        p=(l+r)/2
        sort(LIST,l,p)  #L
        sort(LIST,p,r)  #R
        i=l
        while i<p:
            for j in range(p,r):
                if LIST[j]>LIST[i]: break
                elif LIST[j]<LIST[i]:
                    o=LIST[j]
                    LIST.remove(LIST[j])
                    LIST.insert(i,o)
                    p+=1
            i+=1

a=[]
for i in range (20):
    w=randint(1,100)
    if w not in a:
        a.append(w)
print a
sort(a)
print a
Antworten