거의 정렬 된 목록을 다시 정렬하는 데 가장 적합한 정렬 알고리즘은 무엇입니까?

Question

특정 비교 함수로 정렬 된 문자열 목록이 있습니다.

이제 비교 기능을 사용하여이 목록을 다시 정렬해야합니다.

이 새로운 비교 함수는 Umlaut와 같은 특정 특수 문자를 비교할 때 약간 다르게 작동합니다. 대부분의 경우 요소는 올바른 위치로 이동하기 위해 단지 하나 또는 두 개의 슬롯으로 이동되어야합니다.

어떤 정렬 알고리즘이 거의 완벽하게 정렬 된 목록을 런타임 실행 속도 측면에서 재사용하는 데 가장 적합합니까?

Answer 1

Insertion sort은 작거나 거의 정렬 된 목록에서 잘 작동합니다. 이 ACM Paper에서

: 목록 길이 작은 정렬도 비율의 다양한 조합의 무작위로 생성 된 목록에

테스트 표시 똑바로 삽입 작거나 매우 거의 정렬 된 목록 그에 대한 일종의 최고의 Quickersort는 가장 좋은 방법은 입니다. 위키 문서 Insertion sort 가입일

: 입력 배열이 이미 분류되어있는 경우

가

가 삽입 정렬 따라서 주어진 때 삽입 정렬을보다 효율적으로 만들기 적은 N-1과 비교를 행한다는 정렬하거나 "거의 정렬 된"배열.

SO 질문 : Is there ever a good reason to use Insertion Sort?

Answer 2

모두 검색 작업에 액세스 할 수 있나요? 그렇다면 첫 번째 정렬 과정에서 일부 해시 트리를 만들어 다른 정렬 작업에 사용할 수 있습니다.

Answer 3

데이터 목록이 모두 정렬되어 있습니다 (ASCII/국가 문자 집합 순서로 말하면 됨). 일부 사전 규칙은없는 것으로 알고 있습니다. 특정 국가에 적용됩니다. 예를 들어 독일과 모음 변이를 들어

당신이 새 항목을 삽입하지 않는

위키 피 디아

에 Germanic_umlaut를 참조하십시오, 당신은 단지 조금 더 엄격한 분류 규칙에 의해 그것들을 의지합니다.

여기 예를 들어 읽을 수

http://www.softpanorama.org/Algorithms/Sorting/bubblesort.shtml

버블 정렬은 단지 몇 순열과 allready 분류 목록에서 잘 작동한다. 이것은 버블 정렬이 좋은 알고리즘 인 것처럼 들립니다. 또한 버블 정렬은 "안정적인"정렬 알고리즘임을 유의하십시오. 이는 시나리오에서 중요 할 수 있습니다.

Answer 4

거의 정렬 된 목록의 경우 Comb의 변형이 Quicksort를 능가합니다. 콤 정렬을 삽입 정렬과 비교하는 방법을 테스트하지 않았습니다.