코딩 테스트 [정렬] - 버블 소트 프로그램2

유의선·2023년 7월 26일

버블 소트는 서로 인접해 있는 두 수를 바꾸면서 정렬하는 방법이다. 예를 들어 수열이 3, 2, 1이었다고 가정해 보자. 이때는 인접해 있는 3, 2가 바뀌어야하므로 2, 3, 1이 된다. 그다음은 3, 1이 바뀌어야 하므로 2, 1, 3이 된다. 그다음은 2, 이 바뀌어야 하므로 1, 2, 3이 된다. 그러면 더 이상 바꿀 수 없으므로 정렬이 완료된다.

N개의 수로 이뤄진 수열 A[1], A[2], ... , A[N]이 있다. 이 수열로 버블 소트를 수행할 때 swap이 총 몇번 발생하는지 알아보는 프로그램을 작성하시오.

(시간 제한 1초)

입력

1번째 줄에 수의 개수 N(1 ⪯ N ⪯ 500,000), 2번째 줄부터 N개의 정수로 A[1], A[2], ... , A[N]이 주어진다. 각각의 A[i]는 0 ⪯ |A[i]| ⪯ 1,000,000,000의 범위에 들어 있다.

출력

1번째 줄에 swap 횟수를 출력한다.

예제 입력
8	// 수의 개수
3 2 8 1 7 4 5 6

예제 출력
11

`1단계` - 문제 분석하기

제목은 버블 소트지만 N의 최대 범위가 5,000,000이므로 버블 소트를 사용하면 제한 시간을 초과해버린다. 즉, 이 문제는 버블소트가 아닌 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 사용해야 한다.
병합 정렬은 두 그룹을 병합하는 과정에서 버블 정렬의 swap이 포함되어 있다.

두 그룹을 병합하는 과정에서 뒤쪽 그룹의 5가 앞쪽 그룹의 24, 32, 24, 60의 앞에 놓인다. 이는 버블 정렬에서 swap을 4번해야 볼 수 있는 효과이다.

45는 60보다 앞에 놓이므로 버블 정렬에서 swap을 1번 한 것과 동일하다.

이 아이디어로 문제를 해결해보겠다.

`2단계` - 손으로 풀어 보기

병합 정렬은 동일하게 진행한다. 다만 정렬 과정에서 index가 이동한 거리를 result에 저장한다.

그룹을 정렬하는 과정에서 원소가 앞으로 이동한 거리만큼 result에 더한다.

(3,2), (8,1), (7,4), (5,6) 그룹은 1, 2, 3 번째 그룹에서 2, 1, 4 원소만 이동하므로 result에 총 3을 더한다.

(2,3,1,8), (4,7,5,6) 그룹은 1이 2칸, 5, 6이 각각 1칸씩 이동하므로 result에 총 4를 더한다.

마지막으로 (1,2,3,8,4,5,6,7)은 4, 5, 6, 7이 각 1칸씩 이동하므로 result에 총 4를 더한다.

`3단계` - sudo코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언하기)
tmp(정렬할 때 잠시 사용할 임시 배열 선언하기)

for(N의 개수만큼)
{
	A배열 선언하기
}
병합 정렬 함수 수행하기
결괏값 출력하기

병합 정렬 (s, e) {
	s(시작점), e(종료점), m(중간점)
	// 재귀 함수 형태로 구현
    병합 정렬(s, m)
    병합 정렬(m + 1, e)
    
    for(s ~ e)
    {
    	tmp 배열 저장하기
    }
    
    // 두 배열을 병합하는 로직
    index1 -> 앞쪽 그룹 시작점
    index2 -> 뒤쪽 그룹 시작점
    while(index1 <= 중간점 && index2 <= 종료점) {
    	뒤족 데이터 값이 더 작아 선택될 때
        swap이 일어났다고 가정하고, 현재 남아 있는 앞쪽 데이터 개수만큼 결괏값에 더함
    }
    반복문이 끝난 후 남아 있는 데이터 정리
}

`4단계` - 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q21 {
    public static int[] A, tmp;
    public static long result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

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

        result = 0;

        merge_sort(0, N-1);

        System.out.println(result);
    }

    private static void merge_sort(int s, int e) {
        if (e - s < 1)
            return;

        int m = (s + e) / 2;

        merge_sort(s, m);
        merge_sort(m + 1, e);

        for(int i = s; i <= e; i++){
            tmp[i] = A[i];
        }

        int k = s;
        int index1 = s;
        int index2 = m + 1;
        while(index1 <= m && index2 <= e){
            if(tmp[index1] < tmp[index2]){
                A[k] = tmp[index1];
                k++;
                index1++;
            }else {
                A[k] = tmp[index2];
                result = result + index2 - k;   // 뒤쪽 데이터 값이 작은 경우 result 업데이트
                k++;
                index2++;
            }
        }
        while(index1 <= m){
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= e){
            A[k] = tmp[index2];
            k++;
            index2++;
        }

    }
}