-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
병합정렬 tempArrIndex = leftIndex 질문 있습니다
23.10.29 19:11 작성 23.10.29 19:12 수정 조회수 206
1
안녕하세요,
강의을 따라 코딩을 해보던 중 임시배열 tempArr을 작성하다가
tempArrIndex = leftIndex 에서 leftIndex 대신 0을 넣었는데 그러면 코딩 실행이 정상적으로 되지 않아서 (강의 13:38 부분)
무엇이 잘못됐는지 궁금해 질문 드립니다.
감사합니다 :)
답변을 작성해보세요.
0
감자
지식공유자2023.10.29
안녕하세요 김예서님!
해당 문제는 MergeSort가 두 번 호출될 때 배열의 크기가 달라져서 생기는 문제입니다.
먼저 MergeSort함수 내 첫 번째 MergeSort함수(사진 속 1번 네모) 호출에서 호출한 상황입니다.
Merge 함수는 rightIndex의 크기에 1을 더한 값을 tempArr의 크기로 설정하므로 tempArr의 크기는 2가됩니다. 사진 속 2번 네모에서 배열의 크기를 확인할 수 있습니다.
다음으로 호출되는 MergeSort함수(사진 속 3번 네모)도 마찬가지로 rightIndex의 크기에 1을 더한 값을 tempArr의 크기로 설정하는데 이번엔 조금 더 커진값입니다.
배열의 크기가 4가됩니다.
그리고 이 배열의 앞부분은 이전 함수에서 정렬됐다고 생각하고 0으로 비워뒀습니다.(4번 네모)
만약 tempArrIndex를 0으로 설정했다면 비워둔 값을 가리키게 되기 때문에 정상적인 정렬이 이루어지지 않습니다.
궁금증이 해결되셨나요? 😊
김예서
질문자2023.11.06
이해했습니다 감사합니다 :)
그런데 혹시 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];
}
}
감자
지식공유자2023.11.06
방법이야 어떤식으로 해도 상관없습니다.
잘 되지 않는다면 디버깅 모드로 변경 후 어떤점이 잘못됐는지 찾아보면서 코드를 수정하면 실력 향상에 큰 도움이 될 겁니다. ㅎㅎ
답변 1