DSSequence::merge 함수는 두 개의 정렬된 시퀀스를 병합하는 과정에서 중복된 원소를 제거하고 정렬된 상태를 유지합니다.
이 함수는 두 개의 시퀀스를 하나의 시퀀스로 합칠 때, 다음과 같은 과정을 거칩니다.
1. 두 개의 시퀀스를 나누어 각 시퀀스의 크기를 계산합니다.
2. 두 개의 시퀀스를 비교하여 작은 원소를 선택합니다.
3. 선택된 원소를 결과 시퀀스에 추가합니다.
4. 두 개의 시퀀스를 비교하여 작은 원소를 선택하는 과정을 반복합니다.
5. 한 개의 시퀀스가 끝날 때까지 작은 원소를 선택하는 과정을 반복합니다.
이러한 과정을 거치면 중복된 원소를 제거하고 정렬된 상태를 유지하는 결과 시퀀스가 생성됩니다.
이 함수는 정렬된 시퀀스를 병합하는 데 사용할 수 있습니다. 예를 들어, 두 개의 정렬된 리스트를 병합하는 데 사용할 수 있습니다.
#hostingforum.kr
cpp
void merge(DSsequence *p, int low, int mid, int high) {
int n1 = mid - low + 1;
int n2 = high - mid;
int i, j, k;
int i1, i2;
i1 = 0;
i2 = 0;
i = 0;
while (i1 < n1 && i2 < n2) {
if (p[low + i1] <= p[mid + 1 + i2]) {
p[low + i] = p[low + i1];
i1++;
} else {
p[low + i] = p[mid + 1 + i2];
i2++;
}
i++;
}
while (i1 < n1) {
p[low + i] = p[low + i1];
i1++;
i++;
}
while (i2 < n2) {
p[low + i] = p[mid + 1 + i2];
i2++;
i++;
}
}
void mergeSort(DSsequence p, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(p, l, m);
mergeSort(p, m + 1, r);
merge(p, l, m, r);
}
}
이 함수를 사용하여 두 개의 정렬된 리스트를 병합하는 예제를 살펴보겠습니다.
#hostingforum.kr
cpp
int main() {
DSsequence p = {1, 3, 5, 7, 9};
DSsequence q = {2, 4, 6, 8, 10};
int n = 5;
mergeSort(p, 0, n - 1);
mergeSort(q, 0, n - 1);
merge(p, 0, n - 1, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", p[i]);
}
return 0;
}
이 예제에서는 두 개의 정렬된 리스트를 병합하여 하나의 정렬된 리스트를 생성합니다. 결과는 다음과 같습니다.
#hostingforum.kr
1 2 3 4 5 6 7 8 9 10
이러한 예제를 통해 DSSequence::merge 함수가 두 개의 정렬된 시퀀스를 병합하는 데 사용할 수 있으며, 중복된 원소를 제거하고 정렬된 상태를 유지하는 것을 확인할 수 있습니다.
2025-04-14 02:11