병합정렬 tempArrIndex = leftIndex 질문 있습니... - 인프런

그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

정렬 - 병합정렬

병합정렬 tempArrIndex = leftIndex 질문 있습니다

해결된 질문

작성

312

수정됨

안녕하세요,

강의을 따라 코딩을 해보던 중 임시배열 tempArr을 작성하다가

tempArrIndex = leftIndex 에서 leftIndex 대신 0을 넣었는데 그러면 코딩 실행이 정상적으로 되지 않아서 (강의 13:38 부분)

무엇이 잘못됐는지 궁금해 질문 드립니다.

감사합니다 :)

답변 1

지식공유자

안녕하세요 김예서님!
해당 문제는 MergeSort가 두 번 호출될 때 배열의 크기가 달라져서 생기는 문제입니다.

먼저 MergeSort함수 내 첫 번째 MergeSort함수(사진 속 1번 네모) 호출에서 호출한 상황입니다.

Merge 함수는 rightIndex의 크기에 1을 더한 값을 tempArr의 크기로 설정하므로 tempArr의 크기는 2가됩니다. 사진 속 2번 네모에서 배열의 크기를 확인할 수 있습니다.

다음으로 호출되는 MergeSort함수(사진 속 3번 네모)도 마찬가지로 rightIndex의 크기에 1을 더한 값을 tempArr의 크기로 설정하는데 이번엔 조금 더 커진값입니다.

배열의 크기가 4가됩니다.
그리고 이 배열의 앞부분은 이전 함수에서 정렬됐다고 생각하고 0으로 비워뒀습니다.(4번 네모)
만약 tempArrIndex를 0으로 설정했다면 비워둔 값을 가리키게 되기 때문에 정상적인 정렬이 이루어지지 않습니다.

궁금증이 해결되셨나요? 😊

질문자

이해했습니다 감사합니다 :)

그런데 혹시 tempArrIndex = 0 로 할 수 있는 방법이 있는지도 궁금합니다 !

tempArr의 크기가 rightIndex를 기준으로 정해지지 않고 rightIndex - leftIndex + 1 로 해서

분할했던 원소를 병합한 후의 크기와 동일한 임시배열을 만들고 그걸 arr에 복사붙여넣기하는 방법으로 하려고 했는데 잘 되지 않아서요.

for(let i = leftIndex; i <= rightIndex; i++){
  for(let j = 0; j < tempArr.length; j++){
    arr[i] = tempArr[j];
  }
}

지식공유자

방법이야 어떤식으로 해도 상관없습니다.
잘 되지 않는다면 디버깅 모드로 변경 후 어떤점이 잘못됐는지 찾아보면서 코드를 수정하면 실력 향상에 큰 도움이 될 겁니다. ㅎㅎ