[백준 1517] 버블 소트 (JAVA)

백준 1517번 문제  - 버블 소트

1517번: 버블 소트

---

문제 분석

 

: 오름차순으로 정렬할때 일어나는 swap 개수를 출력해라

---

해결 키 포인트

• 오름차순 정렬
  
  • 병합 정렬
• 병합 정렬하면서 앞 배열의 값보다 뒷 배열의 값이 더 작을 때 swap 개수 증가

 

swap 개수 누적	배열
1 [0하고 1]	3[0]  2[1]  1[2]
2 [0하고 2]	2[1]  3[0]  1[2]
3 [1하고 2]	2[1]  1[2]  3[0]
3	1[2]  2[1]  3[0]

• 증가되는 swap 개수 = 뒷 배열 시작 index - 현재 비교한 앞 배열 index
• value[index] : value = 실제 값 | index = 인덱스 값

 

swap 개수 누적	현재 swap 개수 구하는 법	병합 배열
1 [0하고 1]	1 - 0 = 1	3[0]  |  2[1]  |  1[2]
3 [1하고 2, 1하고 3]	2 - 0 = 2	2[0]  3[1]  |  1[2]
3	0	1  2  3

 

---

병합 정렬 설명

 

복합 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘

 

Do it! 알고리즘 코딩 테스트 기본

 

 

1. 최소 단위로 분할 (가장 작은 데이터 집합으로 분할)
2. 두 단위를 병합하면서 정렬

---

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int [] nums, temp;
    public static long result = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        nums = new int[N];
        temp = new int[N];

        for(int i=0;i<N;i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        // 정렬
        margeSort(0, N-1);

        System.out.println(result);
    }

    public static void margeSort(int s, int e) {
        if( e - s < 1) return;

        int m = s + (e-s) / 2;

        // 분할
        margeSort(s, m);
        margeSort(m+1, e);

        // temp 복사
        for(int i=s;i<=e;i++) {
            temp[i] = nums[i];
        }

        int i = s;
        int index1 = s;
        int index2 = m+1;

        // 병합
        while(index1 <= m && index2 <= e) {
            if(temp[index1] > temp[index2]) {
                nums[i] = temp[index2++];

                // 앞 배열에 남아있는 것들을 하나씩 swap해야하는 것이므로 남아있는 개수를 result에 다 더함
                result += m+1 - index1;
            }
            else {
                nums[i] = temp[index1++];
            }
            i++;
        }

        // index1이 남은 배열이 있을 경우
        while(index1 <= m) {
            nums[i] = temp[index1++];
            i++;
        }

        // index1이 남은 배열이 있을 경우
        while(index2 <= e) {
            nums[i] = temp[index2++];
            i++;
        }
    }
}