[알고리즘] 병합 정렬

알고리즘 배우던 중.. 병합 정렬 너무 재밌어서 포스팅한다

 

병합 정렬이란?

분할정복 알고리즘이다.

 

배열안의 모든 숫자를 나눠서 병합하는 방식으로 정렬을 한다.

 

https://www.c-programming-simple-steps.com/merge-sort.html

입력 받은 수를 저장한 Array를 복사하고 정렬된 값을 담을 Array(입력 받은 수를 저장한 Array를 자주 쓴다)에 담아준다.

기본적으로 투포인터를 사용해서 복사된 array 안의 인덱스 끼리 서로 비교를 해가면서 값을 담는다.

 

시간 복잡도는 O(nlogn) 으로 정렬 알고리즘 중 최상위권이다

공간복잡도는 Array를 복사해야해서 O(2n) 이다 하하

그래서 퀵이랑 힙이 정렬 알고리즘 중에 레전드 오브 레전드라고 불리는 거 같은데 하하하

그래도 병합 정렬이 너무 재밌었다!!

투 포인터를 사용하는 것도 재밌구 진짜 단순하기 때문이다.

 

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class MergeSort {

    static int[] arr = {-8, 2, 1, 4, 8, 94, 12, 10, 5, 7, 40, 11, 3, 110, 890};
    static int[] tmp = new int[arr.length];

    public static void main(String[] args) throws IOException {

        // 병합 정렬!!!
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        mergeSort(0, arr.length - 1);

        for (int i = 0; i < arr.length; i++) {
            bw.write(arr[i] + " ");
        }
        
        bw.flush();
        bw.close();
    }

    public static void mergeSort(int l, int r) {

        if (l < r) {
			// == (l + r) / 2 와 같지만 l + r 할 때 숫자범위를 초과 할 수 있어서 이렇게 한다
            int m = l + (r - l) / 2;
			
            // 재귀함수로 구현
            mergeSort(l, m);
            mergeSort(m + 1, r);

            merge(l, m, r);
        }
    }

    public static void merge(int l, int m, int r) {

        for (int i = l; i <= r; i++) {
            tmp[i] = arr[i];
        }

        int k = l;
        int i1 = l; // leftIndex
        int i2 = m + 1; // rightIndex

		// 투 포인터 쓰면서 왼쪽과 오른쪽 비교 후 작은 값 arr에 저장
        while (i1 <= m && i2 <= r) {

            if (tmp[i1] <= tmp[i2]) {
                arr[k] = tmp[i1];
                i1++;
            } else {
                arr[k] = tmp[i2];
                i2++;
            }
            k++;
        }
		
        // 남은 것들 마저 수행
        while (i1 <= m) {
            arr[k] = tmp[i1];
            i1++;
            k++;
        }

        while (i2 <= r) {
            arr[k] = tmp[i2];
            i2++;
            k++;
        }
    }
}

 

정렬 알고리즘들이 쉽지만 너무 재밌는 거 같다 ㅋㅋ.. 이런 알고리즘들 만든 사람들이 너무 대단해보인다!!