아래 내용은 코테용 정렬 정리본입니다.

정렬 코테 총 정리

1. 배열 Array 정렬

1-1 기본 타입 배열 오름차순

int[] arr1 = {5,2,8,1,9}; 
//오름차순 
Arrays.sort(arr1); // 1,2,5,8,9
//범위 지정 정렬 (0~2번 인덱스만 정렬 
Arrays.sort(arr1, 0, 3); // 2,5,8,1,9

1-2 Wrapper 클래스 배열 내림차순

Integer[] arr = {5,2,8,1,9}; 
Arrays.sort(arr, Collections.reverseOrder()); 

1-3 String 배열 (사전순)

String[] strArr = {"banana", "apple", "cherry"};
Arrays.sort(strArr); //apple, banana, cherry

1-4 람다식 정렬

Integer[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr, (a, b)-> a-b); //오름차순 
Arrays.sort(arr, (a,b)-> b-a); //내림차순 

1-5 복잡한 조건 정렬 (홀수 우선, 같으면 오름차순)

Integer[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr, (o1, o2)-> {
	if(o1 %2 !=0 && o2%2 ==0) return -1; //o1이 홀수 일때 우선 
	if (o1 % 2 == 0 && o2 % 2 != 0) return 1; 
	return o1-o2; //오름 차순 
}); 

---

2. List 정렬

2-1 Collections.sort() 사용

List<Integer> list = new ArrayList<>(Arrays.asList(5,2,8,1,9)); 
//오름차순 
Collections.sort(list); 
//내림차순 
Collections.sort(list, Collections.reverseOrder()); 

2-2 list.sort() 사용 (java 8+)

list.sort(Comparator.naturalOrder()); 

list.sort(Comparator.reverseOrder()); 

2-3 람다식

//오름차순 
list.sort((a,b)-> a-b);  

---

3. 객체 정렬 - Comparable 인터페이스

Person Class에서 compareTo 메서드 오버라이드

Class Person implements Comparable<Person>{
	String name;
    int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override 
    public int compareTo(Person other){
	    return this.age - other.age; //나이 기준 오름 차순 
    }
    
    @Override 
    publis String toString(){
	    return name + "(" + age + ")"; 
    }
    
}

main 메서드

List<Person> people = new ArrayList<>(); 
people.add(new Person("김철수", 25));
people.add(new Person("이영희", 20));
people.add(new Person("박민수", 30));

Collections.sort(people); //compareTo()기준 정렬 
//역순 정렬 
Collections.sort(people, Collections.reverseOrder()); 

        

---

4. 객체 정렬 - Comparator 인터페이스

Student class

class Student {
    String name;
    int score;
    int age;
    
    public Student(String name, int score, int age) {
        this.name = name;
        this.score = score;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + "(" + score + "점, " + age + "세)";
    }
}

main 메서드

List<Student> students = new ArrayList<>();
        students.add(new Student("김철수", 85, 20));
        students.add(new Student("이영희", 90, 22));
        students.add(new Student("박민수", 85, 21));
//1. 점수 기준 내림차순
students.sort((s1, s2)-> s2.score - s1.score); 

//2. 점수가 같으면 나이 오름차순    
students.sort((s1,s2) -> {
	if(s1.score!=s2.score){
		return s2.score- s1.score; //점수 내림차순
	}
	return s1.age - s2.age; //나이 오름차순 
} 

//3. Comparator 메서드 체이닝 !! 
students.sort(Comparator.comparingInt((Student s) -> s.score).reversed()
													.thenComparingInt(s-> s.age); 

// 4. 이름 기준 사전 순 
students.sort(Comparator.comparing(s-> s.name)); 
													

---

5. 2차원 배열 정렬

int[][] arr = {{3, 5}, {1, 2}, {5, 3}, {1, 7}};

//1. 첫번째 원소 기준 오름차순 
Arrays.sort(arr, (a, b)-> a[0]- b[0]); 

//2. 첫번째 같으면 두번째 기준 
Arrays.sort(arr, (a, b)-> {
	if(a[0] !=b[0]) return a[0] - b[0]; //첫번째 오름차순 
	return a[1]- b[1]; //두번째 오름차순 
}); 

//3. 두번째 원소 기준 내림차순 
Arrays.sort(arr, (a, b)-> b[1]- a[1]); 

---

6. 특수 자료 구조 정렬

Priority Queue 정렬

// 1. 최소 힙
PrioriyQueue<Integer> minHeap = new PrioriyQueue<>(); 
minHeap.addAll(Arrays.asList(5,2,8,1,9)); 
//출력- 최소 힙 
while(!minHeap.isEmpty()){
	System.out.print(minHeap.poll() + " " ); 
}

// 2. 최대힙 
PrioriyQueue<Integer> maxHeap = new PrioriyQueue<>(Collections.reverseOrder()); 
maxHeap.addAll(Arrays.asList(5,2,8,1,9)); 
while(!minHeap.isEmpty()){
	System.out.print(minHeap.poll() + " " ); 
}

TreeSet- 자동 정렬 + 중복 제거

TreeSet<Integer> treeSet = new TreeSet<>(Arrays.asList(5, 2, 8, 1, 9, 2));
System.out.println("TreeSet (중복 제거): " + treeSet);

TreeMap- key자동 정렬

TreeMap<String, Integer> treeMap = new TreeMap<>(); 
treeMap.put("banana", 3);
treeMap.put("apple", 1);
treeMap.put("cherry", 2);
System.out.println("TreeMap: " + treeMap);

---

7. 문자열 정렬 특수 케이스

String[] words = {"apple", "pie", "banana", "cat"};

//1. 길이 기준 정렬 
Arrays.sort(words, (a,b) -> a.length() - b.length()); 

//2. 길이 같으면 사전순 
Arrays.sort(words, (a, b)-> {
	if(a.length() != b.length()) return a.length()- b.length(); 
	return a.compareTo(b); 
}); 

//3. 대소문자 구분 없이 정렬 
String[] words3 = {"Apple", "banana", "Cherry"};
Arrays.sort(words3, String.CASE_INSENSITIVE_ORDER); 

---

8. 코테용 자주 쓰는 정렬 패턴

Integer[] arr1 = {-5, 2, -8, 1, 9};

절댓값 기준 정렬

Arrays.sort(arr1, (a,b)-> Math.abs(a)- Math.abs(b));

특정 값과의 거리 기준 정렬

int target = 5; 
Integer[] arr2 = {1, 3, 7, 9, 2};
Arrays.sort(arr2, (a, b)-> Math.abs(a-target)- Math.abs(b-target)); 

빈도수 기준 정렬

Integer[] arr3 = {1, 1, 2, 2, 2, 3};
Map<Integer, Integer> freqMap =  new HashMap<>(); 
for (int num: arr3){
	freqMap.put(num, freqMap.getOrDefault(num, 0) +1); 
}
//빈도수 내림차순 
Arrays.sort(arr3, (a,b)-> freqMap.get(b) - freqMap.get(a)); 

---

9. 정렬 주의사항 및 시간 복잡도

시간 복잡도

• Arrays.sort()

- 기본 타입(int[]): O(n log n) - Dual-Pivot Quicksort”

- 객체 타입(Integer[]): O(n log n) - TimSort”

주의사항

• int[] 배열은 Comparator 사용 불가 → Integer[] 사용
• 람다식 (a, b)→ a-b 오버플로우 주의
  • 안전한것은 Integer.compare(a,b)
• 내림차순 Collections.reverseOrder()또는 (a,b)→ b-a

Comparable vs Comparator

• Comparable: 클래스 내부에 compareTo() 구현 (기본 정렬)
• Comparator: 외부에서 compare() 구현 (사용자 정의 정렬)

stable sort

• Arrays.sort(객체 배열), Collections.sort() : 안정 정렬 o
• Arrays.sort(기본 타입) : 안정 정렬 x