scheme
Implementación de diferentes algoritmos de clasificación.

Ordenación rápida

Quicksort es un algoritmo de clasificación común con una complejidad de caso promedio de O(n log n) y una complejidad de caso más desfavorable de O(n^2) . Su ventaja sobre otros métodos O(n log n) es que puede ejecutarse in situ.

Quicksort divide la entrada en un valor de pivote elegido, separando la lista en aquellos valores que son menores que y aquellos valores que son mayores que (o iguales a) el pivote. La división de la lista se hace fácilmente con filter .

Usando esto, una implementación de Scheme de Quicksort puede parecerse a la siguiente:

(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

Combinar clasificación

Merge Sort es un algoritmo de clasificación común con una complejidad de casos promedio de O(n log n) y una complejidad de caso más desfavorable de O(n log n) . Aunque no se puede ejecutar en el lugar, garantiza la complejidad de O(n log n) en todos los casos.

La ordenación de combinación divide repetidamente la entrada en dos, hasta que se alcanza una lista vacía o una lista de un solo elemento. Una vez que ha alcanzado la parte inferior del árbol de división, luego vuelve a su camino ascendente, fusionando las dos divisiones clasificadas una en la otra, hasta que quede una sola lista ordenada.

Usando esto, una implementación de Esquema de Merge Sort puede parecerse a la siguiente:

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