scheme
Implémentation de différents algorithmes de tri

Tri rapide

Quicksort est un algorithme de tri commun avec une complexité de cas moyenne de O(n log n) et une complexité de cas le plus défavorable de O(n^2) . Son avantage par rapport aux autres méthodes O(n log n) est qu’il peut être exécuté sur place.

Quicksort divise l'entrée sur une valeur de pivot choisie, en séparant la liste des valeurs inférieures et supérieures (ou égales) au pivot. La division de la liste se fait facilement avec le filter .

En utilisant cela, une implémentation Scheme de Quicksort peut ressembler à ceci:

(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

Tri par fusion

Merge Sort est un algorithme de tri commun avec une complexité de cas moyenne de O(n log n) et une complexité de cas le plus défavorable de O(n log n) . Bien qu'il ne puisse pas être exécuté sur place, il garantit la complexité de O(n log n) dans tous les cas.

Fusionner le tri divise de manière répétée l'entrée en deux, jusqu'à ce qu'une liste vide ou une liste d'éléments uniques soit atteinte. Après avoir atteint le bas de l’arbre de fractionnement, celui-ci se remet à remonter, fusionnant les deux divisions triées les unes avec les autres, jusqu’à ce qu’une seule liste triée soit laissée.

En utilisant ceci, une implémentation Scheme de Merge Sort peut ressembler à ceci:

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