많은 텍스트 북에서 맨 위 병합 정렬은 랜덤 액세스의 이점을 고려한 배열로 수행됩니다.다른 데이터 구조와 병합 정렬 하시겠습니까?
다른 데이터 구조로 병합 정렬을 수행하는 방법이 있는지 궁금합니다. 데이터가 대기열 또는 스택에 저장되어 있다고 가정하면 대기열/스택에서 병합 정렬을 수행하여 최대 보조 대기열/스택을 추가 할 수 있습니까?
내 관심사는 임의 액세스가 없기 때문에이 경우 정렬을 병합해도 O (n 로그인) 효율에 도달 할 수 있다는 것입니다.
병합 정렬을 사용하여 배열을 사용할 때의 또 다른 이점은 영리한 (그러나 이해할 수없는) 알고리즘을 작성하면 재귀 호출 수준간에 "스크래치"배열과 "실제"배열을 전환 할 수 있다는 것입니다. 소금의 가치가있는 병합 정렬의 구현에서는 "스크래치"배열을 한 번만 할당하지만 전환 기법을 사용하면 결과를 한 번만 이동하면됩니다.
스택과 대기열을 사용하면 어쨌든 배열을 기본 데이터 구조로 사용할 수 있습니다. 연결된 목록을 사용할 수 있지만 상수 요인은 push() 및 pop() 또는 enqueue() 및 dequeue()으로 커지며 항목에 대한 메모리도 할당해야합니다. 분명히, @LearnedfromMustake이 보여 주듯이, 스택과 큐를 사용하는 것이 가능하지만 어쨌든 배열이 기본 데이터 구조로 사용되기 쉽기 때문에 그런 접근 방식의 이점이 무엇인지는 분명하지 않습니다.
O (* n * lg * n *) 시간에 연결된 목록에서 병합 정렬을 수행 할 수 있습니다. 사실, 링크드 목록 정렬 알고리즘 AFAIK입니다. –
병합 정렬에 임의 액세스가 필요하지 않으므로 주 관심사가 무엇인지 잘 모릅니다. –
@KarolyHorvath하지만 배열 버전에서 반으로 배열을 분할하는 것은 확실히 임의 액세스 권한이 필요합니까? 내 말은 연결된 목록에서 중간에 도달하기 위해 몇 가지 트릭을 사용할 수 있지만 O (n) 시간이 걸리는 것입니까? – Enzo