병합정렬 tempArrIndex = leftIndex 질문 있습니다
안녕하세요,
강의을 따라 코딩을 해보던 중 임시배열 tempArr을 작성하다가
tempArrIndex = leftIndex 에서 leftIndex 대신 0을 넣었는데 그러면 코딩 실행이 정상적으로 되지 않아서 (강의 13:38 부분)
무엇이 잘못됐는지 궁금해 질문 드립니다.
감사합니다 :)
답변 1
0
안녕하세요 김예서님!
해당 문제는 MergeSort가 두 번 호출될 때 배열의 크기가 달라져서 생기는 문제입니다.
먼저 MergeSort함수 내 첫 번째 MergeSort함수(사진 속 1번 네모) 호출에서 호출한 상황입니다.
Merge 함수는 rightIndex의 크기에 1을 더한 값을 tempArr의 크기로 설정하므로 tempArr의 크기는 2가됩니다. 사진 속 2번 네모에서 배열의 크기를 확인할 수 있습니다.
다음으로 호출되는 MergeSort함수(사진 속 3번 네모)도 마찬가지로 rightIndex의 크기에 1을 더한 값을 tempArr의 크기로 설정하는데 이번엔 조금 더 커진값입니다.
배열의 크기가 4가됩니다.
그리고 이 배열의 앞부분은 이전 함수에서 정렬됐다고 생각하고 0으로 비워뒀습니다.(4번 네모)
만약 tempArrIndex를 0으로 설정했다면 비워둔 값을 가리키게 되기 때문에 정상적인 정렬이 이루어지지 않습니다.
궁금증이 해결되셨나요? 😊
1
이해했습니다 감사합니다 :)
그런데 혹시 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];
}
}
연결리스트 삽입삭제 O(1) 아닌가요?
0
40
2
큐의 마지막 데이터가 head에 위치해야 하는 이유가 궁금합니다.
0
91
2
이중연결 리스트 데이터 삭제시 질문이 있습니다.
1
79
2
자바스크립트 배열은 동적이 아닌가요?
1
98
2
자바스크립트 배열
0
88
2
코테에서 링크리스트 자료구조를 사용해야 하면, 이번 강의에서 구현한 메서드들도 모두 직접 구현하면 되나요?/
0
163
2
공부 방식 질문 드립니다.
1
128
2
메모이제이션과 타뷸레이션 관련해서 질문드립니다.
1
185
2
병합정렬에서 질문이 있습니다.
2
150
1
병합정렬 질문 있습니다.
1
150
5
데이터 삽입, 삭제 함수 오류 범위 설정
0
168
2
해시 테이블에서 질문이 잇습니다.
2
135
2
시간복잡도 계산 시 1회 연산당 연산량은 왜 고려하지 않는 건가요?
1
163
2
터미널 설정
0
118
2
2:13분 관련 질문입니다
0
97
1
8:47초경부터 9:00초까지 질문입니다.
1
141
2
tail을 삭제하는 경우에 관련해서 질문이 있습니다.
0
116
1
2:36초 head 위치가?
1
120
2
환경구축강의 중 터미널 파일 실행오류
0
176
2
4:58 이중for문 질문있습니다.
0
112
1
hanoi함수 처음 호출에 대해서 여쭤봅니다.
1
139
2
해쉬테이블 데이터 관련해서 질문있습니다.
0
157
2
자바스크립트 Map과 어떤 차이가 있나요??
0
214
2
질문이있습니다.
0
111
1