선택 정렬
시간복잡도 : 최선 O(n^2), 최악 O(n^2)
- 방식
1
2
3
4
| 1) 리스트에서 최솟값(또는 최댓값)을 찾음
2) 그 값을 맨 앞의 값과 교환
3) 첫 번째 원소를 제외하고 나머지 리스트에 대해 같은 작업 반복
4) 리스트의 끝까지 반복하면 정렬 완료
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [1], 3, 4, 5, 2 | 전체 중 최솟값 1 → 첫 번째 값(5)과 교환 |
| 2 | 1, [2], 4, 5, 3 | 나머지(3~끝) 중 최솟값 2 → 두 번째 값(3)과 교환 |
| 3 | 1, 2, [3], 5, 4 | 나머지 중 최솟값 3 → 제자리 유지 |
| 4 | 1, 2, 3, [4], 5 | 나머지 중 최솟값 4 → 네 번째 값(5)과 교환 |
| 5 | 1, 2, 3, 4, 5 | 정렬 완료 |
- C++ 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int find_max_idx(vector<int> arr, int last) {
int value = 0;
int idx = 0;
for (int i = 0; i <= last; i++) {
if (value < arr[i]) {
value = arr[i];
idx = i;
}
}
return idx;
}
void selection_sort(vector<int> arr) {
for (int i = arr.size() - 1; i >= 1; i--) {
int max_idx = find_max_idx(arr, i);
if (max_idx != i) {
swap(arr[max_idx], arr[i]);
}
}
}
|
삽입 정렬
시간복잡도 : 최선 O(n), 최악 O(n^2)
- 방식
1
2
3
4
| 1) 두 번째 원소부터 시작해, 그 앞쪽(정렬된 부분)의 원소들과 비교
2) 현재 원소보다 큰 원소들은 오른쪽으로 한 칸씩 이동
3) 빈자리에 현재 원소를 삽입
4) 리스트의 끝까지 반복하면 정렬 완료
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [2, 5], 4, 6, 1, 3 | 두 번째 원소(2)를 정렬된 부분(5)과 비교 → 5 앞에 삽입 |
| 2 | [2, 4, 5], 6, 1, 3 | 세 번째 원소(4)를 정렬된 부분(2, 5)과 비교 → 2 뒤, 5 앞에 삽입 |
| 3 | [2, 4, 5, 6], 1, 3 | 네 번째 원소(6)는 올바른 위치에 있어 이동 없음 |
| 4 | [1, 2, 4, 5, 6], 3 | 다섯 번째 원소(1)를 정렬된 부분과 비교 → 맨 앞에 삽입 |
| 5 | [1, 2, 3, 4, 5, 6] | 여섯 번째 원소(3)를 2와 4 사이에 삽입 → 정렬 완료 |
- C++ 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void insertion_sort(int N, int * arr){
for(int i = 1; i < N; i++){
int loc = i - 1;
int p = arr[i];
while(0 <= loc && p < arr[loc]){
arr[loc + 1] = arr[loc];
loc--;
}
if (loc+1 != i){
arr[loc + 1] = p;
}
}
}
|
버블 정렬
시간복잡도 : 최선 O(n), 최악 O(n^2)
- 방식
1
2
3
4
| 1) 첫 번째 원소부터 시작해서 인접한 두 원소를 비교하고, 크기가 잘못된 경우 교환
2) 리스트의 끝까지 반복하면서 가장 큰 값을 맨 뒤로 보냄
3) 나머지 리스트에 대해 같은 작업을 반복
4) 리스트가 정렬될 때까지 반복
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [3, 2, 5, 1, 4] | |
| 1 | [2, 3, 5, 1, 4] | 첫 번째 비교 (3, 2) → 교환하여 [2, 3, 5, 1, 4] |
| 2 | [2, 3, 5, 1, 4] | 두 번째 비교 (3, 5) → 교환 없음 |
| 3 | [2, 3, 1, 5, 4] | 세 번째 비교 (5, 1) → 교환하여 [2, 3, 1, 5, 4] |
| 4 | [2, 3, 1, 4, 5] | 네 번째 비교 (5, 4) → 교환하여 [2, 3, 1, 4, 5] |
| 5 | [2, 1, 3, 4, 5] | 첫 번째 비교 (3, 1) → 교환하여 [2, 1, 3, 4, 5] |
| 6 | [1, 2, 3, 4, 5] | 두 번째 비교 (2, 1) → 교환하여 [1, 2, 3, 4, 5] |
- C++ 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void bubble_sort(int arr[], int n) {
// n-1번 반복 (마지막 원소는 자동으로 정렬됨)
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 이번 회차에 교환이 일어났는지 체크
// 인접한 두 원소를 비교하여 필요시 교환
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// 한 번의 패스에서 교환이 없었다면 이미 정렬된 상태이므로 종료
if (!swapped)
break;
}
}
|
병합 정렬
시간복잡도 : 분할 O(logN), 합병 O(N) -> O(NlogN)
- 방식
1
2
3
4
5
| 1) 리스트를 재귀적으로 두 개의 하위 리스트로 나누어가며 정렬.
2) 각 하위 리스트가 하나의 원소만 남을 때까지 분할.
3) 두 하위 리스트를 병합(merge)하여 하나의 정렬된 리스트를 만듦.
4) 병합 과정에서 두 하위 리스트의 원소를 비교하며, 작은 값을 먼저 새로운 리스트에 추가.
5) 분할된 리스트가 모두 병합될 때까지 이 작업을 반복.
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [5, 2, 4, 3, 1] | 리스트를 반으로 나눕니다: [5, 2, 4]와 [3, 1] |
| 2 | [5, 2, 4], [3, 1] | [5, 2, 4]와 [3, 1]을 다시 각각 분할합니다: [5, 2] [4], [3] [1] |
| 3 | [5, 2], [4], [3], [1] | 리스트를 더 이상 나누지 않으면 각 리스트는 하나의 원소만 남습니다. |
| 4 | [2, 5], [4], [1, 3] | 두 개의 원소가 있는 리스트들을 정렬합니다. [5, 2] → [2, 5], [3, 1] → [1, 3] |
| 5 | [2, 5], [1, 3], [4] | 이제 병합 준비 완료. 각각의 리스트를 병합하면서 정렬합니다. |
| 6 | [1, 2, 3, 4, 5] | 마지막으로 [2, 5], [1, 3], [4]를 병합하여 완전히 정렬된 리스트를 만듭니다. |
- C++ 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| void merge(vector<int>& arr, int left, int mid, int right) {
int i = left; // 왼쪽 배열 시작 인덱스
int j = mid + 1; // 오른쪽 배열 시작 인덱스
vector<int> temp; // 병합 결과를 임시 저장할 배열
// 두 배열을 비교하며 작은 값을 temp에 추가
while (i <= mid && j <= right) {
if (arr[i] <= arr[j])
temp.push_back(arr[i++]);
else
temp.push_back(arr[j++]);
}
// 남은 원소들 처리
while (i <= mid) temp.push_back(arr[i++]);
while (j <= right) temp.push_back(arr[j++]);
// 정렬된 결과를 원본 배열에 복사
for (int k = 0; k < temp.size(); k++)
arr[left + k] = temp[k];
}
// 병합 정렬 (재귀적으로 분할)
void merge_sort(vector<int>& arr, int left, int right) {
if (left >= right) return; // 원소가 하나면 정렬 완료
int mid = (left + right) / 2;
merge_sort(arr, left, mid); // 왼쪽 반 정렬
merge_sort(arr, mid + 1, right); // 오른쪽 반 정렬
merge(arr, left, mid, right); // 두 반을 병합
}
|
퀵 정렬
시간복잡도 : 최선 O(NlogN), 최악 O(n^2)
- 방식
1
2
3
4
5
| 1) 리스트에서 기준 원소(pivot)를 하나 선택합니다.
2) 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다.
3) 왼쪽 부분리스트와 오른쪽 부분리스트에 대해 같은 과정을 재귀적으로 반복합니다.
4) 각 부분리스트의 크기가 1 이하가 될 때까지 분할과 정렬을 수행합니다.
5) 모든 부분리스트가 정렬되면, 이를 병합하여 전체 정렬이 완료됩니다.
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [5, 2, 4, 3, 1] | 피벗을 5로 선택합니다. 피벗보다 작은 [2, 4, 3, 1]과 큰 []으로 분할합니다. |
| 2 | [2, 4, 3, 1] + [5] | 왼쪽 리스트 [2, 4, 3, 1]에서 피벗 2를 선택합니다. [1] (작은 값), [4, 3] (큰 값)으로 분할합니다. |
| 3 | [1] + [2] + [4, 3] + [5] | [4, 3] 부분에서 피벗 4를 선택합니다. [3] (작은 값), [] (큰 값)으로 분할합니다. |
| 4 | [1] + [2] + [3, 4] + [5] | 각 부분리스트가 정렬되어 병합합니다. |
| 5 | [1, 2, 3, 4, 5] | 모든 부분이 병합되어 최종적으로 정렬 완료. |
- C++ 구현 코드
힙 정렬
시간복잡도 : 최선 O(NlogN), 최악 O(NlogN)
- 방식
1
2
3
4
5
| 1) 힙(Heap) 자료구조를 이용하여 정렬하는 알고리즘입니다.
2) 먼저 주어진 리스트를 완전이진트리 형태의 최대 힙(Max Heap)으로 만듭니다.
3) 힙의 루트(가장 큰 값)를 꺼내어 정렬 리스트의 끝으로 보냅니다.
4) 힙의 크기를 하나 줄이고, 다시 최대 힙의 형태를 유지하도록 재정렬합니다.
5) 모든 원소가 제거될 때까지 3~4 과정을 반복하면 오름차순 정렬이 완성됩니다.
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [5, 2, 4, 3, 1] | 리스트를 힙 구조로 변환 (Max Heapify). 루트는 최대값 5. |
| 2 | [1, 2, 4, 3, 5] | 루트(5)를 마지막 원소와 교환 후, 힙 크기를 1 줄이고 다시 힙 정렬 수행. |
| 3 | [4, 3, 1, 2, 5] | 남은 [1, 2, 4, 3]을 다시 힙으로 만들어 최대값 4를 루트로. |
| 4 | [2, 1, 3, 4, 5] | 루트(4)와 마지막 교환, 힙 크기 1 줄이고 다시 정렬. |
| 5 | [1, 2, 3, 4, 5] | 모든 힙 정렬 완료 — 오름차순 정렬 완성. |
- C++ 구현 코드
기수 정렬
- 방식
1
2
3
4
| 1) 정렬할 수를 자릿수(Digit) 기준으로 분리하여 정렬하는 알고리즘입니다.
2) 각 자릿수(일의 자리 → 십의 자리 → 백의 자리 순)마다 **안정 정렬(Stable Sort)**을 적용합니다.
3) 한 자릿수씩 정렬이 끝날 때마다 전체 리스트가 점점 정렬된 형태로 변합니다.
4) 모든 자릿수에 대해 정렬을 마치면 완전히 오름차순으로 정렬됩니다.
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [170, 45, 75, 90, 802, 24, 2, 66] | 정렬할 초기 리스트 |
| 2 | (1의 자리 기준) → [170, 90, 802, 2, 24, 45, 75, 66] | 1의 자리 숫자를 기준으로 안정 정렬 수행 |
| 3 | (10의 자리 기준) → [802, 2, 24, 45, 66, 170, 75, 90] | 10의 자리 숫자를 기준으로 안정 정렬 수행 |
| 4 | (100의 자리 기준) → [2, 24, 45, 66, 75, 90, 170, 802] | 100의 자리 숫자를 기준으로 안정 정렬 수행 |
| 5 | 모든 자릿수 정렬 완료 → [2, 24, 45, 66, 75, 90, 170, 802] | 최종적으로 완전히 정렬된 리스트 완성 |
- C++ 구현 코드
계수 정렬
- 방식
1
2
3
4
| 1) 주어진 리스트의 각 원소 값이 몇 번 등장했는지를 세어(Counting) 저장합니다.
2) 이 빈도 정보를 누적합 형태로 변환하여 각 원소의 정렬된 위치를 계산합니다.
3) 원소를 누적된 인덱스 위치에 맞게 배치하여 정렬된 리스트를 만듭니다.
4) 비교 연산을 하지 않고, "값의 크기 범위"를 이용해 정렬하는 알고리즘입니다.
|
- 동작 과정 예시
| 단계 | 정렬 과정 | 설명 |
|---|
| 1 | [5, 2, 4, 3, 1, 2] | 정렬할 리스트 |
| 2 | 카운트 배열 생성: [0, 1, 2, 1, 1, 1] | 각 숫자가 등장한 횟수를 인덱스에 기록 (예: 1은 1번, 2는 2번 등) |
| 3 | 누적합 계산: [0, 1, 3, 4, 5, 6] | 각 인덱스가 정렬된 배열에서 차지할 마지막 위치를 의미 |
| 4 | 뒤에서부터 정렬된 배열에 채우기 | 원소를 하나씩 꺼내 누적합 인덱스에 맞게 배치 |
| 5 | [1, 2, 2, 3, 4, 5] | 최종적으로 정렬된 리스트 완성 |
- C++ 구현 코드