Sortieren einer Liste von Zahlen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Sortieren einer Liste von Zahlen

    was mich sonst noch bedrückt:

    Ich möchte gerne eine Liste von Zahlen sortieren.
    Hier mein Versuch:
    [code:1](define (reverse list)
    (cond
    [(empty? list) empty]
    [else
    (helper list)]))

    (define (helper list)
    (cond
    [(empty? (cdr list)) (car list)]
    [else
    (cons (helper (cdr list))
    (car list))]))
    [/code:1]

    Hier ein Beispiel:
    [code:1](define test (list 1 2 3 4 5))
    (reverse test)
    ((((5 . 4) . 3) . 2) . 1)[/code:1]

    Meine Funktion dreht die Liste also schön um, macht aus der Liste dann jedoch verschachtelte Paare (wenn ich das richtig verstanden habe).
    Eigentlich ist mir sogar das Problem bekannt:
    [code:1] (cons (helper (cdr list))
    (car list))]))
    [/code:1] generiert immer ein neues Paar mit einer Liste und einem einzelnen Objekt, weshalb die Verschachtelung auftritt.
    Trotz dieser EInsicht weiss ich mir leider aufgrund mangelnder Scheme-Kenntnissen nicht zu helfen. Wenn ich die Therie richtig verstanden habe, sollte ich cons mit einem empty verwenden, damit eine Liste und nicht ein Paar entsteht. Wie kann ich das realisieren?

  • Hallo nochmal,

    Listen sind in Scheme ein Spezialfall von verschachtelten Paaren. Die leere Liste (was du mit empty meinst) ist nur ein leeres Klammerpaar (). Eine einelementige Liste wäre bspw. (0 . ()), eine zweielementige (0 . (1 . ())), usw. Wichtig ist dabei, daß die Teilliste auf der rechten Seite steht. Wenn deine reverse-Funktion die Liste umdreht, muß die die Teilliste auch wieder auf die rechte Seite. Deine helper-Funktion packt die rekursiv bearbeitete Teilliste aber in die linke Seite. Das ergibt dann zwar auch eine listen-ähnliche Struktur, aber nicht das, was Scheme unter einer Liste versteht. ;)

    Zusammengefaßt: (list 1 2) = (cons 1 (cons 2 ())) /= (cons (cons () 1) 2)

    Was die Sortieralgorithmen angeht, hast du ja viele verschiedenen Möglichkeiten. Eine relativ leicht zu implementierende ist diese (in Pseudocode):
    [code:1]; Sortiert eine Liste aufsteigend
    insort () = ()
    insort (x . xs) = insortHelper x (insort xs)

    ; Fügt in eine aufsteigend sortierte Liste ein Element an der richtigen Stelle ein
    insortHelper y () = (y)
    insortHelper y (x . xs) = if (y <= x) then (y . (x . xs)) else (x . (insortHelper y xs))
    [/code:1]

    Nochmals viele Grüße,

    Siracusa