1
교수님이 3 학급 파티셔닝 및 병합으로 배열에서 mergesort를 구현하는 것으로 수업을 지정했습니다.3 파티션 mergesort
교수님의 정확한 질문이었습니다. 문제는 3 방향 mergesort와 같은 것을 발견하지 못했습니다. 3 방향 quicksort에 대해서만 알고 있습니다. 그래서 그는 아마 배열을 취하고, 3 부분으로 나눈 다음, 3 부분을 병합하고, 첫 번째 두 부분을 병합 한 다음 결합 된 부분을 세 번째 부분과 병합하여이 작업을 수행합니다.
정확하게 생각했는데 올바른 일을 했습니까 (이미 구현되었지만 내 질문과 관련이 없으므로 코드를 게시하지 않았습니다) 또는 잘못 이해했으며 내가 알지 못하는 3-way mergesort.
는교수는 우리에게 이것에 대해 매우 회의적 내가 너희되면 등 구글에서만큼 내가 할 수있는 등
나는 실제로 3 개의 각 하나에 대해 Arrays.sort를 사용하고 그런 다음 내가 말한대로 쌍으로 병합합니다. 당신이 내게 말한 것에 관해서는 한 번에 할 수 있다고 생각했지만 너무 복잡해 보였습니다. 그래서 나는 첫 번째 단계가 처음 두 부분의 병합 된 배열을 반환하는 반면 두 단계로 수행했습니다. 내 주요 질문에 관해서는 실제로 그것을 올바르게하고 있습니까? 아니면 내가 한 일과 관련이없는 3-way mergesort를 구현할 수있는 방법이 있습니까? –
정렬을하기 위해'Arrays.sort()'를 호출한다면, 당신은 merge-sort를하지 않을 것입니다. (호출이 그렇게하지 않는다면 보장되지 않습니다). Merge-sort는 두 번째 단락에서 설명하는대로 재귀 적으로 작은 배열을 재귀 적으로 호출하는 함수입니다. 물론 한꺼번에 두 배열을 병합 할 수는 있지만 한 번에 세 개를 병합하면 몇 가지 성능상의 이점이 있습니다. – Attila
그래서 3 개의 하위 배열을 만든 후에는 각 배열을 개별적으로 마지막 단계에서 한 번에 3 부분을 모두 합치거나 아니면 이와 비슷한 질문을 할 수있을 것입니다. http://stackoverflow.com/questions/2224492/mergesort-beginner-question. 그런데도 그는 아직 대답하지 못했습니다 –