scheme
다른 정렬 알고리즘의 구현

퀵 소트

Quicksort는 O(n log n) 의 평균 사례 복잡도와 O(n^2) 의 최악의 복잡도를 갖는 일반적인 정렬 알고리즘입니다. 다른 O(n log n) 메소드에 비해 장점은 내부에서 실행될 수 있다는 것입니다.

Quicksort는 입력을 선택한 피벗 값으로 분할하여 목록을 피벗보다 크거나 그 값보다 큰 값으로 분리합니다. filter 하여 목록을 쉽게 분할 할 수 있습니다.

이를 사용하여 Quicksort의 Scheme 구현은 다음과 같이 보일 수 있습니다.

(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

병합 정렬

정렬 병합 평균 케이스 복잡도 공통 정렬 알고리즘 O(n log n) 그리고 최악의 복잡도 O(n log n) . 즉석에서 실행될 수는 없지만 모든 경우에 O(n log n) 복잡성을 보장합니다.

정렬 병합을 반복하면 빈 목록이나 단일 요소 목록에 도달 할 때까지 입력을 두 개로 나눕니다. 분할 트리의 맨 아래에 도달하면, 정렬 된 하나의리스트가 남을 때까지 두 개의 정렬 된 분할을 서로 병합하여 다시 작동합니다.

이를 사용하여 스키마 정렬 병합 정렬은 다음과 같이 보일 수 있습니다.

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