scheme
Implementacja różnych algorytmów sortowania

Szybkie sortowanie

Quicksort jest popularnym algorytmem sortowania ze średnią złożonością przypadku O(n log n) i najgorszą złożonością przypadku O(n^2) . Jego przewaga nad innymi metodami O(n log n) polega na tym, że można go wykonać w miejscu.

Quicksort dzieli dane wejściowe na wybraną wartość przestawną, dzieląc listę na te wartości, które są mniejsze i te, które są większe niż (lub równe) przestawne. Podziału listy można łatwo dokonać za pomocą filter .

Dzięki temu implementacja schematu Quicksort może wyglądać następująco:

(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

Scal sortowanie

Scalanie sortowania jest powszechnym algorytmem sortowania ze średnią złożonością przypadku O(n log n) i najgorszą złożonością przypadku O(n log n) . Chociaż nie można go wykonać w miejscu, gwarantuje on złożoność O(n log n) we wszystkich przypadkach.

Scal sortowanie wielokrotnie dzieli dane wejściowe na dwie części, aż do osiągnięcia pustej listy lub listy pojedynczych elementów. Po dotarciu do dolnej części rozdzielającego drzewa przesuwa się z powrotem w górę, łącząc dwa posortowane podziały ze sobą, aż pozostanie jedna posortowana lista.

Korzystając z tego, implementacja Scal sortowania może wyglądać następująco:

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