효과적인 기능별 정렬

Question

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

Answer 1

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

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

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

Answer 2

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