보통 2-way mergesort를 많이 하는데
3-way, k-way등이 있는데 왜 mergesort하면 2-way를 주로 쓸까요??
시간복잡도는 3-way쪽이 더 낮을 것 같은데...
recursion할때 스택이 과도하게 많이 잡혀서 그런건가요?
sorting 계산의 시간 복잡도의 lower bound는
binary compare 를 사용하는 이상 nlog2n 입니다.
k-way merge를 하더라도 병합하는 횟수는 줄어들지만
어쨌거나 nlog2n 번의 계산을 해야 합니다.
그러니 좀 더 간단한 걸 선호하는 경향이 있기도 하고...
사실 "주로 쓴다"는 표현은 좀 애매한 것이,
입력 데이터의 특성이나 시스템 특성에 따라 선호되는 sorting 알고리즘이 다르니까요.
대게 k-way merge는 병렬처리 때 쓰죠. 제가 알기로는 k개로 쪼개고, 각 부분을 QuickSort를 한 후 k-way merge 하는 것이 괜찮은 것으로 압니다. Stable sort가 필요하다면 그냥 merge sort로만 처리해야겠지만...
그리고 recursion 깊이는 k가 커질수록 얕야집니다. 따라서 3-way가 2-way 보다 보통 stack을 덜 먹죠.
3-way를 포함해서 k-way merge는 merge를 위한 과정이 복잡해지니까 교육용으로는 잘 안 쓰이는 거겠죠.
관련해서 정확한 비교는 논문찾아보시면 될 듯... 꽤 오래된 논문일 것 같군요.
모 대학 알고리즘 과제인가요?ㅋㅋ
kldp에 물어보다니 좋은 생각이네요♡
고마워요~ 전 희연 학생과 가까운 사람이에요ㅋㅋ
sorting 계산의 시간
sorting 계산의 시간 복잡도의 lower bound는
binary compare 를 사용하는 이상 nlog2n 입니다.
k-way merge를 하더라도 병합하는 횟수는 줄어들지만
어쨌거나 nlog2n 번의 계산을 해야 합니다.
그러니 좀 더 간단한 걸 선호하는 경향이 있기도 하고...
사실 "주로 쓴다"는 표현은 좀 애매한 것이,
입력 데이터의 특성이나 시스템 특성에 따라 선호되는 sorting 알고리즘이 다르니까요.
k-way로 만들고 2-way wrapper를 만드는 것도 괜찮을 듯...
대게 k-way merge는 병렬처리 때 쓰죠.
제가 알기로는 k개로 쪼개고, 각 부분을 QuickSort를 한 후 k-way merge 하는 것이 괜찮은 것으로 압니다.
Stable sort가 필요하다면 그냥 merge sort로만 처리해야겠지만...
그리고 recursion 깊이는 k가 커질수록 얕야집니다.
따라서 3-way가 2-way 보다 보통 stack을 덜 먹죠.
3-way를 포함해서 k-way merge는 merge를 위한 과정이 복잡해지니까 교육용으로는 잘 안 쓰이는 거겠죠.
관련해서 정확한 비교는 논문찾아보시면 될 듯... 꽤 오래된 논문일 것 같군요.
박희연 학생 과제는 스스로 하세요
모 대학 알고리즘 과제인가요?ㅋㅋ
kldp에 물어보다니 좋은 생각이네요♡
고마워요~ 전 희연 학생과 가까운 사람이에요ㅋㅋ