DrScheme의 Quicksort

Question

저는 현재 Lisp 및 DrScheme과 같은 기능 언어를 학습하는 중이지만 DrScheme에 Quicksort 알고리즘의 차이점을 쓰도록 요청 받았습니다. 그러나, 나는 어디에서 시작 해야할지 단서가 없다.

누군가 내게 어떤 함수 및 데이터 유형으로 사용할 포인터를 줄 수 있습니까? 나는 명부, 차, cdr 및 append가 할 것이다 것으로 거대한 부분을하기 위하여려고하고 있다는 것을 분명하게 알고있다.

그건 그렇고, 나는 단지 발사 일반 아이디어를 찾고 있습니다. 나는 반드시 완전한 답을 원한다. 일종의 모험과 재미를 망치고!

Answer 1

Quicksort는 기능 스타일로 구현되는 가장 간단한 정렬 알고리즘 중 하나입니다.

quicksort(lst) 
    if lst is empty 
     return empty list 
    return quicksort([all the elements < first element in lst]) 
      + [first element in lst] + 
      quicksort([all the elements >= first element in lst]) 

은 "까다로운"일부 덜 모든 요소를 ​​점점 : 당신이 필요로하는 유일한 데이터 구조는 표준 리스프 목록입니다 알았어, 오름차순으로 번호 목록을 정렬을위한 출발점으로이 의사 코드를 사용하여 목록의 첫 번째 요소보다 (또는 그 이상의 모든 요소가) filter 절차로 쉽게 표현 될 수 있습니다. 사용이 허락되지 않는다면 처음부터 기본 기능을 구현하기 쉽습니다.

내 가상 코드의 연산자는 append이며 목록의 첫 번째 요소보다 작은 요소 목록, 목록의 첫 번째 요소가있는 싱글 톤 목록 (피벗) 및 목록 목록의 첫 번째 요소보다 크거나 같은 요소를 반환합니다.

실제로 Quicksort를 구현할 때 적절한 피벗 요소를 선택하는 데 더 많은주의를 기울이지 만이 간단한 예제에서는 첫 번째 요소를 사용하기에 충분합니다.