알고리즘 [정렬]
생성 이유
부족한 나의 알고리즘 실력을 필기하기 위해 만들어진 카테고리입니다. 참고한 자료에 저의 생각을 덧붙인형태로 틀린 부분도 있을 것 이다.
선택정렬
선택정렬 - 배열에서 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘으로 배열을 모두 비교하여 제일 작은 값을 저장해 놓고 정렬할 기준위치(맨앞)과 교체한다. 작은 값을 맨앞에 정렬했으니 그 다음 배열의 위치를 기준으로 잡고 비교를 하여 제일 작은 값을 저장후 기준위치랑 교체한다. 이작업을 반복하여 정렬한다. (기준위치를 배열의 맨앞과 맨뒤로 오름차순 내림차순으로 정렬할 수 있다.)
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
int main(void)
{
int i, j, min, index, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i++)
{
min = 9999;
for(j=i; j < 10; j++)
{
if(min > array[j])
{
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for(i=0; i < 10; i++)
{
printf("%d",array[i]);
}
return 0;
}
시간복잡도 10 + 9 + 8 + … + 1 => 10 * (10 +1) / 2 = 55 => N * (N + 1 ) / 2 (일반적으로 컴퓨터에서는 N이 크다는 과정에 + 나 / 별의미가 없기 때문에 무시를 한다) => N * N 빅오표기법 => 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
int main(void)
{
int i, j, temp;
int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
for (i = 0; i < 10; i++)
{
for (j = i; j < 9 - i; j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
for (i = 0; i < 10; i++)
{
printf("%d", array[i]);
}
return 0;
}
시간복잡도 => 10 + 9 + 8 + 7 + … + 1 => N * (N + 1) / 2 => O(N * N)
버블정렬은 선택정렬과 시간복잡도는 같지만 실행하면 버블정렬이 더 느리다 이유는 바로 옆에있는 인덱스와 비교하여 교환 작업을 수행하기 떄문이다. 선택정렬은 마지막에만 제일 작은값을 교환하는 작업을 하여 한 번과 여러번 차이가 난다.
삽입 정렬
삽입 정렬 - 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 ‘필요할 때만’ 위치를 바꾸게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main(void)
{
int i, j, temp;
int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
for (i = 0; i < 9; i++)
{
j = i;
while (j > 0 && array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
j--;
}
}
for (i = 0; i < 10; i++)
{
printf("%d ", array[i]);
}
return 0;
}
시간복잡도 => O(N * N)
버블,선택과 시간복잡도는 같지만 데이터가 이미 거의 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다는 특징을 가지고 있습니다.
퀵 정렬
선택, 버블, 삽입 정렬 알고리즘은 모두 시간 복잡도가 O(N^2)을 가진다. 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기 매우 어려운 알고리즘이다. 그렇기 때문에 더욱 빠른 정렬 알고리즘 중 대표적으로 퀵 정렬이다. 퀵 정렬은 대표적인 분할 정복 알고리즘으로 평균 속도가 O(N*logN)이다.
퀵 정렬 - 특정한 값을 기준으로 큰 숫자와 작은숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 일반적으로 퀵 정렬에서는 기준 값이 있다. 이를 피벗 이라고도 하는데 보통 첫 번째 원소를 피벗 값으로 설정한다. 작은 값의 인덱스가 큰값의 인덱스보다 더 작으면 엇갈렸다고한다 이때 그 작은값과 피벗값을 교체한다. (이상황이 오면 피벗값은 정렬이 된 상태인것 왼쪽으로는 피벗값보다 작고 오른쪽은 큰값으로 분할된다) 분할된 왼쪽과 오른쪽에서 제일 앞에값이 피벗이 되어 다시 수행한다.
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
int number = 10;
int data[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
void show()
{
int i;
for (i = 0; i < number; i++)
{
printf("%d ", data[i]);
}
}
void quickSort(int* data, int start, int end)
{
if (start >= end)
{ // 원소가 1개인 경우 그대로 두기
return;
}
int key = start; // 키는 첫 번째 원소
int i = start + 1, j = end, temp;
while (i <= j) // 엇갈릴 때까지 반복
{
while (i <= end && data[i] <= data[key]) // 키 값보다 큰 값을 만날 때까지
{
i++;
}
while (j > start && data[j] >= data[key]) // 키 값보다 작은 값을 만날 때까지
{
j--;
}
if (i > j) // 현재 엇갈린 상태면 키 값과 교체
{
temp = data[j];
data[j] = data[key];
data[key] = temp;
}
else // 엇갈리지 않았다면 i와 j를 교체
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
quickSort(data, 0, number - 1);
show();
return 0;
}
퀵 정렬의 평균 시간 복잡도는 O(N*logN) 하지만 최악의 경우 O(N^2)이 나오기도한다. 최악의 경우는 이미 정렬이되어 있거나 거의 정렬이 되어있는 경우에 느리다. 웬만한 경우는 퀵 정렬이 빠르고 거의 정렬되어 있는 데이터는 삽입정렬이 더 빠르다.
O(NlogN)을 요구하는 문제에서는 위에 퀵정렬 소스코드를 넣으면 틀린 답이다 최악의경우 O(N^2)이 나올 수 있기 떄문이다. STL 라이브러리에서 제공하는 sort()함수는 퀵 정렬을 기반으로 하지만 최악의 경우에도 O(NlogN)을 보장합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <algorithm>
int number, data[1000000];
int main(void)
{
scanf("%d", &number);
for(int i = 0; i < number; i++)
{
scanf("%d", &data[i]);
}
std::sort(data, data + number);
for(int i = 0; i < number; i++)
{
printf("%d\n", data[i]);
}
return 0;
}
병합 정렬
병합 정렬도 대표적인 분할 정복 방법을 채택한 알고리즘으로 O(NlogN)의 시간 복잡도를 가집니다. 병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(NLongN)을 보장하는 특성을 가지고 있습니다.
병합정렬 - 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택합니다. 즉 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬하는 것입니다. 병합 정렬은 퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징이 있습니다. 바로 이 특징이 단계의 크기가 logN이 되도록 만들어준답니다.
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
int number = 8;
int size;
int sorted[8]; // 정렬 배열은 반드시 전역 변수로 선언
int count = 0;
void merge(int a[], int m, int middle, int n)
{
int i = m;
int j = middle + 1;
int k = m;
// 작은 순서대로 배열에 삽입
while(i <= middle && j <= n)
{
if(a[i] <= a[j]) {
sorted[k] = a[i];
i++;
} else {
sorted[k] = a[j];
j++;
}
k++;
}
// 남은 데이터도 삽입
if(i > middle)
{
for(int t = j; t <= n; t++)
{
sorted[k] = a[t];
k++;
}
} else {
for(int t = i; t <= middle; t++)
{
sorted[k] = a[t];
k++;
}
}
// 정렬된 배열을 삽입
for(int t = m; t <= n; t++)
{
a[t] = sorted[t];
}
}
void mergeSort(int a[], int m, int n)
{
// 이외의 경우는 크기가 1개인 경우
if(m < n) {
int middle = (m + n) / 2;
mergeSort(a, m, middle);
mergeSort(a, middle + 1, n);
merge(a, m, middle, n);
}
}
int main(void)
{
int array[number] = {7, 6, 5, 8, 3, 5, 9, 1};
mergeSort(array, 0, number - 1);
for(int i = 0; i < number; i++)
{
printf("%d ", array[i]);
}
}
병합 정렬을 구성할 때 사용되는 배열을 전역 변수로 선언해야하고 기존의 데이터를 담을 추가적인 배열공간이 필요하다는 점에서 메모리 활용이 비효율적인 문제가 있습니다. 병합 정렬은 일반적인 경우 퀵 정렬보다 느리지만 어떠한 상황에서도 정확히 O(N*logN)을 보장할 수 있다는 점이 장점인 것 같습니다.
sort 함수
sort()의 세 번째 인자 값으로 넣게 되면, 해당 함수의 반환 값에 맞게 정렬이 동작합니다. compare 함수를 이용하여 내림차순 정렬을 해보았다. return 값에 a > b = 내림차순 a < b = 오름차순
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(int a, int b)
{
return a > b;
}
int main(void)
{
int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
sort(a, a + 10, compare);
for(int i = 0; i < 10; i++)
{
cout << a[i] << ' ';
}
}
객체에 특정한 변수를 기준으로 정렬하는 방법으로 클래스내에 operator를 정의하여 하는 방법과 람다함수를 이용하는 방법이있다.
- operator ```cpp #include
#include #include
struct Person { std::string name; int age;
1
2
3
4
5
6
7
8
9
10
// operator< 오버로딩: 나이를 기준으로 오름차순 정렬
bool operator<(const Person& other) const
{
return age < other.age;
}
void print() const
{
std::cout << name << " (" << age << ")\n";
} };
int main() { Person people[] = { {“Alice”, 30}, {“Bob”, 25}, {“Charlie”, 35} };
1
2
3
4
5
6
7
8
9
10
11
12
// 배열의 크기 계산
int n = sizeof(people) / sizeof(people[0]);
// operator<를 사용하여 정렬
std::sort(people, people + n);
std::cout << "operator<를 이용한 배열 정렬:\n";
for (int i = 0; i < n; ++i) {
people[i].print();
}
return 0; }
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
- 장점
1. 간결성
- 정렬 기준이 클래스 내부에 포함되므로 별도로 정렬 기준을 지정하지 않아도 됩니다.
- 호출 시 std::sort에 단순히 반복자만 전달하면 됩니다.
2. 재사용성
- 클래스가 사용되는 다른 곳에서도 동일한 정렬 기준을 사용할 수 있습니다.
- 표준 라이브러리에서 제공하는 데이터 구조(예: std::set 또는 std::map)에서도 같은 기준으로 객체를 자동 정렬할 수 있습니다.
3. 캡슐화
- 객체의 데이터와 비교 기준이 밀접하게 연결되어 있으므로 유지보수가 쉬워집니다.
- 단점
1. 유연성 부족
- 정렬 기준이 고정되어 있으며, 필요에 따라 다른 정렬 기준을 적용하기 어렵습니다.
- 예를 들어, 나이로 정렬하다가 이름으로 정렬하려면 추가 작업이 필요합니다. (추가 오퍼레이터 오버로딩)
2. 코드 복잡도 증가
- 클래스에 너무 많은 기능(예: 다양한 정렬 기준)을 넣으면 클래스가 복잡해질 수 있습니다.
- 람다함수
```cpp
#include <iostream>
#include <algorithm>
#include <string>
struct Person
{
std::string name;
int age;
void print() const
{
std::cout << name << " (" << age << ")\n";
}
};
int main()
{
// 배열 생성
Person people[] =
{
{"Alice", 30},
{"Bob", 25},
{"Charlie", 35}
};
// 배열의 크기 계산
int n = sizeof(people) / sizeof(people[0]);
// 람다를 사용하여 나이를 기준으로 정렬
std::sort(people, people + n, [](const Person& a, const Person& b)
{
return a.age < b.age;
});
std::cout << "람다 함수를 이용한 배열 정렬:\n";
for (int i = 0; i < n; ++i)
{
people[i].print();
}
// 람다를 사용하여 이름을 기준으로 내림차순 정렬
std::sort(people, people + n, [](const Person& a, const Person& b)
{
return a.name > b.name;
});
std::cout << "\n이름을 기준으로 내림차순 정렬:\n";
for (int i = 0; i < n; ++i) {
people[i].print();
}
return 0;
}
- 장점
- 유연성
- 다양한 정렬 기준을 쉽게 정의할 수 있습니다.
- 코드 실행 시점에 다른 기준을 적용하거나, 특정 요구 사항에 맞는 기준을 즉석에서 정의할 수 있습니다.
- 명확성
정렬 기준이 호출부에 명확하게 드러납니다. 코드의 흐름을 읽는 입장에서 어떤 기준으로 정렬하는지 바로 이해할 수 있습니다.
- 단점
- 재사용성 부족
- 같은 기준으로 정렬할 때마다 반복적으로 람다를 작성해야 할 수 있습니다.
- 캡슐화 부족
- 정렬 기준이 클래스 외부에 위치하므로, 클래스의 내부 데이터에 대한 의존성을 증가시킬 수 있습니다.
힙 정렬
힙은 최솟값이나 최댓값을 찾기위해 완전 이진트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소힙이 존재하고 최대 힙은 ‘부모 노드’가 ‘자식 노드’보다 큰 힙이라고 할 수 있다. 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야합니다.
힙 정렬 알고리즘으로 특정한
하나의 노드에 대해 수행하는 것으로 해당 하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태라고 가정을 한다는 특징이 있다. 위의 그림이 해당 가정에 부합함으로 위 트리에서 ‘6’만 최대 힙 정렬을 수행해주면 전체 트리가 최대 힙 구조로 형성되는 상태입니다. 힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘입니다. 위치를 바꾼 이후에도 여전히 자식이 존재한 상태에서 최대 힙이 아닌 상태가 있다면 계속 더 큰 자식과 특정한 자신과 바꿔주는 행동을 반복하여 정렬합니다.
힙 생성 알고리즘의 시간 복잡도는 한 번 자식의 노드로 내려갈 떄마다 노드의 갯수가 2배씩 증가한다는 점에서 O(log N) 입니다.
이 때 데이터의 갯수가 N개 이므로 전체 트리를 힙 구조로 만드는 복잡도는 O(N * log N)입니다. ( 사실상 모든 데이터를 기준으로 힙 생성 알고리즘을 쓰지 않아도 되기 때문에 O(N)에 가까운 속도를 낼 수 있습니다. )
힙 생성 알고리즘을 완료한 힙에서 루트 노드와 마지막 원소랑 교체한 후 마지막 원소를 힙 크기에서 제외 시킨다.
그리고 다시 힙 생성 알고리즘으로 힙 구조로 만든다.
다시 루트 노드와 마지막 원소랑 교체한 후 힙 크기에서 제외 시킨다. 그럼 제외된 마지막 원소들은 정렬되어 있는 모습이다. 이 과정을 반복하여 정리한다.
힙 정렬의 시간 복잡도는 힙을 만드는 힙 생성 알고리즘은 O(logN) 이다 하지만 저 과정을 N개만큼 반복 해야하기 떄문에, 힙 정렬의 시간 복잡도는 `O(N*log N) 입니다.
예제 코드
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
int number = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};
int main(void)
{
// 전체 트리 구조를 최대 힙 구조로 바꿉니다.
for(int i = 1; i < number; i++)
{
int c = i;
do {
int root = (c - 1) / 2; // 특정한 원소의 부모를 가르킴
if(heap[root] < heap[c]) // 부모의 값보다 자식의 값이 더 큰 경우
{
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
} while (c != 0);
}
// 크기를 줄여가며 반복적으로 힙을 구성
for (int i = number - 1; i >= 0; i--)
{
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
int root = 0;
int c = 1;
do {
c = 2 * root + 1;
// 자식 중에 더 큰 값을 찾기
if(c < i - 1 && heap[c] < heap[c + 1])
{
c++;
}
// 루트보다 자식이 크다면 교환
if(c < i && heap[root] < heap[c])
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < i);
}
// 결과 출력
for(int i = 0; i < number; i++)
{
printf("%d ", heap[i]);
}
}
힙 정렬은 병합 정렬과 다르게 별도로 추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 몹시 효율적입니다. 또한 항상 O(N * log N)을 보장할 수 있다는 점에서 몹시 강력한 정렬 알고리즘입니다. 이론적으로는 퀵 정렬, 병합 정렬보다 더 우위에 있다고 할 수 있습니다. 하지만 단순히 속도만 가지고 비교하면 퀵 정렬이 평균적으로 더 빠르기 때문에 힙 정렬이 일반적으로 많이 사용되지는 않습니다.
계수 정렬
다음 5이하 자연수 데이터들을 오름차순으로 정렬해라 1 3 2 4 3 2 5 3 1 2 4 2 1 5 2 1 2 이런 식으로 정렬할 데이터가 많지만 데이터가 1부터 5사이세 속하는 특징이 있을 때 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이다. 속도는 O(N)이고 계수 정렬은 단순하게 크기를 기준으로 세는 알고리즘입니다. 배열의 크기를 범위 크기 만큼 지정해준 후 ex)int count[] 데이터 배열의 원소를 하나하나 접근해 그 값에 맞게 count[원소 값]을 ++ 시켜 데이터의 양을 확인하는 방법이다.
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
#include <stdio.h>
int main(void)
{
int temp;
int count[6];
int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
for(int i = 1; i <= 5; i++)
{
count[i] = 0;
}
for(int i = 0; i < 30; i++)
{
count[array[i]]++;
}
for(int i = 1; i <= 5; i++)
{
if(count[i] != 0)
{
for(int j = 0; j < count[i]; j++)
printf("%d ", i);
}
}
return 0;
}
예시 코드와 같이 매우 간결한 코드이다. 모든 데이터의 크기 범위를 메모리 상에 표현할 수만 있다면 O(N)이라는 압도적인 속도로 정렬을 수행할 수 있는 것입니다.
참고 블로그
참고 링크 정말 감사합니다!