scheme
Реализация различных алгоритмов сортировки

Quicksort

Quicksort - это общий алгоритм сортировки со средней сложностью случая O(n log n) и наихудшая сложность O(n^2) . Его преимуществом по сравнению с другими методами O(n log n) является то, что он может быть выполнен на месте.

Quicksort разбивает вход на выбранное значение поворота, разделяя список на те значения, которые меньше, и те значения, которые больше (или равны) оси вращения. Разделение списка легко выполняется с помощью filter .

Используя это, реализация схемы Quicksort может выглядеть следующим образом:

(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

Сортировка слиянием

Merge Sort - общий алгоритм сортировки со средней сложностью случая O(n log n) и наихудшая сложность O(n log n) . Хотя он не может быть выполнен на месте, он гарантирует во всех случаях сложность O(n log n) .

Merge Sort неоднократно разбивает входные данные на два, пока не будет достигнут пустой список или список из одного элемента. Достигнув дна дерева расщепления, он затем работает обратно, слияние двух отсортированных разделов друг с другом, пока не останется один отсортированный список.

Используя это, реализация схемы Merge Sort может выглядеть следующим образом:

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