2751

수 정렬하기 2 : https://www.acmicpc.net/problem/2751

 

Collections.sort : 수행시간 2500ms

Quick sort : 시간초과 : O(n2)케이스가 있는 것으로 보임

Merge sort : 수행시간 880ms O(nLog n)의 안정적인 속도

 

참조 사이트 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

이번 문제풀면서 가장 잘못됐던 것은 , 그동안 즐겨 쓰던 아래의 형태가

엄청나게 성능에 영향을 준다는 것.

기존 : 

for (int v : arr)

  System.out.print(v + " ");

수행시간 : 4982ms

 

개선 :

for (int v : arr)

  sb.append(v).append(' ') or   sb.append(v).append('\n')

System.out.println(sb);

수행시간 : 820ms

 

 

 

그동안 출력문으로 인해 얻은 불이익이 상당히 크다는 것을 깨닫게 되었다.

심플하게 생각해봐도, 매번 출력을 하는 것과 sb에 저장된 내용을 한번에 출력하는 것의 속도차가 출력의 개수가 많을 수록 커진다는 것은 당연한 것이다.

 

//Collections.sort
import java.util.*;
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int N = sc.nextInt();

		ArrayList<Integer> a = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			a.add(sc.nextInt());
		}
		
		Collections.sort(a);
		for(int value : a)  sb.append(value).append('\n');
	
		System.out.println(sb);
  }
}

 

 

 

 

//Quick sort
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N;

	static int[] arr;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		arr = new int[N];
		for (int i = 0; i < N; ++i)
			arr[i] = Integer.parseInt(br.readLine());

		quick_sort(arr, 0, arr.length - 1);
		StringBuilder sb = new StringBuilder();
		for (int v : arr)
			sb.append(v).append('\n');
		System.out.println(sb);
	}

	private static void quick_sort(int[] list, int start, int end) {
		int pivot, low, high;

		if (start >= end)
			return;
		if(DBG)
		System.out.printf("sort %d %d\n ", start, end);
		pivot = list[start];
		low = start + 1;
		high = end;

		if(DBG)
		System.out.println("pivot : " + pivot + " low : " + low + " high : " + high);
		do {
			while (low < end && list[low] < pivot) {
				low++;
			}
			if(DBG)
			System.out.printf("%d %d\n ", start, high);
			while (start < high && list[high] > pivot)
				high--;
			if (low < high) {
				if(DBG)
				System.out.printf("swap %d %d\n ", low, high);
				swap(list, low, high);
			}
		} while (low < high);
		// high는 pivot보다 작은 요소 집합의 마지막을 가리킴
		// System.out.printf("swap high pivot[%d %d]\n", start, high);
		swap(list, start, high);

		if (DBG) {
			for (int v : list)
				System.out.print(v + " ");
			System.out.println();
		}
		quick_sort(list, start, high - 1);
		quick_sort(list, high + 1, end);

	}

	static void swap(int[] list, int a, int b) {
		int temp = list[a];
		list[a] = list[b];
		list[b] = temp;
	}

}

//merge sort
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N;
	static int[] arr, sorted;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		sorted = new int[N ];
		for (int i = 0; i < N; ++i)
			arr[i] = Integer.parseInt(br.readLine());

		merge_sort(arr, 0, arr.length - 1);
		StringBuilder sb = new StringBuilder();
		for (int v : arr)
			sb.append(v).append('\n');
		System.out.println(sb);
	}

	static void merge_sort(int[] list, int left, int right) {

		if (left < right) {
			int mid = (left + right) / 2;
			
			merge_sort(list, left, mid);
			merge_sort(list, mid + 1, right);
			merge(list, left, mid, right);
		}

	}

	static void merge(int[] list, int left, int mid, int right) {
		int i, j, k, l;
		i = left;
		j = mid + 1;
		k = left;

		while (i <= mid && j <= right) {
			if (list[i] <= list[j])
				sorted[k++] = list[i++];
			else
				sorted[k++] = list[j++];
		}

		if (i > mid) {
			for (l = j; l <= right; l++)
				sorted[k++] = list[l];
		} else {
			for (l = i; l <= mid; l++)
				sorted[k++] = list[l];
		}

		for (l = left; l <= right; l++) {
			list[l] = sorted[l];
		}

		// System.out.printf("merged left right [%d %d ]\n",left,right);
	}
}