scheme
Implementierung verschiedener Sortieralgorithmen

Schnelle Sorte

Quicksort ist ein allgemeiner Sortieralgorithmus mit einer durchschnittlichen Fallkomplexität von O(n log n) und einer Worst-Case-Komplexität von O(n^2) . Der Vorteil gegenüber anderen O(n log n) -Methoden besteht darin, dass sie direkt ausgeführt werden kann.

Quicksort teilt die Eingabe für einen ausgewählten Pivotwert auf, wobei die Liste in die Werte unterteilt wird, die kleiner als der Pivotwert sind. Das Aufteilen der Liste erfolgt einfach mit einem filter .

Eine Schema-Implementierung von Quicksort kann folgendermaßen aussehen:

(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

Zusammenführen, sortieren

Merge Sort ist ein allgemeiner Sortieralgorithmus mit einer durchschnittlichen Fallkomplexität von O(n log n) und einer Worst-Case-Komplexität von O(n log n) . Obwohl es nicht direkt ausgeführt werden kann, ist die Komplexität von O(n log n) in allen Fällen gewährleistet.

Merge Sort teilt die Eingabe wiederholt in zwei Teile, bis eine leere Liste oder Einzelelementliste erreicht wird. Wenn Sie den unteren Teil des Aufteilungsbaums erreicht haben, arbeitet er sich wieder nach oben und verbindet die beiden sortierten Aufteilungen ineinander, bis eine einzige sortierte Liste übrig bleibt.

Wenn Sie dies verwenden, kann eine Schemaimplementierung von Merge Sort folgendermaßen aussehen:

;; 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)))))))