scheme
Implementering av olika sorteringsalgoritmer

quick

Quicksort är en vanlig sorteringsalgoritm med en genomsnittlig fallkomplexitet för O(n log n) och ett värsta fallskomplexitet för O(n^2) . Dess fördel jämfört med andra O(n log n) -metoder är att det kan köras på plats.

Quicksort delar ingången på ett valt pivotvärde och delar listan i de värden som är mindre än och de värden som är större än (eller lika med) pivot. Dela upp listan görs enkelt med filter .

Med hjälp av detta kan en schemaimplementering av Quicksort se ut så här:

(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

Slå samman

Merge Sort är en vanlig sorteringsalgoritm med en genomsnittlig fallkomplexitet för O(n log n) och ett värsta fall komplexitet för O(n log n) . Även om det inte kan köras på plats, garanterar det O(n log n) komplexitet i alla fall.

Merge Sort delar upp ingången upprepade gånger i två, tills en tom lista eller en-elementlista nås. Efter att ha nått botten av klyvträdet, arbetar det sedan uppåt igen, sammanfogar de två sorterade delningarna i varandra tills en enda sorterad lista är kvar.

Med hjälp av detta kan en schemaimplementering av Merge Sort se ut enligt följande:

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