갠적으로 퀵정렬보다는 훨씬 어려웟음 ㅠ 다른거보다 저걸 잘 읽엇어야함 일단 반으로 다 쪼개고 난 다음 나중에 합친다는걸 잘 읽엇어야댐 ㅠ_ㅠ 거참 콜롬버스 달걀처럼 누가 해놓은거 보기 전에는 디지게 어렵떠니 코드는 또 왜르케 간결한거임 이렇게 간결하게 정렬을 구현하다니 헟참나
if(i > middle) 부분 설명좀 해주실 분 계신가요? int i = m 이라고 선언이 되어있습니다. 5 7 / 6 8이라는 예시가 있다고 가정 / 5가 k의 배열 속으로 먼저 삽입된 후 를 가정하여 if( i > middle)이 선언되었다 하였을 때, 동영상을 통해 학습한 것으로는 middle의 값은 5 7 / 6 8 이라는 지점은 7 과 6의 값(0부터 시작시 1과 2의 지점) 가르키는 것이라고 이해하고 있습니다. 이러한 상황 속에서 i 값이 middle 값보다 커질 수 있는게 어떻게 가능한지 궁금합니다.
middle이 7, 6 둘 다 가리키고 있는 것이 아닙니다. 말씀하신 경우에서 middle은 7이고 j가 6인 것입니다. 즉, middle은 왼쪽 덩어리 (이 경우 5 7)의 끝부분을 가리킵니다. ( middle값을 (m + n) / 2 로 잡아줬는데 5 7 6 8이 전체 배열이라고 치면 5 -> 0, 8 -> 3의 인덱스를 갖고 '/'연산은 몫만 반환하기 때문에 1반환. 즉, 7만을 가리키는 것이 맞음 ) i는 처음에 5로 시작해서 5가 들어가고나면 7로 넘어갑니다. 그 다음엔 j가 6에서 시작하여 6이 들어가고 8로 넘어갑니다. 그럼 이제 i == 7, j == 8인 상태에서 둘을 비교하고 더 작은 i가 들어가게면서 mid+1 ( 최초의 j값 )을 가리키게 됩니다. 이제 if (i > middle)인 경우가 발생하였고 이는 "왼쪽 덩어리 다 들어갔으니 오른쪽 덩어리 전부 갖다 넣으면 됨"을 의미합니다. 아마 그림때문에 조금 헷갈리신 것 같은데 5 7 / 6 8 은 서로 다른 두개의 배열이 아닙니다. 사실은 하나의 배열이고 두 덩어리처럼 사용하기 위해서 인덱스로만 구분해놓은 것입니다. 동영상에서 언급된 "mid부분이 사실 실제 메모리상으론 붙어있는 것이다"라는 말이 이것 때문입니다. 참고로 한 쪽 덩어리가 모두 들어갔을 때 나머지 덩어리를 전부 그대로 넣어주면 되는 이유는 머지소트에서 말하는 머지(병합)는 각각 정렬이 되어있는 두 덩어리를 합치면서 정렬을 해주는 것이기 때문입니다. 두 덩어리의 가장 앞 원소 둘 중에 가장 작은 값이 있을테니 그것을 비교하여 넣어주는 것이고, 한 쪽 덩어리가 모두 들어갔다면 나머지는 처음 조건에 의해 이미 정렬이 되어있는 상태이니 그대로 넣어주기만 하면 되는 것입니다.
제가 이해를 제대로 한건지 확인부탁드릴게요ㅠ 예를들어 i= 6 7 / j= 4 8이라고 한다면 4 6 7 ~순으로 배열이 되는데 여기서 보면 i가 먼저 배열이 끝나잖아요.(4부터 8까지. 즉 끝까지 배열이 되기 전에 i인 6과 7은 정렬 완료) i가 먼저 배열이 끝난다고 쓴걸 (i>middle)이라고 표현한게 여기서 i=6인거고 middle (7+4)/2=5.5 따라서 i>middle이라는 말인거죠?
@@kyh4112 i > middle은 왼쪽배열(사실은 두개의 배열 중 왼쪽 배열이 아니라 하나의 배열을 두개처럼 보기 위해 인덱스로 구분한 것이고 그 중 왼쪽부분) 의 모든 원소가 먼저 끝나는 경우를 말하는 게 맞습니다. ( 반대로 오른쪽 배열이 먼저 끝났으면 if (i > middle) ~~ else ~~ 에서 else쪽으로 넘어갈 것입니다.) 뒤에 말씀하신 부분은 조금 틀렸습니다. i, j, k, middle은 모두 '인덱스'를 의미합니다. 배열의 원소를 나타내는 변수가 아닙니다. ( 본인께선 인덱스가 아닌 원소값으로 말씀하셨습니다. ) 6 7 / 4 8 의 경우에서 간략히 읊어보겠습니다. start == 0 이고 end == 3입니다. ( 인덱스 ) middle = ( i + j ) / 2 이기 때문에 1이 됩니다. i = start 이기 때문에 i는 0 j = middle + 1이기 때문에 2가 됩니다. 즉, 두개의 배열 ( 거듭 강조하지만 실제로 두개의 배열인 것이 아니라 하나의 배열을 두개처럼 보기 위해서 인덱스로 구분한 것임 ) 중에서 왼쪽 배열의 첫번째 인덱스 == i, 왼쪽 배열의 마지막 인덱스 == middle, 오른쪽 배열의 첫번쨰 인덱스 == j가 된 것입니다. 숫자로 따져보면 원소 6의 인덱스 0이 i 원소 7의 인덱스 1이 middle 원소 4의 인덱스 4가 j가 되어있는 상태입니다. 4가 빠지면서 j는 3으로 바뀌어 8의 인덱스를 나타냄 6이 빠지면서 i는 1로 바뀌어 7의 인덱스를 나타냄 ( 이때 i == middle ) 7이 빠지면서 i는 2로 바뀌어서 원래 4의 인덱스를 나타냄 ( 이떄 i > middle ) while( i
merge 부분는 mergesort에서 제일끝에 있죠 .즉 각 mergesort함수가 종료되기 전에 merge병합 되는 겁니다. 8,4,2,1 분할하며 내려갈때까지 mergesort함수들은 모두 종료 되지않아요 다 열려 있죠 . 그러다가 이제 1부터 올라오면서 병합하며 각 함수들이 종료됩니다. 이해안되시면 n을 작게해서 직접 코드순에 따라 그려보세요.
![9강 - C++ STL sort() 함수 다루기 ① [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #9 ]](http://i.ytimg.com/vi/YJ-OUnZu7nQ/mqdefault.jpg)
![9강 - C++ STL sort() 함수 다루기 ① [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #9 ]](/img/tr.png)
![5강 - 퀵 정렬(Quick Sort)의 시간 복잡도와 작동 원리 [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #5 ]](http://i.ytimg.com/vi/O-O-90zX-U4/mqdefault.jpg)
![11강 - 힙 정렬(Heap Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #11 ]](http://i.ytimg.com/vi/iyl9bfp_8ag/mqdefault.jpg)
당신이 최고입니다.
와 대박 제 은인입니다
갠적으로 퀵정렬보다는 훨씬 어려웟음 ㅠ
다른거보다 저걸 잘 읽엇어야함
일단 반으로 다 쪼개고 난 다음 나중에 합친다는걸 잘 읽엇어야댐 ㅠ_ㅠ
거참 콜롬버스 달걀처럼
누가 해놓은거 보기 전에는 디지게 어렵떠니 코드는 또 왜르케 간결한거임
이렇게 간결하게 정렬을 구현하다니 헟참나
갓동빈 ㄷㄷ 이거보고 바로 손코딩함
와.. 마침내 이해함. 동빈나 스승님 고맙습니댜
진짜..진짜...이해 잘 돼요 ㅠㅠㅠㅠ 이런 영상 공유해주셔서 너무 감사합니다
진짜 천재시구나..
와....알고리즘 시험 칠때도 이해못하고 암기함걸 이재야 이거보고 알아가네요 굳
if(i > middle) 부분 설명좀 해주실 분 계신가요?
int i = m 이라고 선언이 되어있습니다.
5 7 / 6 8이라는 예시가 있다고 가정 / 5가 k의 배열 속으로 먼저 삽입된 후 를 가정하여
if( i > middle)이 선언되었다 하였을 때,
동영상을 통해 학습한 것으로는 middle의 값은 5 7 / 6 8 이라는 지점은 7 과 6의 값(0부터 시작시 1과 2의 지점) 가르키는 것이라고 이해하고 있습니다.
이러한 상황 속에서 i 값이 middle 값보다 커질 수 있는게 어떻게 가능한지 궁금합니다.
middle이 7, 6 둘 다 가리키고 있는 것이 아닙니다.
말씀하신 경우에서 middle은 7이고 j가 6인 것입니다.
즉, middle은 왼쪽 덩어리 (이 경우 5 7)의 끝부분을 가리킵니다.
( middle값을 (m + n) / 2 로 잡아줬는데 5 7 6 8이 전체 배열이라고 치면 5 -> 0, 8 -> 3의 인덱스를 갖고 '/'연산은 몫만 반환하기 때문에 1반환. 즉, 7만을 가리키는 것이 맞음 )
i는 처음에 5로 시작해서 5가 들어가고나면 7로 넘어갑니다.
그 다음엔 j가 6에서 시작하여 6이 들어가고 8로 넘어갑니다.
그럼 이제 i == 7, j == 8인 상태에서 둘을 비교하고 더 작은 i가 들어가게면서 mid+1 ( 최초의 j값 )을 가리키게 됩니다.
이제 if (i > middle)인 경우가 발생하였고 이는 "왼쪽 덩어리 다 들어갔으니 오른쪽 덩어리 전부 갖다 넣으면 됨"을 의미합니다.
아마 그림때문에 조금 헷갈리신 것 같은데 5 7 / 6 8 은 서로 다른 두개의 배열이 아닙니다.
사실은 하나의 배열이고 두 덩어리처럼 사용하기 위해서 인덱스로만 구분해놓은 것입니다.
동영상에서 언급된 "mid부분이 사실 실제 메모리상으론 붙어있는 것이다"라는 말이 이것 때문입니다.
참고로 한 쪽 덩어리가 모두 들어갔을 때 나머지 덩어리를 전부 그대로 넣어주면 되는 이유는 머지소트에서 말하는 머지(병합)는 각각 정렬이 되어있는 두 덩어리를 합치면서 정렬을 해주는 것이기 때문입니다.
두 덩어리의 가장 앞 원소 둘 중에 가장 작은 값이 있을테니 그것을 비교하여 넣어주는 것이고, 한 쪽 덩어리가 모두 들어갔다면 나머지는 처음 조건에 의해 이미 정렬이 되어있는 상태이니 그대로 넣어주기만 하면 되는 것입니다.
제가 이해를 제대로 한건지 확인부탁드릴게요ㅠ
예를들어 i= 6 7 / j= 4 8이라고 한다면 4 6 7 ~순으로 배열이 되는데
여기서 보면 i가 먼저 배열이 끝나잖아요.(4부터 8까지. 즉 끝까지 배열이 되기 전에 i인 6과 7은 정렬 완료) i가 먼저 배열이 끝난다고 쓴걸 (i>middle)이라고 표현한게 여기서 i=6인거고 middle (7+4)/2=5.5 따라서 i>middle이라는 말인거죠?
@@kyh4112
i > middle은 왼쪽배열(사실은 두개의 배열 중 왼쪽 배열이 아니라 하나의 배열을 두개처럼 보기 위해 인덱스로 구분한 것이고 그 중 왼쪽부분) 의 모든 원소가 먼저 끝나는 경우를 말하는 게 맞습니다.
( 반대로 오른쪽 배열이 먼저 끝났으면 if (i > middle) ~~ else ~~ 에서 else쪽으로 넘어갈 것입니다.)
뒤에 말씀하신 부분은 조금 틀렸습니다.
i, j, k, middle은 모두 '인덱스'를 의미합니다. 배열의 원소를 나타내는 변수가 아닙니다. ( 본인께선 인덱스가 아닌 원소값으로 말씀하셨습니다. )
6 7 / 4 8 의 경우에서 간략히 읊어보겠습니다.
start == 0 이고 end == 3입니다. ( 인덱스 )
middle = ( i + j ) / 2 이기 때문에 1이 됩니다.
i = start 이기 때문에 i는 0
j = middle + 1이기 때문에 2가 됩니다.
즉, 두개의 배열 ( 거듭 강조하지만 실제로 두개의 배열인 것이 아니라 하나의 배열을 두개처럼 보기 위해서 인덱스로 구분한 것임 ) 중에서 왼쪽 배열의 첫번째 인덱스 == i, 왼쪽 배열의 마지막 인덱스 == middle, 오른쪽 배열의 첫번쨰 인덱스 == j가 된 것입니다.
숫자로 따져보면
원소 6의 인덱스 0이 i
원소 7의 인덱스 1이 middle
원소 4의 인덱스 4가 j가 되어있는 상태입니다.
4가 빠지면서 j는 3으로 바뀌어 8의 인덱스를 나타냄
6이 빠지면서 i는 1로 바뀌어 7의 인덱스를 나타냄 ( 이때 i == middle )
7이 빠지면서 i는 2로 바뀌어서 원래 4의 인덱스를 나타냄 ( 이떄 i > middle )
while( i
@@임현강-w9g 와 대박 이해 안할수가 없네요. 감사합니다ㅠ 이해했어요:) 복받으세요~
@@임현강-w9g 현강님 설명 덕분에 이해했습니다.
영상에서 Middle과 n을 설명하는 그림이 좀 많이 헷갈리게 나와있네요
혹시 12:30초 에서 for(int t=m; t
밑에 main 함수 보시면 mergeSort (array, 0, number - 1)라고 되어 있네요, 이미 n이 number보다 1 작은 수 입니다!
[병합 정렬] 절반으로 나누고 병합하면서 정렬한다
mergeSort(a, m, middle); (left는 왼쪽으로 나눌게 없어질때까지 실행된다)
mergeSort(a, middle + 1, n); (right는 left가 끝나면 실행된다)
merge(a, m, middle, n); (right가 끝나면 병합이 실행된다)
예시 7 6 5 8 3 5 9 1
1. left가 실행된다 7 6 5 8 -> 7 6 -> 7
2. left가 끝났으니 right가 실행된다 6
3. right가 끝났으니 merge함수가 실행된다 7과 6을 비교 후 6 7로 정렬
4. 정렬될 때까지 반복한다
전체적인 실행순서
7 6 5 8 -> 7 6 -> 7 -> 6 -> merge(6, 7) -> 5 8 -> 5 -> 8 -> merge(5, 8) -> merge(5, 6, 7, 8)
-> merge(1, 3, 5, 5, 6, 7, 8, 9) -> 1 3 5 5 6 7 8 9
3 5 9 1 -> 3 5 -> 3 -> 5 -> merge(3, 5) -> 9 1 -> 9 -> 1 -> merge(1, 9) -> merge(1, 3, 5, 9)
살짝 길잃을뻔했는데 설명 감사합니다 ㅠㅠ
9:38 저 두개가 같은 middle값이라고 하셨는데, 그럼 j = middle + 1 하는 이유가 뭘까요..
i를 첫번째 점으로 했으면, j도 첫번째 점인 그냥 middle로 해야하는 것 아닌가요??
i는 시작부터 중간까지(middle)까지 j는 중간부터 끝까지 가야해서 중간다음인 middle+1부터 하는거에요.
만냑 가피 가플
저는 미국에 사는데 내일 모레 c++ final 있어요
진짜 일년동안 뭐 배웠나 싶었는데 이거 보고 겨우 이해합니다ㅋㅋㅋㅋㅋ
내년에 java 는 어떻게 들을까 싶네요ㅜㅜㅜㅋㅋㅋㅋㅋ
완전 video thank you so much 에요!!
미쿡사는게부럽네요..개발자천국
아니 쉬운거 맞음 ㅠ_ㅠ? 답 안보고 10분까지만 개념듣고 풀라는데 퀵정렬보다 훨씬 어려운데 ㅠㅠㅠㅠ
진짜 아예 접근이 잘 안되는뎅.. 아놔 ㅠㅠㅠ 빡대가리 어케 코딩함
함수를 만들때 void merge(int * a ~~~ 이렇게 쓰는거랑 void merge(int a[] ~~~ 랑 무슨 차이가 나는 건가요
bgm뭐냐 실화야
이해가 너무 잘됩니다 감사합니다^^
교수님 강의보다 훨씬 이해가 잘됩니다,,, 감사합니다 ㅠㅜ
이해가 될랑말랑 말랑될랑 .....
오홍홍 좋아용
파이썬 강의 빨리 올려주세요! 현기증 난단 말이에요! 핡짝!!핡짝!!
혹시 이 코드는 자료의 개수가 짝수개일때만 정렬이 가능한 코드인가요?? 홀수개라면 middle의 위치가 애매해질수도 있지않나요?? 궁금합니다 ㅠ
이거 해결하셨나요?
c언어에서 Int 자료형은 정수만 저장하기 때문에 딱히 다를건 없습니다!
8:11 코드 작성
Mergesort에서 a가 *a여야하는거 아닌가요?? a가 뭘 뜻하는건가요?
함수보면 매개변수 int a[] - 배열의 포인터를 받고잇습니다
배열의 길이를 변수로 설정하시면 안돼요
좋은 강의 감사합니다~
mergesort 재귀함수에서 계속 나누면서 병합하는데 그럼 8>4>2>1 이렇게 나누는건데 재귀함수안에 merge함수도 들어가있으니까
4 4 로 쪼갰을떄 이미 정렬이 되는거 아닌가요 ?ㅠㅠ
merge 부분는 mergesort에서 제일끝에 있죠 .즉 각 mergesort함수가 종료되기 전에 merge병합 되는 겁니다. 8,4,2,1 분할하며 내려갈때까지 mergesort함수들은 모두 종료 되지않아요 다 열려 있죠 . 그러다가 이제 1부터 올라오면서 병합하며 각 함수들이 종료됩니다. 이해안되시면 n을 작게해서 직접 코드순에 따라 그려보세요.
아... 이해하는데 2시간 걸렸다. .정상이냐
ㅠㅠ