Coding Everybody
댓글
-
이런 방법도 있네요...
전날 봤을때는 피곤한 상태에서 이건 당최 무슨 소리인가... 하면서 봤는데, 다시 보니 기발하고 머리 좋으신 분들이 참 많다는걸 느낍니다.
영상을 보고도 이해가 안되시는 분들을 위해 간단하게 설명해드리면,
1. 일단 배열을 2개의 뭉텅이로 쪼갠 후,
2. 그 뭉텅이들만 정렬하는데,
이 때 2번의 방법을 재귀적으로 이용해 뭉텅이들을 정렬시킵니다.
3. 뭉텅이들이 정렬이 완료되었다면, 이젠 그 뭉텅이들을 쪼개기 전 상태로 다시 합칩니다(Merge).
이 합치는 과정에서 뭉텅이 내 요소들이 이미 정렬이 되었기 때문에, 정렬된 순서대로 뭉텅이들에서 요소를 가져와서 비교를 하면 비교적 쉽게 정렬을 할 수 있습니다
4. 처음 뭉텅이를 반으로 쪼갰던 순서의 역순으로 3번의 과정을 반복해 뭉텅이를 합치다 보면 결국 하나의 뭉텅이로 합쳐지게 되고 정렬이 완료됩니다. -
Merge sort explained with problem - https://www.interviewbit.com......hm/
-
잘 봤습니다. 감사합니다.
-
Zedd0202 http://zeddios.tistory.com/38
수까락 http://egloos.zum.com......985
Merge 알고리즘에 대한 사전지식이 없어서 영상을 곧장 이해할 수 없었는데,
두 분 블로그에 이 알고리즘이 정말 훌륭하게 설명 되어 있더라구요? 참고가 되었습니다! -
음이건 1도 이해가안되네 ㅎㅎ
-
[Merge 알고리즘 정리] 기본 알고리즘은 임시주소(버퍼)을 이용해서 원자원소로 나누어 두 수를 비교하여 작은 수는 임시주소에 두고 남은 수는 왼쪽 원소집합의 두번 째 원소와 비교하면서 임시주소(버퍼)에 작은 수 순으로 정열되면 실제주소로 들어가는 연산을 "왼쪽>오른쪽>전체"로 진행합니다. (메모리가 커야 할 듯)
(1차 연산)
1) 배열집합을 반으로 나누어 왼쪽에 있는 배열이 먼저 비교를 시작한다. 50%의 배열은 다시 50%의 50%로 나뉘면서 더 이상 나눠지지 않는 맨 왼쪽의 두 원소까지 50% 분할를 한다.
2) 맨 왼쪽의 나눠지지 않는 두 원소(이하 원자원소)가 비교를 하여 작은 수가 왼쪽으로 가면서 1차 연산을 멈춘다. 다음 오른쪽의 배열집합의 원자원소가 비교를 하여 작은 수가 왼쪽으로 가면서 1차 연산을 멈추고, 다음 오른쪽의 배열집합의 원자원소가 비교를 하면서 1차 연산이 끝나면
(2차 연산)
3)맨 오른쪽의 두 원자원소부터 비교를 하면서 작은 수가 임시주소(버퍼)의 위치하고 남은 수가 오른쪽의 수와 비교하여 다시 작은 수가 임수주소(버퍼)에 위치하면서 계속해서 오른쪽으로 비교를 해 갑니다. 비교가 끝나면 임시주소에 원소가 실제주소로 들어가면서 임시주소에 맨 왼쪽 원소(가장 작은 수)가 왼쪽 옆의 배열집합과 비교를 다시 비교를 하면서 작은 수는 임시주소의 왼쪽으로 가고 남은 수가 오른쪽 원소와 비교하면서 임시주소에서 정열하여 끝나면 실제주소로 들어갑니다.
(3차 연산)
4) 이제 오른쪽 배열집합의 가장 작은 수인 첫 번째 원소는 왼쪽 배열집합의 가장 작은 수인 왼쪽 첫번 째 수와 비교하여 작은 수는 임시주소(버퍼)에 나오고 남은 수는 왼쪽 배열집합의 두번 째 원소와 비교하여 작은 수는 임시주소(버퍼)에 자리잡고 남은 수가 다시 다음 원소와 비교하면서 오른쪽 끝의 원소까지 비교하게되면 정열이 끝납니다.
