scheme
Implementatie van verschillende sorteeralgoritmen

Snel sorteren

Quicksort is een algemeen sorteeralgoritme met een gemiddelde case-complexiteit van O(n log n) en een worst case-complexiteit van O(n^2) . Het voordeel ten opzichte van andere O(n log n) -methoden is dat het ter plekke kan worden uitgevoerd.

Quicksort splitst de invoer op een gekozen spilwaarde, waarbij de lijst wordt onderverdeeld in die waarden die kleiner zijn dan en die waarden die groter zijn dan (of gelijk zijn aan) de spil. Het splitsen van de lijst is eenvoudig gedaan met filter .

Hiermee kan een Scheme-implementatie van Quicksort er als volgt uitzien:

(define (quicksort lst)
  (cond
    ((or (null? lst) ; empty list is sorted
         (null? (cdr lst))) ; single-element list is sorted
     lst)
    (else
      (let ((pivot (car lst)) ; Select the first element as the pivot
            (rest (cdr lst)))
        (append
          (quicksort ; Recursively sort the list of smaller values
            (filter (lambda (x) (< x pivot)) rest)) ; Select the smaller values
          (list pivot) ; Add the pivot in the middle
          (quicksort ; Recursively sort the list of larger values
            (filter (lambda (x) (>= x pivot)) rest))))))) ; Select the larger and equal values

Sorteren samenvoegen

Sorteren samenvoegen is een algemeen sorteeralgoritme met een gemiddelde case-complexiteit van O(n log n) en een worst case-complexiteit van O(n log n) . Hoewel het niet ter plekke kan worden uitgevoerd, garandeert het in alle gevallen O(n log n) -complexiteit.

Sorteer samenvoegen splitst de invoer herhaaldelijk in twee, totdat een lege lijst of een lijst met één element is bereikt. Nadat het de onderkant van de splitsingsboom heeft bereikt, werkt het vervolgens terug naar boven, waarbij de twee gesorteerde splitsingen in elkaar worden samengevoegd, totdat er een enkele gesorteerde lijst overblijft.

Hiermee kan een Scheme-implementatie van Merge Sort er als volgt uitzien:

;; Merge two sorted lists into a single sorted list
(define (merge list1 list2)
  (cond
    ((null? list1)
     list2)
    ((null? list2)
     list1)
    (else
      (let ((head1 (car list1))
            (head2 (car list2)))
        ; Add the smaller element to the front of the merge list
        (if (<= head1 head2)
          (cons
            head1
            ; Recursively merge
            (merge (cdr list1) list2))
          (cons
            head2
            ; Recursively merge
            (merge list1 (cdr list2))))))))

(define (split-list lst)
  (let ((half (quotient (length lst) 2)))
    ; Create a pair of the first and second halves of the list
    (cons
      (take lst half)
      (drop lst half))))

(define (merge-sort lst)
  (cond
    ((or (null? lst) ; empty list is sorted, so merge up
         (null? (cdr lst))) ; single-element list is sorted, so merge up
     lst)
    (else
      (let ((halves (split-list lst)))
        ; Recursively split until the bottom, then merge back up to sort
        (merge (merge-sort (car halves))
               (merge-sort (cdr halves)))))))