2010-05-18 5 views
3

TI-Nspire에 대한 함수를 프로그래밍 중이므로 함수 내부에서 내장 함수를 사용할 수 없습니다. 목록 자체를 수정하지 않고 숫자 목록을 정렬하는 가장 일반적으로 효율적인 알고리즘은 무엇입니까? (재귀 및리스트 분할은 수학의 일반적인 사용과 마찬가지로 공정한 게임입니다.)효과적인 기능별 정렬

+1

을 언급 한 바와 같이

그래서 당신은 당신이 목록에'SortA'를 호출하려고 생각하지만, 계산기는 당신이 못하게 일반적인 정렬 알고리즘으로 사용할 수는 함수에 있기 때문에 그? 한숨. 이 문제는 TI-68k에도 존재합니다. –

+0

정확히 문제. 83 시리즈에는이 문제가 없지만 인수 전달이 내장되어 있지 않습니다. – muhmuhten

+0

도움이된다면 ticalc.org에서 다음 정렬 기능을 발견했습니다. http://www.ticalc.org/archives/files/fileinfo/429/42964.html –

답변

3

Mergesort는 간단하고 간단하며 효율적이며 안정적입니다. 목록을 분할하고 재귀 적으로 정렬 한 다음 결과를 병합합니다.

보다 구체적으로, mergesort는 점근 적으로 최적 인 O (N log N)을 취합니다. 또한, (두 알고리즘 모두 특수 목적 정렬을 사용하여 짧은 하위 목록을 정렬하도록 수정 한 경우) mergesort는 C/C++ 표준 라이브러리에서 사용되는 수정 된 퀵 정렬에 가까운 경쟁자가 될 수 있습니다.

편집 : quicksort 및 삽입 정렬과 같은 내부 정렬과는 달리, mergesort는 보조 메모리가 필요하며 스왑 대신 복사하여 구현하는 것이 가장 간단합니다.

+0

목록을 수정할 수 있다면 quicksort를 제안 할 것입니다. 평균 메모리 사용량은 적지 만,이 경우에는 mergesort를 사용하는 것이 좋습니다. –

+0

@Justin Peel : 빠른 정렬의 순진한 구현은 대용량 데이터의 병합 정렬보다 쉽게 ​​느려질 것입니다. AFAIK, 효율적인 빠른 정렬은 빠른 정렬 + 피벗의 피벗 선택 + 힙 정렬에 대한 대체 (인트로 정렬 참조)를 의미합니다. 그렇지 않으면, 내 경험상, 순수한 빠른 정렬은 병합 정렬에 비해 잘 수행되지 않습니다. – Giorgio

0

Timsort은 python 및 java SE 7에서 사용됩니다. 병합 정렬 및 삽입 정렬이 가장 좋습니다. 삽입 정렬은 O (n^2)이지만 작은 숫자 목록을 사용하면 병합 정렬보다 빠릅니다! here

+1

이 모든 것을 읽는 것을 좋아하지는 않지만 병합 및 삽입 정렬이 가장 좋으며 삽입 정렬을 사용하면 값이 바뀔 수 있다고 생각하면 timsort에 수정이 필요합니까? – muhmuhten

+1

Timsort는 훌륭하지만, 계산기에서 좋은 정렬을 얻는 것보다 훨씬 복잡하다고 생각합니다. –