C++ MergeSort 관련 질의

Question

Mergesort 를 할 때에 예를 들어 {'A','G','F','B'} 가 있다고 하면 {A,G} / {F/B} 를 다시 하나로 쪼개서 합병을 하는것으로 알고 있는데 {A,G} 의 경우는 A가 G 보다 작으므로 굳이 합병을 하지 않아도 된다고 생각됩니다.위와 같은 예처럼 Merge 함수를 굳이 부를 필요가 없을 때 아래 코드에서 어떤 코드를 더 추가해야하는지 궁금합니다.#include using namespace std; void merge(char *a, char *aux, int lo, int mi, int hi) { for (int k = lo; k <= hi; k++) aux[k] = a[k]; int i = lo; int j = mi + 1; for(int k = lo; k <= hi; k++) { if (i > mi) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (aux[j] < aux[i]) a[k] = aux[j++]; else a[k] = aux[i++]; } } void mergeSort(char *a, char *aux, int N, int lo, int hi){ if (hi <= lo) return; int mi = lo + (hi - lo) / 2; mergeSort (a, aux, N, lo, mi); mergeSort (a, aux, N, mi + 1, hi); merge(a, aux, lo, mi, hi); }

지붕뚫고높이차 · Answer

.

KOR YS · Answer

지붕뚫고높이차 님 댓글이 보이지 않습니다 ㅠㅠ

지붕뚫고높이차 · Answer

A, G 는 정렬하지 않아도 된다고 하셨는데이미 무의식적으로 A 가 G 보다 작음을 비교했기 때문에 말 할 수 있는 겁니다. 컴퓨터도 똑같습니다. A 가 G 보다 작음을 알 수 있도록 비교 연산이 필요하지 않을까요? ^^

KOR YS · Answer

그렇다면 이렇게 하면 될까요?mergeSort (a, aux, N, lo, mi); mergeSort (a, aux, N, mi &#43; 1, hi); if(a[lo] < a[hi]) return 0; merge(a, aux, lo, mi, hi);

C++ MergeSort 관련 질의

4개의 답변

#mergesort 목록