정렬 정리

정렬 (Sorting)

🔍 개요

• 시간 복잡도 기준
  • O(N²) : 버블, 선택, 삽입 → N이 작을 때만 사용
  • O(N log N) : 퀵, 병합, 힙, Java 내장 정렬
  • O(N + K) : 계수 정렬 (Counting Sort, K=값의 범위)
• 직접 알고리즘 구현보다, 정렬 기준을 어떻게 잘 잡는지가 중요

---

📚 정렬 종류

1. 기본 배열 정렬

int[] arr = {5, 2, 9, 1};
Arrays.sort(arr); // 오름차순

2. 내림차순 정렬

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

3. 객체 배열 정렬 (Comparator)

class Person {
	String name;
	int age;
	Person(String name, int age) {
		this.name = name;
		this.age = age;
	}
}
 
Person[] people = {
	new Person("kim", 25),
	new Person("Lee", 20),
	new Person("Park", 30)
};
 
// 나이 오름차순
Arrays.sort(people, Comparator.comparingInt(p -> p.age));
 
// 나이 내림차순
Arrays.sort(people, (a, b) -> b.age - a.age);
 
// 이름 사전순
Arrays.sort(people, Comparator.comparing(p -> p.name));

4. 리스트 정렬

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

---

✅ 주요 정렬 알고리즘 개념

1. 선택 정렬 (Selection Sort)

• 아이디어 : 매번 가장 작은 데이터를 선택해서 앞으로 보냄
• 시간 복잡도 : O(N²)

for(int i = 0; i < n-1; i++) {
	int minIdx = i;
	for(int j = i+1; j < n; j++) {
		if(arr[j] < arr[minIdx]) {
			minIdx = j;
		}
	}
	
	int tmp = arr[i];
	arr[i] = arr[minIdx];
	arr[minIdx] = tmp;
}

2. 삽입 정렬 (Insertion Sort)

• 아이디어 : 이미 정렬된 구간에 새로운 원소를 끼워 넣음
• 시간 복잡도 : O(N²), 거의 정렬된 상태면 빠름.

for(int i = 1; i < n; i++) {
	int key = arr[i];
	j = i-1;
	
	while(j >= 0 && arr[j] > key) {
		arr[j+1] = arr[j];
		j--;
	}
	
	arr[j+1] = key;
}

3. 퀵 정렬 (Quick Sort)

• 아이디어 : 피벗을 기준으로 좌우 분할 → 재귀
• 시간 복잡도 : 평균 O(N log N), 최악 O(N²)

static void quickSort(int[] arr, int left, int right) {
	if(left >= right) {
		return;
	}
	
	int pivot = arr[(left + right) / 2];
	int i = left;
	int j = right;
	while(i <= j) {
		while(arr[i] < pivot) {
			i++;
		}
		while(arr[j] > pivot) {
			j--;
		}
		if(i <= j) {
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	}
	quickSort(arr, left, j);
	quickSort(arr, i, right);
}

4. 병합 정렬(Merge Sort)

• 아이디어 : 배열을 반으로 쪼개 정렬 후 합침
• 시간 복잡도 : O(N log N)

static void mergeSort(int[] arr, int left, int right) {
	if(left >= right) {
		return;
	}
	
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	merge(arr, left, mid, right);
}

---

❓ 정렬 활용

(A) 여러 기준 정렬

// 국어 점수 내림차순, 같으면 영어 점수 오름차순
Arrays.sort(students, (a, b) -> {
	if(a.korean != b.korean) {
		return b.korean - a.korean;
	}
	return a.english - b.english;
});

(B) 정렬 후 스위핑

• 구간 겹침 체크, 최대 동시 진행 → 정렬 후 한번 훑기.

(C) 정렬 + 투 포인터

• 두 배열 합, 차이 최소, 특정 합 찾기

(D) 정렬 + 이진탐색

• 데이터 정렬 → Arrays.binarySearch 또는 직접 구현