정렬

Merge-sort

댓글

댓글 본문
작성자
비밀번호
  1. 별모모
    [Merge 알고리즘 정리] 기본 알고리즘은 임시주소(버퍼)을 이용해서 원자원소로 나누어 두 수를 비교하여 작은 수는 임시주소에 두고 남은 수는 왼쪽 원소집합의 두번 째 원소와 비교하면서 임시주소(버퍼)에 작은 수 순으로 정열되면 실제주소로 들어가는 연산을 "왼쪽>오른쪽>전체"로 진행합니다. (메모리가 커야 할 듯)
    (1차 연산)
    1) 배열집합을 반으로 나누어 왼쪽에 있는 배열이 먼저 비교를 시작한다. 50%의 배열은 다시 50%의 50%로 나뉘면서 더 이상 나눠지지 않는 맨 왼쪽의 두 원소까지 50% 분할를 한다.
    2) 맨 왼쪽의 나눠지지 않는 두 원소(이하 원자원소)가 비교를 하여 작은 수가 왼쪽으로 가면서 1차 연산을 멈춘다. 다음 오른쪽의 배열집합의 원자원소가 비교를 하여 작은 수가 왼쪽으로 가면서 1차 연산을 멈추고, 다음 오른쪽의 배열집합의 원자원소가 비교를 하면서 1차 연산이 끝나면

    (2차 연산)
    3)맨 오른쪽의 두 원자원소부터 비교를 하면서 작은 수가 임시주소(버퍼)의 위치하고 남은 수가 오른쪽의 수와 비교하여 다시 작은 수가 임수주소(버퍼)에 위치하면서 계속해서 오른쪽으로 비교를 해 갑니다. 비교가 끝나면 임시주소에 원소가 실제주소로 들어가면서 임시주소에 맨 왼쪽 원소(가장 작은 수)가 왼쪽 옆의 배열집합과 비교를 다시 비교를 하면서 작은 수는 임시주소의 왼쪽으로 가고 남은 수가 오른쪽 원소와 비교하면서 임시주소에서 정열하여 끝나면 실제주소로 들어갑니다.

    (3차 연산)
    4) 이제 오른쪽 배열집합의 가장 작은 수인 첫 번째 원소는 왼쪽 배열집합의 가장 작은 수인 왼쪽 첫번 째 수와 비교하여 작은 수는 임시주소(버퍼)에 나오고 남은 수는 왼쪽 배열집합의 두번 째 원소와 비교하여 작은 수는 임시주소(버퍼)에 자리잡고 남은 수가 다시 다음 원소와 비교하면서 오른쪽 끝의 원소까지 비교하게되면 정열이 끝납니다.
graphittie 자세히 보기