scheme
Implementazione di diversi algoritmi di ordinamento

quicksort

Quicksort è un algoritmo di ordinamento comune con una complessità del caso medio di O(n log n) e una complessità del caso peggiore di O(n^2) . Il suo vantaggio rispetto ad altri metodi O(n log n) è che può essere eseguito sul posto.

Quicksort divide l'input su un valore pivot scelto, separando l'elenco in quei valori che sono inferiori a e quei valori che sono maggiori di (o uguali a) il pivot. Dividere la lista è facile con il filter .

Usando questo, l'implementazione di Schema di Quicksort potrebbe essere simile alla seguente:

(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

Unisci Ordina

Unisci ordinamento è un algoritmo di ordinamento comune con una complessità del caso medio di O(n log n) e una complessità del caso peggiore di O(n log n) . Sebbene non possa essere eseguito sul posto, garantisce la complessità di O(n log n) in tutti i casi.

Unisci Ordina divide ripetutamente l'input in due, finché non viene raggiunto un elenco vuoto o un elenco di elementi singoli. Avendo raggiunto la parte inferiore dell'albero di divisione, viene ripristinato, unendo le due suddivisioni ordinate l'una nell'altra, finché non viene lasciato un singolo elenco ordinato.

Utilizzando questo, un'implementazione Scheme di Merge Sort può essere simile alla seguente:

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