[ 정렬 ] 병합 정렬, 기수 정렬(백준 1517, 2750)

 병합 정렬 : O(nlogn)

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

병합과정이 총 logn만큼 일어난다.

각각을 병합하는 과정은 n의 시간이 걸린다.(아래 설명)

💡 2개의 그룹을 병합하는 과정

투 포인터 개념을 사용해서 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 배열에 추가하고 포인터를 오른쪽으로 이동시킨다.

이렇게 2개의 그룹을 병합하는 과정이 시간이 N만큼 걸린다.

 

 1517 : 버블 소트

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

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

 

입력

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

• 데이터 크기의 값이 50만이다. 즉 N2 의 시간복잡도로는 시간초과가 난다.
  따라서 병합정렬을 사용해서 스왑횟수를 알아내야한다.

출력

첫째 줄에 Swap 횟수를 출력한다

입력	출력
3 3 2 1	3

 

문제 풀이

• 버블정렬은 시간 복잡도가 n2 이라서 시간초과가 난다.. 왜 제목이 버블소트임..?어이없 암튼 그런 이유로 병합정렬을 사용해야한다!
• 스왑이 일어나는 횟수 구하기
  병합이 일어날때마다 각 자리에서 왼쪽으로 이동한만큼을 swap횟수에 더해준다.
  
  

실행 코드

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

public class P1517 {
    static long swap = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 입력받기
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++)
            A[i] = Integer.parseInt(st.nextToken());

        // 병합정렬
        mergeSort(A, 0, N-1);

        // 결과 출력 (정렬된 배열 확인)
        for (int i = 0; i < N; i++) {
            System.out.print(A[i] + " ");
        }
        System.out.print("swap : "+swap);
    }
    private static void mergeSort(int[] A, int S, int E){
        if(S<E){
            int mid = (S+E)/2;
            mergeSort(A, S, mid);
            mergeSort(A, mid+1, E);

            Merge(A, S, mid, E);
        }
    }

    private static void Merge(int[] A, int s, int mid, int e) {
        int[] sorted = new int[e-s+1];
        // 투포인터 사용
        int i = s;
        int j = mid+1;
        int idx = 0; //sorted배열 인덱스
        while(i<=mid && j<=e){
            if(A[i]<=A[j]) {
                sorted[idx++] = A[i++];
            }
            else{
                if(idx<j){
                    swap += (mid-i+1); //mid값은 첫번째 배열의 마지막 인덱스임
                }
                sorted[idx++] = A[j++];
            }
        }
        while(i<=mid){
            sorted[idx++] = A[i++];
        }
        while(j<=e){
            sorted[idx++] = A[j++];
        }
        // 원본 배열에 복사
        for(i = s, idx=0;i<=e;i++, idx++) {
            A[i] = sorted[idx];
        }
    }
}

 

 

 기수 정렬 : O(kn)

기수 정렬은 값을 비교하지 않는 특이한 정렬이다.
기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. 시간복잡도의 k가 자릿수에 해당한다.

• 기수 정렬은 0~9까지 수를 담기 위해 10개의 큐를 이용한다.
• 1의 자리수를 기준으로 큐에 넣고 출력한다. 이 출력값은 일의자리가 정렬된 수들이다. 이렇게 자릿수를 높여가며 진행한다.
  
  

 2750 : 수 정렬하기

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

문제 풀이

• 기수 정렬을 이용해서 풀어보려한다. -> 양수만 가능, 음수도 처리하려면 음수와 양수를 따로 정렬해서 합쳐야한다.

실행 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P2750_RadixSort {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
        }

        // 기수정렬
        radixSort(A);

        // 출력
        for(int i=0;i<N;i++){
            System.out.println(A[i]);
        }
    }

    private static void radixSort(int[] a) {
        // 큐 10개 만들기
        Queue<Integer>[] queues = new Queue[10];
        for(int i = 0;i<10;i++)
            queues[i] = new LinkedList<>();

        int max = maxNum(a); //가장 큰 수
        int exp = 1;

        // 자릿수 별로 정렬 수행
        while (max/exp > 0){
            for(int num : a){
                int digit = (num/exp) % 10; //해당 자릿수에 있는 수
                queues[digit].add(num); //자릿수에 있는 수에 해당하는 큐에 저장
            }

            // 자릿수마다 정렬된 결과를 배열에 복사
            int idx = 0;
            for(int i=0;i<10;i++){
                while(!queues[i].isEmpty())
                    a[idx++] = queues[i].poll();
            }
            exp*=10; //다음 자릿수로
        }
    }

    private static int maxNum(int[] a) {
        int max = a[0];
        for(int num : a){
            if(num>max)
                max = num;
        }
        return max;
    }
}