정렬 | Notion

정렬

: 특정 규칙 순서대로 요소들을 나열하는 것.

container 구조에서 활용

arraylist, 또는 배열에서 많이 사용

treemap같은 경우 이미 정렬된 상태

(deque, queue, stack, hm ← 정렬하면 안되는 구조)

정렬

→ 오름차순 정렬 (default*)

→ 내림차순 정렬 (솔직히 필요는 없음 ← 기본 정렬이 아닌 자료구조의 우선순위)

⇒ 오름차순 정렬로 두고 뒤에서부터 보면 되기 때문에 굳이 정렬할 필요가 없음.

Integer[] arr = {3, 4, 5, 1, 2};
// 기본 정렬 -> 오름차순의 기본 정렬
Arrays.sort(arr);
for (int i=0; i<arr.length; i++)
		System.out.print(arr[i]);
System.out.println();

// 내림차순 정렬
// 배열 또는 arraylist에서 내림차순 정렬 할 이유 X
// -> 오름차순 정렬로 두고 뒤에서부터 보면 되기 때문
// treemap, priority queue →
// arrays.sort(container, Comparator)
// comparator = compare + ator class
// Comparator를 통해서 정렬 조건을 바꾸고 싶다면 → Wrapper type
Arrays.sort(arr, new cmp());
for (int i=0; i<arr.length; i++)
		System.out.print(arr[i]);
System.out.println();

// 얘랑 똑같은걸
Arrays.sort(arr, Collections.reverseOrder());
for (int i=0; i<arr.length; i++)
		System.out.print(arr[i]);
System.out.println();

// ArrayList 정렬
ArrayList<Integer> al = new ArrayList<>();
al.add(3);
al.add(1);
al.add(2);
Collecions.sort(); // Collections.reverseOrder() 사용 가능
for (int elem : al) {
		System.out.print(elem + " ");
}
System.out.println();

→ Comparator

static class cmp implements Comparator <Integer> {
		@Overide
		public int compare(Integer left, Integer right) {
				// left < right
				// right는 항상 left보다 커야 오름차순이 생성된다.
				// left - right = 음수 // 내가 원하는 오름차순이 유지될려면
				// left < right -> 음수를 리턴하게 된다.
				// right - left = 양수
				// return right - left;
				
				// -> 일단 모든 언어 공통으로 사용가능
				// -> java = int return, c++ = bool return
				
				// left < right 내가 우너하는 상황이다 ! -> 라고 하면 음수 리턴
				// 1 5
				if (left < right) return -1;
				// 5 1 -> 내가 원하는 오름차순의 상황이 아닌 것 -> 양수를 리턴
				if (left > right) return 1;
				// 마지막 무지성으론 stability
				return 0;
				// 내림차순 하고 싶으면 부등호만 바꿔주면 됨.
		}
}

정렬의 시간복잡도
- 최고로 좋고 빠른 정렬 알고리즘 구현해서 쓰는게 더 빠르지 않을까? → X
- 이미 STL에서 제공하는 정렬 기능은 최적이다.
  
  → 그럼 이게 어떻게 구현되었길래????????????
정렬 알고리즘은 언어마다 다르게 쓰임
- C++ : dual pivot quick sort
- java : timsort (insertion + merge + heap sort)
  - base 자체가 merge sort ⇒ 소모되는 메모리가 N
  - java에서 linked list를 정렬하는 게 위험
    - 보통 정렬 시 int → 1개 (4byte)
    - linked list = Node 메모리 큼. ⇒ Memory heap space error

class 정렬

static class Node {
		int y;
		int x;
		Node (int y, int x) {
				this.y = y;
				this.x = x;
		}
}

Node[] nodearr = new Node[5];
nodearr[0] = new Node(0, 0);
nodearr[1] = new Node(1, 100);
nodearr[2] = new Node(100, 1);
nodearr[3] = new Node(3, 5);
nodearr[4] = new Node(3, 500);

// y가 작은거 우선, x가 큰거 우선
Arrays.sort(nodearr);
for (int i=0; i<5; i++) {
		System.out.println(nodearr[i].y + " " + nodearr[i].x);
} // -> 에러 발생

// 1. 외부로 비교 가능한 코드를 만들어주는 방식
static class nodecmp implements Compatator <Node> {
		@Override
		public int compare(Node left, Node right) {
				// 원하는 조건을 우선순위가 높은 순으로 작성
				if (left.y < right.y) return -1;
				if (left.y > right.y) return 1;
				if (left.x > right.x) return -1;
				if (left.x < right.x) return 1;
				return 0;
		}
}

// 2. compare + able => 비교가 가능한 class로 만든다
static class Node implements Comparable <Node>{
		int y;
		int x;
		Node (int y, int x) {
				this.y = y;
				this.x = x;
		}
		@Override
		public int compareTo(Node o) {
				// 나 자신이 left, o = right
				if (y < o.y) return -1;
				if (y > o.y) return 1;
				if (x > o.x) return -1;
				if (x < o.x) return 1;
				return 0;
		}
}

→ pro 시험에서 정렬 쓸 일 많지 않음

→ #1. api 호출이 50만번인데 호출될때마다 정렬? 비효율적임

→ 정렬된게 필요하면 treemap 사용. 삽입때마다 log(N)