#lang racket ;; Sortiertes Einfuegen v1 (define (insert k lst) (if (null? lst) (list k) (if (< k (car lst)) (cons k lst) (cons (car lst) (insert k (cdr lst)))))) ;;; Insertion Sort v1 ("Schemeig") (define (isort l) (if (null? l) l (insert (car l) (isort (cdr l))))) ;;; Zusammen"mischen" von sortierten Listen (define (merge l1 l2) (cond ((null? l1) l2) ((null? l2) l1) ((< (car l1) (car l2)) (cons (car l1) (merge (cdr l1) l2))) (else (cons (car l2) (merge l1 (cdr l2)))))) ;;; Teilen einer Liste in ca. gleichgrosse Teillisten ;;; Input: Liste l ;;; Output: Liste von Listen (l1 l2), wobei jedes Element von l ;;; in l1 oder l2 ist, und jedes Element von l1 und l2 in l ist, ;;; und l1 und l2 ungefaehr gleiche Laenge haben (define (split l) (cond ((null? l) ; Leeres l -> ('() '()) (list '() '())) ((null? (cdr l)) ; Nur ein Element: ('() l) (list '() l)) (else ; Sonst: (let* ((res (split (cddr l))) (l1 (car res)) ;; Erste Liste des Teilergebnisses (l2 (cadr res)) ;; Zweite ) (list (cons (car l) l1) (cons (cadr l) l2)))))) (define (mergesort l) (if (or (null? l) (null? (cdr l))) l (let* ((res (split l)) (l1 (mergesort (car res))) (l2 (mergesort (car (cdr res))))) (merge l1 l2)))) ;;; BM (define (read-list-verbose inp) (let ((l1 (read inp))) (display "Liste mit ") (display (length l1)) (display " Elementen eingelesen") (newline) l1 )) (define in-fp (open-input-file "sortlists.txt")) (define l1000 (read-list-verbose in-fp)) (define l2000 (read-list-verbose in-fp)) (define l4000 (read-list-verbose in-fp)) (define l8000 (read-list-verbose in-fp)) (define l16000 (read-list-verbose in-fp)) (close-input-port in-fp) (define (sort-cmp l) (display "Sorting list with ") (display (length l)) (display " elements") (newline) (display "isort start (press [enter]):") (newline) (read-char) (isort l) (display "isort done") (newline) (display "mergesort start (press [enter]): ") (read-char) (mergesort l) (newline) (display "mergesort done") (newline)) (sort-cmp l1000) (sort-cmp l2000) (sort-cmp l4000) (sort-cmp l8000) (sort-cmp l16000)