병합 정렬 : 혼합 요소가있는 목록 정렬

Question

저는 Scheme에서 병합 정렬을 작성하고 있습니다. 병합 정렬 정의, 목록을 분할하는 분할 자 및 목록을 병합하는 병합 있습니다.

(define mymergesort 
    (lambda (alist) 
    (if (null? (cdr alist)) alist 
     (let ((splits (splitter alist))) 
      (merge (mymergesort (car splits)) (mymergesort (cadr splits))))))) 

(define splitter 
    (λ (alist) (splitter-helper alist()()))) 

(define splitter-helper 
    (λ (alist list_a list_b) 
    (cond ((null? alist) (cons (reverse list_a) (cons list_b()))) 
      ((null? (cdr alist)) (cons (reverse (cons (car alist) list_a)) (cons list_b()))) 
      (else (splitter-helper (reverse (cdr (reverse (cdr alist)))) (cons (car alist) list_a) (cons (car (reverse (cdr alist))) list_b)))))) 

(define merge 
    (λ (list_a list_b) 
    (cond ((null? list_a) list_b) 
      ((null? list_b) list_a) 
      ((<= (car list_a) (car list_b)) (cons (car list_a) (merge (cdr list_a) list_b))) 
      ((<= (car list_b) (car list_a)) (cons (car list_b) (merge list_a (cdr list_b))))))) 

이 구현은 숫자 목록 정렬에 적합합니다. 하지만 혼합 된 요소 목록을 정렬 할 수 있기를 원합니다. 예를 들어

: '(I는 "갈"수 4 123 "에 대한"음료수 케이?)

어떤 제안/솔루션? 나는 또한 재귀 적 해결책을 둘러싼 "속임수"와 같은 대부분의 절차의 사용을 피하려고 노력 중이다.

Answer 1

이러한 항목의 순위를 매기는 '경험적'이 필요합니다. 예를 들어, "about"앞에 "go"가 올 것인가? 4는 어때? 그래서 정렬하고자하는 요소가 다른 요소에 대해 '< ='인지 확인하는 함수를 작성할 수 있습니다. 또한

(<= (car list_a) (car list_b)) 다음으로 (<= (car list_b) (car list_a))은 일종의 중복입니다. a가 < = b가 아니면 a> b를 알 수 있습니다.