rekursion bzw Mergeosrt

[otttim]

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]

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]

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]

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]

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]

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]

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