99클럽 코테 스터디 31일차 TIL 병합 정렬 구현

병합 정렬 구현

• 정렬해야 할 리스트를 계속 분할하여 최대한 작게 쪼갠 후, 부분 리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식
• 정렬 방법
  • 주어진 리스트를 절반으로 분할하여 부분 리스트로 나눈다. (Divide : 분할)
  • 해당 부분 리스트의 길이가 1 이 아니라면 1번 과정을 되풀이한다.
  • 인접한 부분 리스트끼리 정렬하여 합친다. (Conqure : 정복)
• 시간 복잡도
  • O(NlogN)
  • 최선, 평균, 최악 모두 같다.
• 구현

import java.util.Arrays;

public class MergeSort {

    public static int[] answer, temp;

    public static void main(String[] args) {
        solution(5, new int[]{5, 4, 3, 2, 1});
    }

    public static void solution(int n, int[] nums) {
        answer = new int[n + 1];
        temp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            answer[i] = nums[i - 1];
        }
        mergeSort(1, n);
    }

    public static void mergeSort(int start, int end) {
        // 부분리스트 원소가 1개면 쪼개기 종료
        if (end == start) {
            return;
        }

        int mid = start + (end - start) / 2;  // 부분리스트의 절반 위치
        // 제일 작은 단위로 쪼개질 때 까지 재귀
        mergeSort(start, mid);  // 절반 중 왼쪽 부분리스트 (start ~ mid)
        mergeSort(mid + 1, end);  // 절반 중 오른쪽 부분리스트 (mid + 1 ~ end)

        // 다 쪼개졌으면 병합 수행
        // 정렬 할 부분리스트 temp 배열에 저장
        for (int i = start; i <= end; i++) {
            temp[i] = answer[i];
        }

        int k = start;  // 채워 넣을 배열의 index
        int index1 = start;
        int index2 = mid + 1;

        // 한 쪽 리스트 비교가 끝날 때 까지
        while (index1 <= mid && index2 <= end) {
            // 왼쪽 부분의 비교 값이 더 크면
            if (temp[index1] > temp[index2]) {
                // 오른쪽 비교 값을 넣고 배열의 index 와 오른쪽 비교 인덱스를 1 증가
                answer[k] = temp[index2];
                k++;
                index2++;
            } else {
                answer[k] = temp[index1];
                k++;
                index1++;
            }
        }

        // 오른쪽 부분리스트 비교가 먼저 끝났으면
        // 왼쪽 남은 값들을 배열에 넣기
        while (index1 <= mid) {
            answer[k] = temp[index1];
            k++;
            index1++;
        }

        // 왼쪽 부분리스트 비교가 먼저 끝났으면
        // 오른쪽 남은 값들을 배열에 넣기
        while (index2 <= end) {
            answer[k] = temp[index2];
            k++;
            index2++;
        }
    }
}

728x90

느낀 점

• 직접 구현하는 문제가 나올 수 도있고, 시간 복잡도가 O(NlogN)으로 O(N²)인 버블, 삽입, 선택 정렬보다 빠르므로 잘 알아두자.

다음에 학습할 것

• 다른 정렬들 알아보기

반응형

---

더 빠른 정렬도 존재하므로 꼭 공부해 보자!