글 읽기 - [c++]합병정렬 관련해서 질문드리고 싶은게 있습니다.

needid 4년 전 0

합병정렬을 쓸경우 보통

merge_sort()
merge_sort()
merge()

이런식으로 쓰고 merge() 안에 정렬된 배열을 따로 저장해두는 임시 배열을 하나 만들어두는걸로 압니다.
여기서 임시배열을 int *sorted = new int[end - start + 1] 이런식으로 할당을 했더니 런타임에러가 뜨는데 혹시 이유를 알 수 있을까요?

dyk777 4년 전 0

https://www.acmicpc.net/board/view/32737

질문 작성 시 틀린 코드를 한 글자도 틀림 없이 정확하게 올리라고 되어 있습니다.

위 설명만으로는 메모리 할당 실패에 의한 런타임 에러인지, 함수가 내부적으로 잘못되었는지, 혹은 기타 다른 원인이 있는지 알 수 없습니다.

needid 4년 전 0

메모리 할당 부분을 없애고 1000001만큼의 배열을 생성하니 문제를 성공하여 이부분만 적었습니다...;;
추가설명을 적었어야 되는데 죄송합니다... 틀린소스 추가했습니다.

#include <iostream>
#include <algorithm>
using namespace std;

void merge(int *data, int start, int mid, int end){
    int *sorted = new int[end-start+1];
    int i = start;
    int j = mid + 1;
    int k = start;   
    while(i<=mid && j<=end){
        if(data[i] <= data[j]){
            sorted[k] = data[i];
            i++;
        }else{
            sorted[k] = data[j];
            j++;
        }
        k++;
    }
    if(i > mid){
        for(int t = j ; t <= end ; t++){
            sorted[k] = data[t];
            k++;
        }
    }else{
        for(int t = i ; t<= mid ; t++){
            sorted[k] = data[t];
            k++;
        }
    }
    for(int t = start; t<=end; t++){
        data[t] = sorted[t];
    }
}
void merge_sort(int *data, int start, int end){
    int mid, temp;
    if((end - start) == 1){
        if(data[start] > data[end]){
            temp = data[end];
            data[end] = data[start];
            data[start] = temp;
        }
    }else if(start < end){
        mid = (start + end)/2;
        merge_sort(data, start, mid);
        merge_sort(data, mid+1, end);
        merge(data, start, mid, end);
    }
}
int main(){
    int num, b;
    cin >> num;
    int *arr = new int[num];
    for(int i = 0 ; i<num ; i++){
        cin >> b;
        arr[i] = b;
    }
    merge_sort(arr, 0, num-1);
    for(int i = 0 ; i<num ; i++){
        cout << arr[i] << '\n';
    }
    return 0;
}

dyk777 4년 전 0

new로 할당한 배열이 이후 delete 되지 않아서, 메모리 누수가 발생하고 있는 것 같습니다.

재귀가 깊어지면서 더이상 가용한 메모리가 남지 않게 되면 할당에 실패하게 될 것 같네요.

이 경우 예외가 throw 되거나, nullptr이 반환될 것입니다.

예외가 throw 되는 경우 백준에서 아마도 런타임 에러로 잡을 것 같구요,

nullptr이 반환된 경우에도 0번지에 대한 부적절한 접근이 발생하므로 런타임 에러가 발생할 것입니다.

dyk777 4년 전 0

다른 이유가 더 있었네요.

sorted의 인덱스는 0~(end-start) 까지 인데, start가 충분히 큰 경우가 재귀호출되면 배열 범위 밖을 벗어나서 접근할 것으로 보입니다.

이 또한 런타임 에러가 발생하는 원인이 될 수 있구요.

needid 4년 전 0

start가 큰 수를 가질 경우에 if(start<end)일 경우에만 merge함수를 호출하도록 한 것만으로는 배열 범위 밖을 넘어가는 것을 막지 못할까요?

dyk777 4년 전 1

있음직한 예를 들어보죠. 16개의 수를 임의로 골라 잘 섞어서 0~15의 인덱스로 하여 정렬한다고 생각해봅시다.

반으로 나눠서 정렬한 후 합칠 것이므로, 재귀호출하던 어느 순간에는 8~11의 인덱스를 정렬하는 순간이 올 것입니다.

8,9와 10,11을 각각 정렬된 후, 합치는 과정을 고려해봅시다. start가 8이고, end가 11이겠네요.

이때 sorted 배열은 11-8+1 = 4의 크기를 가지고, 인덱스로는 0~3을 갖습니다.

그런데 merge 함수 내의 while문을 잘 보시면, k의 초깃값이 start=8입니다.

그 상태에서 sorted[k]와 같이 하여 접근하고 있으므로, 배열의 범위를 초과하게 됩니다.

needid 4년 전 0

아 그렇네요 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++]합병정렬 관련해서 질문드리고 싶은게 있습니다.

needid 4년 전 0

dyk777 4년 전 0

needid 4년 전 0

dyk777 4년 전 0

dyk777 4년 전 0

needid 4년 전 0

dyk777 4년 전 1

needid 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말