시간 데이터가 포함 된 거의 정렬 된 목록에 대한 효율적인 정렬 알고리즘은 무엇입니까?

Question

이름은 모두 그것을 정말로 말한다. 삽입 정렬은 일반적으로 대부분 정렬 된 데이터의 가장 좋은 정렬이기 때문에 최상의 것으로 판단됩니다. 그러나 데이터에 대해 더 많이 알고 있기 때문에 다른 유형의보고가있을 가능성이 있습니다. 따라서 다른 관련 정보는 다음과 같습니다.

1) 이것은 시간 데이터입니다. 이는 데이터 정렬에 효과적인 해시를 생성 할 수 있다고 판단 할 수 있음을 의미합니다. 2) 데이터가 한 번에 모두 존재하지는 않습니다. 대신에 하나의 벡터 또는 수십 또는 수백 개의 벡터를 포함 할 수있는 레코드를 읽을 것입니다. 나는 5 초 안에 모든 시간을 출력하고 싶다. 따라서 데이터를 삽입 할 때 정렬을 수행하는 것이 더 나은 옵션 일 수 있습니다. 3) 메모리는 큰 문제는 아니지만 CPU 속도는 시스템의 병목 현상 일 수 있습니다.

누구나 삽입 정렬 외에도 고려할 가치가있는 알고리즘을 제안 할 수 있습니까? 또한, 좋은 정렬 옵션이 무엇인지 결정하기 위해 '대부분 정렬'된 방법은 무엇입니까? 내가 의미하는 바는 내 데이터를보고 '이것이 삽입 정렬이 더 이상 최선의 옵션이 아닌 것처럼 생각한만큼 정렬되지 않았 음'을 결정하는 것입니다. 학위 데이터와 관련된 복잡성을보다 잘 정의하는 프로세스 복잡성을 고려한 아티클에 대한 링크는 모두 이해할 수 있습니다.

감사

편집

는 : 귀하의 정보를 당신에게 모두 감사합니다. 나는 쉬운 삽입 또는 병합 정렬 (어느 것이 든 내가 이미 미리 쓴 것)으로 갈 것이다. 그러나 일단 다른 방법을 시도해 보겠습니다 (구현에 더 많은 노력을 기울이기 때문에) 최적화 단계에 가까워졌습니다. 도움을 주셔서 감사합니다.

Answer 1

제안한 옵션 (2)을 채택 할 수 있습니다. 요소를 삽입하는 동안 데이터를 정렬하십시오.

시간을 기준으로 정렬 된 skip list을 사용하여 오름차순으로 데이터를 유지 관리하십시오.

• 새로운 입장이 도착하면 - 그것은 마지막 요소 (쉽고 빠르게) 후 큰 경우가 있는지 확인 - 단순히 (스킵 목록에서 쉽게 할 수) 추가합니다. 건너 뛰기 목록은이 경우에 평균 2 개의 노드를 추가해야하며 O(1)에 이됩니다.
• 요소가 마지막 요소보다 크지 않은 경우 - O(logn)이 될 표준 삽입 연산으로 건너 뛰기 목록에 추가하십시오.

이 방법을 사용하면 O(n+klogn) 알고리즘이 생깁니다. 여기서 k은 순서가 잘못 삽입 된 요소의 수입니다.

Answer 2

자연 버전을 구현하는 경우 O(N)의 우수 사례와 O(N log N)의 우수 사례가있는 경우 문제가있는 경우이를 던집니다. 삽입하면 최악의 경우는 O(N^2)이고 가장 좋은 경우는 O(N)입니다.

Answer 3

대부분 정렬 된 데이터를 정렬하도록 특별히 설계된 많은 적응 형 정렬 알고리즘이 있습니다. 날짜를 저장한다는 사실을 무시하고 최악의 경우 O (n log n) 시간 및 최상의 경우 O (n)으로 정렬 된 데이터를 정렬 할 수있는 알고리즘으로 smoothsort 또는 데카르트 트리 정렬을 볼 수 있습니다. 시각. Smoothsort는 삽입 정렬과 같은 O (1) 공간 만 필요로한다는 장점이 있습니다.

모든 것이 날짜이며 따라서 정수로 변환 될 수 있다는 사실을 이용하여 3 중 피벗 선택을 사용하여 2 진 퀵 정렬 (MSD 기수 정렬)을 살펴볼 수 있습니다. 이 알고리즘은 최상의 케이스 O (n log n) 성능을 갖지만 매우 경쟁력있는 매우 낮은 상수 계수를가집니다. 최악의 경우는 O (n log U)입니다. 여기서 U는 각 날짜의 비트 수 (아마도 64)입니다. 너무 나쁘지는 않습니다.

희망이 도움이됩니다.

Answer 4

OS 또는 C 라이브러리가 mergesort 기능을 제공하는 경우 지정된 데이터가 O (N) 시간에 부분적으로 (모든 방향으로) 정렬 된 경우를 처리 할 가능성이 매우 높습니다.

그렇지 않으면 좋아하는 BSD 운영 체제에서 사용할 수있는 mergesort를 복사 할 수 있습니다.

Answer 5

문제를 완전히 이해하지 않고 데이터가 대부분 정렬되어 있다고 주장 할 때 Timsort이 청구서에 부합 할 수 있습니다.

Answer 6

n의 목록을 k 개의 요소로 정렬 할 수 있습니다 (O(n + k lg k) 시간).

참조 : http://www.quora.com/How-can-I-quickly-sort-an-array-of-elements-that-is-already-sorted-except-for-a-small-number-of-elements-say-up-to-1-4-of-the-total-whose-positions-are-known/answer/Mark-Gordon-6?share=1는

기본 개념이있다 : 증가 시퀀스를 (건물 배열의 요소 위에

가

• 대하여 반복 현재 요소의 최종 요소보다 크거나 같으면 그 서브 시퀀스를 서브 시퀀스의 끝에 추가한다. 그렇지 않으면, 현재의 요소와 서브 시퀀스의 마지막 요소를 모두 버린다. 이 시간은 O(n)입니다.
• 요소가 부재하기 때문에 사용자는 2k 개 요소를 버려야합니다.
• 병합 정렬 또는 힙 정렬과 같은 O(k lg k) 정렬 알고리즘을 사용하여 버려진 2k 요소를 정렬합니다.
• 이제 두 개의 정렬 된 목록이 있습니다. 병합 정렬의 병합 단계에서와 같이 O(n) 시간에 목록을 병합하십시오.

전체 시간 복잡도 = O(n + k lg k)

전체 공간의 복잡성 = O(n)

(이것은 당신이 O(1) 공간에 병합 할 수 있습니다 경우 O(1) 공간에서 실행하도록 수정 될 수 있지만 사소한 의미하여이 없다)