;;; Fichier tri.drs / 5 fevrier 2000

;;; 1ere Version (terminale):

(define (tri l)
  (define (aux l res)
    (cond ((null? l) res)
          (else (aux (cdr l) (inserer (car l) res)))))
  (aux l '()))

(define (inserer x l)
  (cond ((null? l) (list x))
        ((< x (car l)) (cons x l))
        (else (cons (car l) (inserer x (cdr l))))))
    
;;; 2eme Version (non terminale, plus rapide):

(define (tri-rapide l)
  (cond ((null? l) '())
        ((null? (cdr l)) l)
        (else 
         (append (tri-rapide (selection (cdr l) (car l) >=))
                 (list (car l))
                 (tri-rapide (selection (cdr l) (car l) <))))))

(define (selection l x pred)
  (cond ((null? l) '())
        ((pred x (car l)) 
         (cons (car l) (selection (cdr l) x pred)))
        (else (selection (cdr l) x pred))))
                      
;;; Une liste ...

(define (une-liste n)
  (define (aux k res)
    (cond ((= k 0) res)
          (else (aux (- k 1) (cons (random n) res)))))
  (aux n '()))