c언어 병합정렬 구현하려는데 도움부탁드립니다

Question

#include #include void merge(int ar[], int num); int main(void) { int array[7]={ 3, 5, 1, 6, 9, 2, 4}; merge(array,7); printf("array is "); for(int i=0;i<7;i++) { printf("%d ",array[i]); } printf(" "); } void merge(int ar[], int num) { int end=0,intersection=0,left_num=0,right_num=0; int merged[num]; printf("num is %d ",num); if(num==1) { return; } intersection=(num)/2; int left[intersection], right[num-intersection]; for(int i=0;i

나도이젠맥북오우너 · Answer

Wiki 에 머지소트라고 치면 슈도코드 혹은 실제 각 언어별로구현된 코드가 나올겁니다!복 붙

bot99 · Answer

병합정렬은 다음과 같이, 양쪽의 정렬이 진행된 다음에 이를 크기 순서대로 통합하는 과정이 들어가야 합니다. 위의 소스코드에는 그 과정이 빠져 있군요. 병합정렬(왼쪽부분)병합정렬(오른쪽부분)병합(왼쪽의 정렬된 부분, 오른쪽의 정렬된 부분)그리고 left, right는 굳이 따로 쪼개서 만들어 넘겨줄 필요가 없습니다. 인덱스로 범위를 지정하여 넘겨줄 수도 있고, 포인터에 익숙하다면 각 부분의 처음 위치를 가리키는 포인터 주소를 넘겨줘도 되고...병합을 진행할 때에는, 왼쪽 부분과 오른쪽 부분의 길이를 합친 만큼 버퍼를 만들고, 여기에 하나씩 복사해 가면서 병합한 다음에, 이를 원래 위치(왼쪽의 정렬된 위치)에 써 넣는 식으로 합니다.이때 malloc로 일일이 공간을 할당하고 해제해가며 진행하면 시간이 많이 걸리기 때문에, 원래 배열과 같은 크기의 버퍼를 만들어두고 이걸 함수인자로 그대로 넘겨주거나 하면서 진행하는게 보통입니다.병합정렬은 널리 알려진 정렬이고 자료도 많은 편이라, 검색하셔서 찾을 수 있는 자료들보다 더 쉽게 설명해 드리기도 어렵군요. 차근차근 기존 소스코드 따라해가며 이해해 보시길 바랍니다.https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

c언어 병합정렬 구현하려는데 도움부탁드립니다

2개의 답변

기타 목록