java util 의 정렬

• 직접 정렬 알고리즘을 구현하는 것 보다 java util 의 라이브러리를 사용한 정렬이 더욱 디테일하게 최적화가 되어있기 때문에
  접근성과 효율적인 측면 모두 사용하지 않을 이유가 없다.

✏️ Arrays.sort

🔗 퀵 정렬

• dual-pivot Quick Sort 즉, 퀵 정렬 알고리즘을 사용해 정렬해준다.
• 평균 시간복잡도는 O(nlogn) 이지만, 최악의 경우 O(n^2) 의 시간복잡도를 갖는다.

✏️ Collections.sort

🔗 병합 정렬

• Tim sort 알고리즘을 사용해 정렬해준다.
  • Tim sort 는 병합정렬 및 삽입정렬 알고리즘을 사용하는 정렬 방식이다.
  • 이렇게 두가지가 섞인 정렬 알고리즘을 hybrid sorting algorithm 이라고 한다.
• 병합 정렬은 최선, 최악의 경우 모두 O(nlogn) 의 시간 복잡도를 보장해준다.
• 삽입 정렬은 최선의 경우 O(n), 최악의 경우 O(n^2) 의 시간복잡도를 갖는다.
  • 이 두 알고리즘의 장점을 사용하는 Tim sort 는 O(n) ~ O(nlogn) 을 보장하는 매우 신속한 정렬 알고리즘이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
		/*
		  -1000000 ~ 1000000
		  기준점 0 = index 100000 으로 생각
		*/
		boolean[] arr = new boolean[2000001];	
        
		int N = Integer.parseInt(br.readLine());
        
		for(int i = 0; i < N; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000000] = true;
		}
 
		for(int i = 0; i < arr.length; i++) {
			if(arr[i]) {
				sb.append((i - 1000000)).append('\n');
			}
		}
		System.out.print(sb);
	}
}