정렬 알고리즘 정리
정렬이란? 크기순으로 오름차순이나 내림차순으로 나열하는 것
모두에 최적인 정렬 알고리즘은 없음, 상황에 따라 잘 판단해야 한다.
- 단순하지만 비효율적 : 삽입, 선택, 버블
- 복잡하지만 효율적 : 퀵정렬, 히브정렬, 합병정렬(병합정렬) merge sort
1. 선택 정렬 (Selection Sort)
가장 작은 값을 찾아서 가장 맨 앞과 바꾼다. 제자리 정렬이다.
public class SelectionSort {
static void print(int arr[]) {
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
static void swap(int arr[], int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
static void sort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
print(arr);
int min = i; // 현재 사이클에서 최소값
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(arr, i, min);
}
}
public static void main(String[] args) {
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
sort(array);
print(array);
}
}2. 삽입 정렬 (Insertion Sort)
정렬 되어있는 부분에 새로운 정렬 되지 않은 것을 삽입하는 과정
public class InsertionSort {
static void print(int arr[]) {
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
static void swap(int arr[], int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
static void sort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
print(arr);
int target = i; // 현재 사이클에서 정렬할 대상
for (int j = i - 1; j >= 0; j--) {
if (arr[target] < arr[j]) {
swap(arr, target, j);
target = j; // 타겟을 이동시킨 지점으로, 타겟위치 지정
}
}
}
}
public static void main(String[] args) {
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
sort(array);
}
}3. 버블 정렬 (Bubble Sort)
앞 뒤를 바꾸어서 정렬하는 방법. 인접한 2개의 레코드를 비교하여 순서대로 되어있지 않으면 서로 교환, 0번 값부터 시작해서 제일 큰 값이 끝으로 이동한다.
public class BubbleSort {
static void print(int arr[]) {
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
static void swap(int arr[], int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
// 끝부터 자재로 정렬우다
static void sort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
print(arr);
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void main(String[] args) {
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
sort(array);
print(array);
}
}⚠️ 구현하기 쉬운 것들은 보통 최악의 경우 시간 복잡도가 O(n²) 이 나오므로 이는 매우 비효율적이다!!!
4. 합병 정렬 (Merge Sort)
재귀를 통한 divide and conquer 방식으로 구현된다.
- 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬
- 정렬된 두 개의 부분 리스트를 합하여 전체 리스트를 정렬함
→ Merge sort는 크기가 n인 리스트를 균등 분배하므로 O(n * log(n)) 의 복잡도를 가진다!!
public class MergeSort {
static void print(int arr[], int left, int right) {
for (int i = 0; i < arr.length; i++) {
if (i == left) {
System.out.print("[");
}
System.out.print(arr[i]);
if (i == right) {
System.out.print("] ");
} else {
System.out.print(" ");
}
}
System.out.println();
}
static void merge(int arr[], int left, int mid, int right) {
int[] left_arr = Arrays.copyOfRange(arr, left, mid + 1);
int[] right_arr = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0; // 왼쪽 배열 검사 인덱스
int j = 0; // 오른쪽 배열 검사 인덱스
int k = left; // 합병중인 배열의 현재 인덱스
while (i < left_arr.length && j < right_arr.length) {
if (left_arr[i] <= right_arr[j]) {
arr[k++] = left_arr[i++];
} else {
arr[k++] = right_arr[j++];
}
}
while (i < left_arr.length) {
arr[k++] = left_arr[i++];
}
while (j < right_arr.length) {
arr[k++] = right_arr[j++];
}
print(arr, left, right);
}
static void mergeSort(int[] arr, int left, int right) {
// left와 right로 분할 가능하다면
if (left < right) {
int mid = (right + left) / 2; // mid
// mid를 기준으로 두 마트로 분할
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right); // 분할한 결과 합병 (분할 정복)
}
}
static void sort(int arr[]) {
mergeSort(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
print(array, -1, -1);
sort(array);
}
}5. 퀵 정렬 (Quick Sort)
Pivot을 정하고 이를 중심으로 분할 한다음 정렬하는 것!!
- 기준값(pivot)을 중심으로 왼쪽에서 큰값과 오른쪽에 작은 값을 교환
- 기준값을 제일 마지막 작은 값과 교환
- 기준값을 중심으로 앞에는 기준값보다 작은 값
- 뒤에는 큰 값으로 나누어짐
- 기준값 앞과 뒤를 다시 순환적으로 퀵정렬 호출
| 포인터 | 동작 |
|---|---|
low | 피봇보다 작을 동안 계속 증가 → 피봇보다 크거나 같은 처음 값에서 멈춤 |
high | 피봇보다 클 동안 감소 → 피봇보다 작거나 같은 처음 값에서 멈춤 |
low < high면 low, high 값 교환low > high면 high와 피봇 교환 → 피봇이 옮겨간 위치는 더 이상 바뀌지 않는다
public class QuickSort {
static void print(int arr[]) {
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
static void swap(int arr[], int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
static int partition(int arr[], int left, int right) {
int pivot = arr[left]; // 피봇: 맨 왼쪽 값
int low = left + 1;
int high = right;
while (low <= high) {
// low: 피봇보다 크거나 같은 처음 값에서 멈춤
while (low <= right && arr[low] < pivot) {
low++;
}
// high: 피봇보다 작거나 같은 처음 값에서 멈춤
while (high >= left + 1 && arr[high] > pivot) {
high--;
}
if (low < high) {
swap(arr, low, high); // low < high 면 교환
}
}
swap(arr, left, high); // low > high 면 피봇과 high 교환
return high; // 피봇의 최종 위치 반환
}
static void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
print(arr);
quickSort(arr, left, pivot - 1); // 피봇 왼쪽 재귀
quickSort(arr, pivot + 1, right); // 피봇 오른쪽 재귀
}
}
static void sort(int arr[]) {
quickSort(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
sort(array);
print(array);
}
}알고리즘 비교 - 시간 복잡도
| 구분 | 최선 | 평균 | 최악 |
|---|---|---|---|
| 선택정렬 | O(n²) | O(n²) | O(n²) |
| 삽입정렬 | O(n) | O(n²) | O(n²) |
| 버블정렬 | O(n) | O(n²) | O(n²) |
| 힙정렬 | O(n log n) | O(n log n) | O(n log n) |
| 합병정렬 | O(n log n) | O(n log n) | O(n log n) |
| 셸정렬 | O(n log n) | O(n log n) | O(n²) |
| 퀵정렬 | O(n log n) | O(n log n) | O(n²) |
코딩 테스트에서는? - 내장 정렬 사용법
Arrays.sort()
배열을 정렬하는 데 사용되는 방법. 퀵 정렬과 병합 정렬을 결합한 듀얼 피벗(Dual-Pivot) 퀵 정렬을 사용한다.
- 삽입 정렬과 퀵의 정렬을 합친 형태이며, 작은 배열에 대해서는 삽입 정렬을, 큰 배열에 대해서는 퀵 정렬을 사용하는 방식
- 평균적으로는 O(nlogn)의 시간 복잡도이지만, 드물게 O(n²)의 최악의 경우가 발생할 수 있다는 것은 퀵 정렬과 동일하다.
1) 오름차순 정렬 (기본)
import java.util.Arrays;
public class SortExample1 {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 1, 3};
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));
}
}++ 문자열 또한 사전순으로 정렬됨!! 주의할점은 대문자보다 소문자가 먼저 정렬된다.
2) 내림차순 정렬
import java.util.*;
public class SortExample3 {
public static void main(String[] args) {
Integer[] numbers = {5, 2, 8, 1, 3};
Arrays.sort(numbers, Comparator.reverseOrder());
System.out.println(Arrays.toString(numbers));
}
}⚠️ 기본형
int[]는 Comparator를 사용할 수 없으므로, 래퍼 클래스Integer[]를 사용해야 한다.
3) 사용자 정의 정렬 (Comparator)
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() == o2.length()) {
return o1.compareTo(o2);
} else {
return o1.length() - o2.length();
}
}
});o1은 앞의 원소,o2는 뒤의 원소- 길이나 다른 조건으로도 정렬 가능!
Collections.sort()
컬렉션을 정렬하는 데 사용되는 방법. 합병 정렬과 삽입 정렬을 결합한 Timsort를 사용한다.
- 합병 정렬의 최악의 경우와, 삽입 정렬의 최선의 경우를 얻을 수 있는 방법이며, 시간복잡도는 O(n) ~ O(nlogn) 을 보장할 수 있다.
++
Collection.sort는List.sort(),Arrays.sort가 생기면서 이거 2개를 쓰는 것을 권장
List.sort()
배열 리스트 ArrayList를 정렬할 때 사용한다! 내장함수를 사용, 직접 구현도 가능하다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class SortArrayList {
public static void main(String[] args) {
// ArrayList 준비
ArrayList<String> list = new ArrayList<>(Arrays.asList("C", "A", "B", "a"));
System.out.println("원본 : " + list); // [C, A, B, a]
// 오름차순으로 정렬
list.sort(Comparator.naturalOrder());
System.out.println("오름차순 : " + list); // [A, B, C, a]
// 내림차순으로 정렬
list.sort(Comparator.reverseOrder());
System.out.println("내림차순 : " + list); // [a, C, B, A]
// 대소문자 구분없이 오름차순 정렬
list.sort(String.CASE_INSENSITIVE_ORDER);
System.out.println("대소문자 구분없이 오름차순 : " + list); // [a, A, B, C]
// 대소문자 구분없이 내림차순 정렬
list.sort(Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
System.out.println("대소문자 구분없이 내림차순 : " + list); // [C, B, a, A]
}
}객체 정렬 - Comparable, Comparator
객체 정렬시에는 Comparable, Comparator를 사용하여 정렬한다.
apples.sort(new Comparator<Apple>() {
@Override
public int compare(Apple o1, Apple o2) {
if (o1.getWeight() == o2.getWeight()) {
return o1.getName().compareTo(o2.getName());
}
return o1.getWeight() - o2.getWeight();
}
});💡 서로 다른 타입을 엮어서 데이터를 저장하는 방법
코딩 테스트에서 두 가지 이상의 타입을 묶어서 정렬해야 할 때는 다음 3가지 방법을 활용하자.
방법 1. String 배열로 저장 후 변환
// "나이 이름" 형태로 저장 후 파싱
String[] data = new String[N];
// ... 입력 후
Arrays.sort(data); // 사전순 정렬방법 2. 클래스(객체)로 만들어서 처리 ✅ 권장
static class Type {
int age;
String name;
}
// 나이순 정렬 예시
Arrays.sort(types, new Comparator<Type>() {
@Override
public int compare(Type o1, Type o2) {
return o1.age - o2.age;
}
});
for (int i = 0; i < N; i++) {
System.out.println(types[i].age + " " + types[i].name);
}전체 예시 - 나이순 정렬
public class 나이순정렬 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Type[] types = new Type[N];
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
Type type = new Type();
types[i] = type;
types[i].age = Integer.parseInt(st.nextToken());
types[i].name = st.nextToken();
}
Arrays.sort(types, new Comparator<Type>() {
@Override
public int compare(Type o1, Type o2) {
return o1.age - o2.age;
}
});
for (int i = 0; i < N; i++) {
System.out.println(types[i].age + " " + types[i].name);
}
}
static class Type {
int age;
String name;
}
}방법 3. HashMap 활용 (단, 중복 key 불가)
// Map은 중복을 허용하지 않으므로 key가 unique한 경우에만 사용!
Map<Integer, String> map = new HashMap<>();
map.put(20, "Alice");
map.put(25, "Bob");
// 정렬
List<Map.Entry<Integer, String>> entries = new ArrayList<>(map.entrySet());
entries.sort(Map.Entry.comparingByKey());⚠️ Map은 key 단위에서 중복을 허용하지 않으므로, 나이가 같은 사람이 여럿인 경우엔 클래스(방법 2)를 활용하는 것이 안전하다.
✅ 최종 정리
알고리즘 선택 기준
| 상황 | 추천 알고리즘 |
|---|---|
| 데이터가 거의 정렬되어 있을 때 | 삽입 정렬 O(n) |
| 메모리가 제한적일 때 (제자리 정렬 필요) | 선택 정렬, 퀵 정렬 |
| 안정적인 정렬이 필요할 때 (같은 값의 순서 유지) | 합병 정렬, 삽입 정렬 |
| 일반적인 대용량 데이터 | 퀵 정렬, 합병 정렬 |
| 코딩 테스트 (Java) | Arrays.sort() / List.sort() 활용 |
정렬 알고리즘 핵심 요약
| 알고리즘 | 핵심 아이디어 | 시간복잡도(평균) | 공간복잡도 | 안정 정렬 |
|---|---|---|---|---|
| 선택 정렬 | 최솟값을 찾아 맨 앞과 교환 | O(n²) | O(1) | ❌ |
| 삽입 정렬 | 앞의 정렬된 영역에 끼워넣기 | O(n²) | O(1) | ✅ |
| 버블 정렬 | 인접 원소 비교 후 교환 | O(n²) | O(1) | ✅ |
| 합병 정렬 | 분할 후 정렬하며 합병 | O(n log n) | O(n) | ✅ |
| 퀵 정렬 | 피봇 기준 좌우 분할 재귀 | O(n log n) | O(log n) | ❌ |
Java 내장 정렬 정리
| 메서드 | 대상 | 내부 알고리즘 | 시간복잡도 |
|---|---|---|---|
Arrays.sort(int[]) | 기본형 배열 | Dual-Pivot 퀵 정렬 | O(n log n) 평균 |
Arrays.sort(T[], Comparator) | 객체 배열 | Timsort | O(n log n) 보장 |
Collections.sort() | List | Timsort | O(n log n) 보장 |
List.sort() | List | Timsort | O(n log n) 보장 |
Comparator compare() 반환값 규칙
compare(o1, o2) 반환값:
음수 → o1이 o2 앞에 위치 (오름차순)
0 → 순서 유지
양수 → o1이 o2 뒤에 위치 (내림차순)
오름차순: return o1 - o2; (또는 o1.compareTo(o2))
내림차순: return o2 - o1; (또는 o2.compareTo(o1))다중 조건 정렬 패턴 (코테 단골!)
// 1순위: 나이 오름차순, 2순위: 이름 사전순
Arrays.sort(types, new Comparator<Type>() {
@Override
public int compare(Type o1, Type o2) {
if (o1.age == o2.age) {
return o1.name.compareTo(o2.name); // 2순위: 이름순
}
return o1.age - o2.age; // 1순위: 나이순
}
});
// Lambda로 간결하게 (Java 8+)
Arrays.sort(types, (o1, o2) -> {
if (o1.age == o2.age) return o1.name.compareTo(o2.name);
return o1.age - o2.age;
});서로 다른 타입 묶어서 정렬할 때 선택 기준
중복 가능성 있음?
├─ YES → 클래스(static class) or String 배열 사용 ✅
└─ NO → HashMap 사용 가능 (단, key 중복 불가 주의)
정렬 기준이 복잡함?
├─ YES → 클래스 + Comparator 조합이 가장 유연 ✅
└─ NO → String 배열 + Arrays.sort() 로 간단히 처리