[백준] 1517번 버블 소트 - 병합 정렬 / 버블 정렬

문제

 

 

My Code

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


public class Main {
static int[] testArray;
static int count;
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int[] array = new int[N];
testArray = new int[N];
count = 0;

StringTokenizer st = new StringTokenizer(bf.readLine());

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

mergesort(array, 0, N-1);

System.out.println(count);
}

private static void mergesort(int[] arr, int left, int right) {
int mid;

if(left < right){
mid = (left+right)/2;
mergesort(arr, left, mid);
mergesort(arr, mid+1, right);

merge(arr, left, mid, right);
}
}

private static void merge(int[] arr, int left, int mid, int right) {
int i, j, k;
i = left;
j = mid+1;
k = left;
while (i <= mid && j <= right){
if (arr[i] <= arr[j]){
testArray[k++] = arr[i++];
}
else {
count += mid - i + 1;
testArray[k++] = arr[j++];
}
}
if (i > mid) {
for (int a = j; a <= right; a++) testArray[k++] = arr[a];
}
else{
for (int a = i; a <= mid; a++)testArray[k++] = arr[a];
}

for (int b = left; b <= right; b++){
arr[b] = testArray[b];
}
}
}