Grundlagen der funktionsorientierten Programmierung mit SCHEME/Minimum-Sortieren

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Streichen und Minimum ==

<code id="4caec8f912d94">
(define numliste '(2 3 5 -1 3 6 11 18 15 0 19 27 -33 -2 55 31 7 39 22 1))

(define streiche-erstes
  (lambda (el ls)
    ...))

(define minimum
  (lambda (ls)
    ...))
</code>

== MinSort ==

Zum Sortieren muss das Minimum an seiner ursprünglichen Stelle gestrichen und der Minumum-sortierten Restliste vorangesellt werden. Da wir dieses Element zum Streichen und Voranstellen zweimal benötigen, soll es ''lokal'' an eine Variable gebunden werden. Das entsprechende Sprachelement heißt  <tt>let</tt>.

<code id="4caecace17a2d" hidden>
(define listequal?
  (lambda (ls1 ls2)
    (cond
      [(and (null? ls1) (null? ls2)) #t]
      [(or (null? ls1) (null? ls2)) #f]
      [(and (list? (car ls1)) (list? (car ls1)))
         (and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))]
      [else 
       (and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))])))
</code>

<code id="4caec8f912ea8">
(define minsort
  (lambda (ls)
    (if (null? ls)
        ()
        (let ([el (minimum ls)])
          ...))))
</code>

<check>
(and (listequal? (minsort '(2 3 5 -1 3 6 11 18 15 0 19 27 -33 -2 55 31 7 39 22 1))
                 '(-33 -2 -1 0 1 2 3 3 5 6 7 11 15 18 19 22 27 31 39 55))
     (listequal? (minsort '(-1)) '(-1))
     (listequal? (minsort '()) '()))
</check>

<eval id="4caecace17b4e">(minsort numliste)</run>

Die Effizienz von [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MinSort|MinSort]] wollen wir [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/MinSort|später]] untersuchen.<br />

Zurück zu [[Komplexe Anwendungen: Numerische Listen|numerische Listen]].