병합 정렬

수 정렬하기2

Question - 2751

Code

병합 정렬

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

public class Main {
    
    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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        tmp = new int[N + 1];
    
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
    
        merge_sort(1 , N);
        for (int i = 1; i <= N; i++) {
            bw.write(A[i] + "\n");
        }
    
        bw.flush();
        bw.close();
    }
    
    private static void merge_sort(int s, int e) {
        if ( e - s < 1)
            return ;
        int m = s + (e - s) / 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[index2];
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

함수

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class N20_P2751_수_정렬하기2 {

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

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

        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

Isight

Idea

reference

버블 소트 프로그램2

Question - 1517

Code

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

public class Main {
    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 + 1];
        tmp = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        result = 0;
        merget_sort(1, N);
        System.out.println(result);
    }
    
    private static void merget_sort(int s, int e) {
        if(e - s < 1)
            return;
        int m = s + (e - s) / 2;
        
        // 재귀 함수 형태로 구현하기
        merget_sort(s, m);
        merget_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[index2];
                result = result + index2 - k;
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
            
        }
        
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

Insight

Idea

reference