정렬 알고리즘은 N개의 숫자를 기준에 맞게 오름차순 or 내림차순으로 정렬하는 알고리즘입니다.
종류가 다양하게 있지만 이 글에서는 선택, 버블, 삽입, 병합, 퀵 정렬만 정리하려고 합니다.
그리고 오름차순 정렬만 정리하였습니다.
1. 선택 정렬 (Selection Sort)
선택 정렬은 현재 위치에 들어갈 수를 찾으면서 정렬하는 알고리즘입니다.
1. 선택한 인덱스부터 N까지 가장 작은 값을 찾습니다.
2. 가장 작은 값과 선택한 값을 서로 바꿉니다.
3. 이 과정을 N - 1번 반복합니다.
이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void selectionSort() {
for (int i = 0; i < N - 1; i++) {
int minidx = i;
for (int j = i + 1; j < N; j++) {
if (list[minidx] > list[j]) {
minidx = j;
}
}
int tmp = list[minidx];
list[minidx] = list[i];
list[i] = tmp;
}
}
|
cs |
2. 버블 정렬 (Bubble Sort)
버블 정렬은 연속된 2개의 수를 비교하여 정렬하는 알고리즘입니다.
정렬 과정에서 가장 큰수를 맨뒤로 보내는 방식입니다.
1. 두 번째 인덱스부터 바로 이전의 인덱스와 값을 비교합니다. (list[idx], list[idx - 1])
2. list[idx - 1] > list[idx]이면 두 수를 바꿉니다.
3. 아니면 다음 인덱스를 확인합니다.
4. 이 과정을 N번 반복합니다.
이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.
선택 정렬은 앞에서부터 작은 수가 결정되는 방식이지만
버블 정렬은 뒤에서부터 큰 수가 결정되는 방식입니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
void bubbleSort() {
for (int i = 0; i < N; i++) {
for (int j = 1; j < N - i; j++) {
if (list[j - 1] > list[j]) {
int tmp = list[j];
list[j] = list[j - 1];
list[j - 1] = tmp;
}
}
}
}
|
cs |
3. 삽입 정렬 (Insertion Sort)
삽입 정렬은 현재 위치에서 이전의 값들을 비교하여 자신이 들어갈 위치를 찾아들어가는 정렬 알고리즘입니다.
1. 현재 인덱스에서 왼쪽으로 이동하면서 값을 비교합니다.
2. tmp보다 작은 수가 나올 때까지 수들을 한칸 옮겨줍니다.
3. tmp보다 작은 수가 나오면 그 다음 자리에 tmp를 넣어줍니다.
4. 이 과정을 N - 1번 반복합니다.
이 알고리즘의 시간복잡도는 최선 : O(N), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void insertionSort() {
for (int i = 1; i < N; i++) {
int tmp = list[i];
int j = i - 1;
for (; j >= 0; j--) {
if (list[j] > tmp) {
list[j + 1] = list[j];
}
else
break;
}
list[j + 1] = tmp;
}
}
|
cs |
4. 병합 정렬 (Merge Sort)
병합 정렬은 배열을 반씩 분할해가면서 정렬하는 알고리즘입니다.
시간적으로는 효율적이나 메모리를 배열의 2배 사용해야하는 단점이 있습니다.
1. 배열을 가장 작은크기까지 분할합니다.
2. 분할된 배열끼리 정렬합니다.
3. 분할된 배열을 다시 합쳐서 합친 배열을 다시 정렬합니다.
4. 이 과정을 반복합니다.
|
과정 예시)
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
[배열을 분할합니다.]
N = 8 {4, 5, 8, 2, 6, 1, 7, 3}
N = 4 {4, 5, 8, 2} {6, 1, 7, 3}
N = 2 {4, 5} {8, 2} {6, 1} {7, 3}
N = 1 {4} {5} {8} {2} {6} {1} {7} {3}
[배열을 병합하는 과정에서 정렬합니다.]
N = 1 {4} {5} {8} {2} {6} {1} {7} {3}
N = 2 {4, 5} {2, 8} {1, 6} {3, 7}
N = 4 {2, 4, 5, 8} {1, 3, 6, 7}
N = 8 {1, 2, 3, 4, 5, 6, 7, 8}
|
|
정렬로직 설명)
분할된 두 개의 배열에서 가장 작은 값들끼리 비교하여 작은 값을 새로운 배열에 넣습니다.
arr1: {2, 4, 5, 8} arr2: {1, 3, 6, 7} sorted: {}
arr1 or arr2의 숫자를 모두 고를때까지 반복합니다.
arr1: {2, 4, 5, 8} arr2: {1, 3, 6, 7} sorted: {}
arr1[i] = 2
arr2[j] = 1
arr1: {2, 4, 5, 8} arr2: {3, 6, 7} sorted: {1}
arr1[i] = 2
arr2[j] = 3
arr1: {4, 5, 8} arr2: {3, 6, 7} sorted: {1, 2}
arr1[i] = 4
arr2[j] = 3
arr1: {4, 5, 8} arr2: {6, 7} sorted: {1, 2, 3}
arr1[i] = 4
arr2[j] = 6
arr1: {5, 8} arr2: {6, 7} sorted: {1, 2, 3, 4}
arr1[i] = 5
arr2[j] = 6
arr1: {8} arr2: {6, 7} sorted: {1, 2, 3, 4, 5}
arr1[i] = 8
arr2[j] = 6
arr1: {8} arr2: {7} sorted: {1, 2, 3, 4, 5, 6}
arr1[i] = 8
arr2[j] = 7
arr1: {8} arr2: {} sorted: {1, 2, 3, 4, 5, 6, 7}
여기서 arr2의 숫자를 모두 골랐으니 arr1의 남은 숫자를 sorted의 뒤에 붙여주면 됩니다.
arr1: {} arr2: {} sorted: {1, 2, 3, 4, 5, 6, 7, 8}
|
이 알고리즘의 시간복잡도는 최선, 최악 : O(NlogN)이고, 공간복잡도는 O(N * 2)입니다.
|
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
32
33
34
|
void merge(int l, int m, int r) {
int i = l;
int j = m + 1;
int k = l;
while (i <= m && j <= r) {
if (list[i] < list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if (i > m) {
for (int t = j; t <= r; t++, k++) {
sorted[k] = list[t];
}
} else {
for (int t = i; t <= m; t++, k++) {
sorted[k] = list[t];
}
}
for (int t = l; t <= r; t++)
list[t] = sorted[t];
}
void mergeSort(int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(l, m);
mergeSort(m + 1, r);
merge(l, m, r);
}
}
|
cs |
5. 퀵 정렬 (Quick Sort)
배열에서 피봇을 선택해 피봇보다 작은 원소를 왼쪽에, 큰 원소를 오른쪽에 옮겨지고
피봇을 기준으로 피봇을 제외한 왼쪽, 오른쪽 원소들을 다시 정렬해나가는 알고리즘입니다.
|
과정 예시)
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
피봇은 배열의 첫번째 요소로 지정합니다.
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot = 0
i = 1
j = 0
list[] = {4, 2, 8, 5, 6, 1, 7, 3}
pivot = 0
i = 3
j = 1
list[] = {4, 2, 1, 5, 6, 8, 7, 3}
pivot = 0
i = 5
j = 2
list[] = {4, 2, 1, 3, 6, 8, 7, 5}
pivot = 0
i = 7
j = 3
list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}
이후에 피봇 기준 왼쪽 오른쪽 배열{3, 2, 1}과 {6, 8, 7, 5}도 똑같은 로직을 반복합니다.
|
|
정렬로직 설명)
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot : 0
i = 1
j = 0
list[i]와 list[pivot]을 비교합니다.
list[i] < list[pivot]이면 j를 1증가하고, list[i]와 list[j]를 바꿉니다.
이를 i = 1부터 끝까지 반복합니다.
그럼 최종적으로
list[] = {4, 2, 1, 3, 6, 8, 7, 5} 라는 배열이 만들어집니다.
여기서 pivot은 여전히 0이고
j는 3입니다.
그럼 list[pivot]과 list[j]를 바꿉니다.
=> list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}
이제 4의 위치는 정해졌으며 이를 기준으로 왼쪽 배열과 오른쪽 배열도 같은 로직을 반복합니다.
|
이 알고리즘의 시간복잡도는 최선 : O(NlogN), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int partition(int pivot, int l, int r) {
int j = pivot;
for (int i = pivot + 1; i <= r; i++) {
if (list[pivot] > list[i]) {
swap(list[++j], list[i]);
}
}
swap(list[pivot], list[j]);
return j;
}
void quickSort(int l, int r) {
if (l < r) {
int pivot = partition(l, l, r);
quickSort(l, pivot - 1);
quickSort(pivot + 1, r);
}
}
|
cs |
'algorithm > Theory' 카테고리의 다른 글
| 좌표 압축 (Coordinate Compression) (2) | 2022.08.24 |
|---|