[BOJ/Merge Sort] 백준 1517 - 버블 소트 (Java)

1517 - 버블 소트

https://www.acmicpc.net/problem/1517

문제

N개의 수로 이뤄진 수열 A[1], A[2], ..., A[N]
버블 소트: 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방식
ex. 3 2 1 ->  2 3 1 -> 2 1 3 -> 1 2 3

입력
첫째 줄: N (1 <= N <= 500,000)
다음 줄: N개의 정수 A[1], A[2], ..., A[N] (0 <= |A[i]| <= 1,000,000,000)
출력: swap 횟수

---

풀이

버블 정렬에서 발생하는 swap 횟수 = 역순 쌍(inverse) 개수

 

합병 정렬(Merge Sort)

배열을 반으로 분할 -> 각 절반을 재귀적으로 정렬 -> 정렬된 두 배열 병합(merge)

시간 복잡도: O(N log N)

 

 

mergeSort(lt, rt)

• [lt ~ rt] 구간 정렬
  • `lt >= rt`: 원소가 1개 이하 => 이미 정렬된 상태
• 왼쪽, 오른쪽 반으로 나누고 각각 정렬한 뒤 `merge()`로 합침

static void mergeSort(int lt, int rt) {
    if (lt >= rt) return;

    int mid = (lt + rt) / 2;
    mergeSort(lt, mid);
    mergeSort(mid + 1, rt);
    merge(lt, mid, rt);
}

 

merge(lt, mid, rt)

• i: 왼쪽 배열 포인터 / j: 오른쪽 배열 포인터 / `idx`: 임시 배열(`tmp`)에 넣을 위치
  • [lt ~ mid], [mid + 1 ~ rt] 이미 정렬됐다는 전제
• 왼쪽, 오른쪽 배열 둘다 남아 있을 때만 비교
  • 정상 정렬 케이스: `A[i] <= A[j]` -> `tmp[idx++] = A[i++]`
  • 역순 쌍 O (`A[i] > A[j]`) -> 왼쪽 배열 이미 정렬됐고 전부 A[j]보다 큼
    => `A[j]`가 왼쪽 원소들 전부와 swap 해야 함
    
    • `tmp[idx++] = A[j++]`
    • `cnt += (mid - i + 1)`
• 남은 값 처리
  • 오른쪽 배열 먼저 끝난 경우: `i <= mid` -> `tmp[idx++] = A[i++]`
  • 왼쪽 배열 먼저 끝난 경우:`j <= rt` -> `tmp[idx++] = A[j++]`
• 원본 배열에 복사

static void merge(int lt, int mid, int rt) {
    int i = lt;
    int j = mid + 1;
    int idx = lt;

    while (i <= mid && j <= rt) {
        if (A[i] <= A[j]) tmp[idx++] = A[i++];
        else {
            tmp[idx++] = A[j++];
            cnt += (mid - i + 1);
        }
    }

    while (i <= mid) tmp[idx++] = A[i++];
    while (j <= rt) tmp[idx++] = A[j++];

    for (int k = lt; k <= rt; k++) A[k] = tmp[k];
}

---

코드

import java.io.*;
import java.util.*;

// 버블 소트
public class boj_1517 {
    static int N;
    static int[] A, tmp;
    static long cnt = 0;

    static void mergeSort(int lt, int rt) {
        if (lt >= rt) return;

        int mid = (lt + rt) / 2;
        mergeSort(lt, mid);
        mergeSort(mid + 1, rt);
        merge(lt, mid, rt);
    }

    static void merge(int lt, int mid, int rt) {
        int i = lt;
        int j = mid + 1;
        int idx = lt;

        while (i <= mid && j <= rt) {
            if (A[i] <= A[j]) tmp[idx++] = A[i++];
            else {
                tmp[idx++] = A[j++];
                cnt += (mid - i + 1);
            }
        }

        while (i <= mid) tmp[idx++] = A[i++];
        while (j <= rt) tmp[idx++] = A[j++];

        for (int k = lt; k <= rt; k++) A[k] = tmp[k];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());

        A = new int[N];
        tmp = new int[N];

        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        mergeSort(0, N - 1);
        System.out.println(cnt);
    }
}