알고리즘) 4장

 

 

 

1. "해시(Hash)는 넣어줄 필요 없나?"

네, 맞습니다!

• HashMap이나 HashSet은 데이터를 무작위로(해시값에 따라) 저장하기 때문에 정렬이라는 개념이 없습니다. 그래서 생성자에 Comparator를 넣는 칸 자체가 없습니다.

2. "리스트(ArrayList)도 넣어줄 수 있나?"

리스트는 조금 독특합니다.

• 생성할 때: 말씀하신 대로 new ArrayList<>(10) 처럼 **용량(Capacity)**을 넣지, Comparator를 넣지는 않습니다. 리스트는 기본적으로 "넣은 순서대로" 보관하는 게 목적이니까요.
• 정렬할 때: 하지만 리스트에 담긴 내용물을 정렬하고 싶을 때는 Comparator를 씁니다. 이때는 생성자가 아니라 메서드에 넣어줍니다.
  • 예: list.sort(new MyComp()); (리스트야, 이 심판의 규칙대로 정렬해!)

 

 

 

 

"그럼 언제 클래스 생성할 때 넣어주나?" (핵심!)

TreeSet이나 TreeMap**을 만들 때 생성자에 넣어줍니다.

// 생성할 때부터 "너는 이 심판(MyComp)의 규칙을 따라라"라고 지정
TreeSet<String> ts = new TreeSet<>(new MyComp());

• 이유: 얘네들은 데이터를 넣자마자 즉시 정렬해야 하기 때문입니다. "나중에 정렬할게~"가 아니라, 데이터를 하나 넣을 때마다 심판(Comparator)에게 "얘 어디다 세워야 하니?"라고 물어봐야 해서 처음부터 심판을 고용해서 넣어주는 것입니다.

 

 

TreeMap의 키(Key) 타입과 심판(Comparator)이 담당하는 타입이 서로 다르기 때문

 

• 원래 TreeMap에 넣는 키(C)는 스스로 비교할 줄 아는 능력(Comparable)이 있어야 합니다.
• 하지만 지금처럼 생성자에 심판(Comparator)을 직접 고용해서 넣어주면, C 클래스에 implements Comparable이 없어도 아무 문제 없이 잘 돌아갑니다. (심판이 대신 일해주니까요!)

 

 

거꾸로 만드는 다양한 방법들

 

 

이어서 계속 비교하는 방법들 

 

 

 

 

• comp.reversed(): " "앞번호부터 줄 서!"라는 규칙을 "뒷번호부터 줄 서!"로 규칙 자체를 바꾸는 것입니다.( 반대 규칙을 가진 새 객체 반환
• Collections.reverse(list): "이미 이 바구니(List)에 [1, 2, 3]이 들어있지? 이걸 [3, 2, 1]로 바꿔라!" ( 반환값 없음 (기존 리스트가 직접 변경됨) )
• *Collections.reverseOrder()

우리가 숫자를 [1, 5, 3] 정렬하면 보통 [1, 3, 5]가 됩니다. 이걸 반대로 [5, 3, 1]로 정렬하고 싶을 때, 매번 MyComp 같은 클래스를 직접 만드는 건 귀찮은 일이죠.

그럴 때 **Collections.reverseOrder()**를 쓰면 자바가 미리 만들어둔 "역순 정렬용 리모컨(Comparator)"을 바로 가져다 쓸 수 있습니다.

 

 

 

• 그냥 평범하게(오름차순) 정렬할래! → Collections.sort(myList);
• 내가 정한 특별한 규칙으로 정렬할래! → Collections.sort(myList, myComparator);

 

thencompare로 만든것 자체도 comparator클래스니깐, 최종적으로는 이걸 트리맵의 생성자에 넣어야하는거지 ?ㅇㅇㅇ

 

 

 

 

 

Arrays.sort()

Primitive data type 의경우  Dual-Pivot Quicksort

Object type 의경우  Mergesort 

 

Collections.sort() 

Mergesort 

 

 

1. 숫자(기본 타입) 정렬은 속도가 제일 중요해서 퀵소트를 쓴다.
2. 객체 정렬은 데이터 순서가 뒤섞이지 않는 안정성이 중요해서 병합 정렬(Mergesort) 계열을 쓴다.
3. **Collections.sort()**는 리스트를 직접 정렬하는 게 아니라, 배열로 바꿔서 Arrays.sort()의 기능을 빌려 쓰고 다시 리스트로 돌려주는 방식