scheme
異なるソートアルゴリズムの実装

クイックソート

クイックソートは、 O(n log n)平均ケース複雑度とO(n^2)最悪ケース複雑度を持つ一般的なソートアルゴリズムです。他のO(n log n)メソッドよりもその利点は、インプレースで実行できることです。

クイックソートは、選択したピボット値で入力を分割し、リストをピボットよりも小さい値とピボットより大きい（または等しい）値に分割します。リストを分割することはfilter簡単に行え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)複雑さが保証されます。

マージソートは、空のリストまたは単一要素のリストに達するまで、繰り返し入力を2つに分割します。分割ツリーの一番下に到達した後、分割された2つの分割を1つのソートされたリストが残されるまで、マージして元の状態に戻ります。

これを使用して、マージソートのScheme実装は次のようになります。

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