2010-11-23 11 views
1

목록을 증가하는 순서로 반환하는 정렬 알고리즘을 작성하는 방법.스키마에서 목록 정렬

예 : '(1 3 5 2 9) 반환'(1 2 3 5 9)

+0

질문은 이미 스택 오버플로에서 질문되었습니다. http://stackoverflow.com/questions/2527150/scheme-sorting-a-list – joce

답변

0

SRFI 95는 정렬 라이브러리를 제공합니다. 많은 Scheme 구현에는 정렬 라이브러리가 내장되어 있지만 모든 라이브러리가 SRFI 95 인터페이스를 준수하지는 않습니다. 당신이 당신의 자신의 구현을 작성해야하는 경우


, 당신은 머지 소트 또는 퀵와 같은 정렬 알고리즘 표준 중 하나를 사용한다 (숙제, 말). 그러나 두 알고리즘 모두 벡터 기반 알고리즘이므로 벡터에 목록을 복사하고 정렬 한 다음 다시 목록에 복사해야합니다. 벡터 조작에 유용한 SRFI 43, 특히 벡터의 두 요소를 교환하는 데 특히 vector-swap!을 찾을 수 있습니다.

링크 된 목록을 직접 정렬하는 데 적합한 알고리즘이있을 수 있습니다. 나는 그 (것)들에 au fait가 아니다, 그래서 나는 더 그 (것)들에 대하여 논평하지 않을 것이다.

+0

mergesort와 quicksort는 모두 목록을 매우 쉽게 구현할 수 있습니다. 목록을 탐색해야하는 일부 지점에서는 약간의 성능이 저하 될 수 있습니다. (동일한 수의 비교를 유지하더라도). – erjiang

2

대부분의 Scheme 구현에는 목록을 정렬하는 절차가 있습니다. 구현에서 제공하지 않으면 구현을 어렵지 않습니다. 다음은 빠른 정렬 알고리즘의 구현입니다.

> (define (qsort e) 
    (if (or (null? e) (<= (length e) 1)) e 
     (let loop ((left null) (right null) 
        (pivot (car e)) (rest (cdr e))) 
      (if (null? rest) 
       (append (append (qsort left) (list pivot)) (qsort right)) 
       (if (<= (car rest) pivot) 
        (loop (append left (list (car rest))) right pivot (cdr rest)) 
        (loop left (append right (list (car rest))) pivot (cdr rest))))))) 
> (qsort '(1 3 5 2 9)) 
=> (1 2 3 5 9) 
+0

이 프로그램의 작동 방식에 대해 좀 더 자세히 설명해 주시겠습니까? 나는 그런 식으로 일하는 것을 결코 보지 못했고 내가 말할 수있는 한 분명히 그렇게해서는 안된다. 루프가 전체 코드이므로 let 다음에 람다를 사용하지 않는 이유는 무엇입니까? 나는 왜 let이 사용되는지 모르겠다. –