정렬 : Sorting

1. 정렬 조건이 필요하다

   • 어떤것이 더 앞에 와야하는지
   • ex) 오름차순

     static class Elem implements Comparable<Elem>{
     
     	@overide
     	public int compareTo(Elem other){
     		return num - other.num;
     
     		//return 음수 : 내(num)가먼저
     		//return 양수 : 쟤(other)가 먼저
     	}
     
     }

2. 시간복잡도 :: O(N log N)

   • 자바에서 기본적으로 제공해주는 정렬 함수 이용하면 됨.
   • N개의 원소를 정렬하는 것은 O(N log N)만큼 시간복잡도를 갖는다.
   • primitive 원소 정렬
     • Dual-Pivot Quick Sort → In-place
     • 평균 O(N log N)
     • 최악의 경우 O(N^2) 시간초과 가능
   • Object 원소 정렬
     • Tim Sort → Stable Sort
     • 평균 O(N log N)
     • 최악에도 O(N log N)보장
     • 그럼 무조건 object가 좋은것이냐? 아니다. In-place 가 아니라 시간초과 가능

   → 따라서, primitive는 In-place, Object는 Stable 모두 평균 O(N log N)

3. In-place / Stable 여부를 알아야한다.

   • In-place
     • 정렬 과정에 n에 비해 충분히 무시할만큼의 메모리만 사용되는가
     • ex) 10만개 정렬하는데 10개만큼 메모리만 사용하는가, 10만개에 10만개 필요하면 그건 안됨
   • Stable
     • 동등한 위상 원소들의 순서 관계가 보존되는가?
     • ex) 비교할 수 없는 원소들 (5와5) 간에, 1번5가 나오고 2번5가 나오는가

4. 정렬 후,

   1. 같은 정보들은 인접해 있을 것이다.
   2. 각 원소마다, 가까운 원소는 자신의 양 옆에 있다.

정렬 | BOJ_10825, BOJ_1015, BOJ_11652, BOJ_15970