정렬
일반적으로 시간복잡도 O(nlogn)인 정렬을 사용
특수한 상황인 경우 상황에 따라 O(n)에 근접한 알고리즘이 사용될 수 있습니다.
O(n^2) 인 알고리즘
Bubble sort
앞에서부터 인접한 2개씩 크기를 비교하여 왼쪽에 있는 데이터가 오른쪽보다 크면 Swap.
1. 처음에는 n과 n-1을 비교하는 것까지 하고 (그러면 가장 큰 수가 맨 뒤로 간다.)
2. 그 다음에 n-1과 n-2를 비교하는 것 까지 하고 (그러면 2번째로 큰 수가 뒤에서 2번째로 간다.)
3. n-2와 n-3을 비교… 1과 2를 비교하는 것까지 반복한다.
이렇게 하면 비교연산을 n(n-1)/2 번 수행하면 된다.
(최악의 경우 이렇고, 이미 정렬이 되어 있다면 n번 수행하면 된다)
Selection sort
1. 1번째 ~ 모든 숫자를 살펴본 뒤 가장 작은 숫자를 맨 앞에 삽입
2. 2번째 ~ 모든 숫자를 살펴본 뒤 가장 작은 숫자를 맨 앞에 삽입….
3. n까지 반복한다.
항상 n(n-1)/2번 수행한다.
Insertion sort
1. 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
2번째 자료는 1번째와,
3번재 자료는 1~2번 째와,…. n번째 자료는 1~n-1번 자료와 비교한다.
이 Insertion sort의 이름은 “삽입” 정렬입니다다.
이 정렬은 맨 처음에 정렬하는 것은 O(n^2)이 걸리지만 새로운 자료가 들어왔을 때, O(n)에 정렬이 가능한 장점이 있습니다.
(대신 Array 등을 사용하면 마찬가지로 삽입할 때 오버헤드가 생기므로 자료구조를 잘 선택해야 합니다
또, 더 짧은 시간에 이용할 수 있는 Heap Sort가 있기 때문에 더 빠르게 최적화를 하기 위해선 Heap Sort를 씁시다.)
또한 정렬할 개수가 적을 때, O(logn)보다도 시간이 짧고 코드가 쉽다는 장점이 있습니다.
void insertionSort(vector){
for (int i = 0; i < n; ++i){
for (int j = i + 1; j > 0 && list[j] < list[j - 1]; --j){
swap(vector[j], vector[j - 1]);
}
}
}
O(nlogn) 인 알고리즘
Merge sort
분할-정복 알고리즘의 대표적인 알고리즘이죠.
성능은 일반적으로 Quick Sort보다 떨어지고, 메모리가 N만큼 더 필요하다는 단점이 있지만, Stable Sort라는 장점이 있습니다.
(Stable sort란 같은 값에 대하여 앞에 있던 값이 정렬 후에 그대로 앞에 있는 것)
또한 개념과 코드가 되게 직관적이어서 코드 구현과 응용이 쉽고 버그가 생길 가능성이 적다는 장점이 있습니다.
퀵소트는 코드 자체는 간단한데 버그가 생기는 경우가 많아서, 숙달될 때 까지 여러 번 연습해보는 것이 필요합니다.
Heap sort
트리의 한 종류인 힙에 대해 공부했던 것 기억 나시나요? https://jw92.tistory.com/19
Tree (트리)
2번째 주제 트리입니다. Tree 그래프의 일종으로 Node가 계층 관계로 1:n 관계를 가지는 자료구조 기본 Tree에서는 용어 정리 정도만. 노드: 각 원소 엣지: Node를 연결하는 선, 부모 노드와 자식 노드
jw92.tistory.com
우선순위가 제일 높은 것을 뽑아내는 데, 탐색에 O(logn)이 걸렸고, 추가에 O(logn)이 걸렸죠.
정렬과 비슷해 보이지않나요? 정렬: 우선순위 순으로 데이터를 저장하는 것.
우선순위가 제일 높은 것을 뽑는데 O(logn)이 걸리므로
우선순위 순으로 n개를 뽑는데 O(nlogn) 이 걸리겟죠.
Heap에 대해서는 앞의 자료를 참고해주세요.
Quick sort
Quick. 일반적인 상황에서 최고의 속도를 내는 정렬 알고리즘입니다.
일반적인 언어에서 제공하는 함수들이 이 Quick sort를 변형한 알고리즘을 사용합니다.
1. 적절한 원소 하나를 pivot으로 삼는다.
2. Pivot을 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 보낸다.
3. 나누어진 각각에서 pivot을 새로 잡고 2.를 수행한다.
4. 나누어진 크기가 0 혹은 1이 될 때 까지 반복한다.
1~2의 과정을 Partition step이라고 합니다. Quick sort에서는 이 Partition step을 어떻게 정의하냐에 따라 성능이 많이 달라집니다. 일반적으로 쉬운 방법으로 중위값(가운데 위치한 데이터)를 사용합니다.
왜냐하면 최악의 경우에 이미 정렬된 것을 정렬할 때, 아래처럼 가장 바깥 쪽이 연속으로 pivot으로 선정되면 O(n^2)이 걸릴 수 있기 때문입니다.
또 이 Quick 정렬은 Stable 정렬이 아니기 때문에 문제에 따라 사용 못 할 수 있습니다.
기타 정렬 (O(nlogn)도 아니고 O(n^2)도 아닌 것)
Radix sort(기수 정렬)
O(kn) // k는 데이터의 자릿수
위의 정렬들은 데이터끼리 직접 비교하기 때문에 O(nlogn)이나 O(n^2)이 나올 수 밖에 없습니다.
그에 반해 기수 정렬은 자릿수에 대하여 데이터 직접 비교없이 수행하여 O(nk)가 나오게 됩니다.
K가 상수인 경우 O(n)이 되어 Quick sort보다 빠른 정렬이 될 수 있습니다.
데이터가 x진법이라고 할 때,
1. 0~x-1까지의 리스트를 만들어 놓는다.
2. 각 데이터를 순서대로 현재 자릿수의 숫자가 가리키는 리스트에 넣고 리스트를 순서대로 이어 붙인다.
3. 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복한다.
예를 들어 10진법인 경우에
156, 10, 23, 753, 3에 대하여 정렬을 해보면 아래와 같습니다.
1. 일의 자리
| 0 | 10 |
| 3 | 23,753,3 |
| 6 | 156 |
1의 결과: 10, 23, 753, 3, 156
2. 십의 자리
| 0 | 3 |
| 1 | 10 |
| 2 | 23 |
| 5 | 753, 156 |
2의 결과: 3, 10, 23, 753, 156
3. 백의 자리
| 0 | 3, 10, 23 |
| 1 | 156 |
| 7 | 753 |
3의 결과: 3, 10, 23, 156, 753
O(nk)에 정렬이 완료되었습니다.
하지만 이 방법이 항상 빠른 것은 아니고,
O(nlogn)과 O(nk)를 비교해보면 logn이 k로 바뀐 것인데,
자릿수라는 것을 생각해보면 k 자체가 log나 마찬가지이므로. (x진법 최대값이 m이면 k=logxm
)
중복된 값이 많은 경우에 logn이 k보다 크므로 중복된 값이 많은 데이터에서 사용하면 이점을 볼 수 있습니다.
Counting Sort 계수 정렬
O(n+k) 에 할 수 있는 정렬입니다. // k는 최댓값
1. 자료를 탐색해서 k(최댓값)을 구합니다.
2. k+1만큼의 크기로 모든 자료가 0으로 초기화된 배열(counts)를 생성합니다.
3. 모든 원소에 대하여 counts에 해당하는 곳에 +1을 해줍니다.
-> counts은 각 n에 해당하는 값이 몇 개 있는 지를 의미합니다.
4. counts[i] += counts[i-1] 을 1~k까지 수행합니다.
-> 배열은 각 n 이하의 값이 몇 개 있는 지를 의미합니다.
5. 길이가 input과 같은 배열(ans)를 하나 더 생성합니다.
6. Counts의 input[0]에 대응하는 곳의 원소를 찾아서 t로 놓고, ans의 t-1에 대응하는 곳에 input[0]을 저장합니다. Counts의 input[0]에 대응하는 곳은 1을 빼줍니다.
7. 6을 모든 자료에 대하여 반복합니다.
예제
0. Input = [6, 3, 5, 7, 10, 2, 5]
1. k = 10
2. 크기 11인 배열 생성: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3. 모든 input에 대하여 n++: [0, 0, 1, 1, 0, 2, 1, 1, 0, 0, 1]
4. counts[i] += counts[i-1] 수행: [0, 0, 1, 2, 2, 4, 5, 6, 6, 6, 7]
5. 길이가 7인 배열 ans 생성: [N, N, N, N, N, N, N] // N은 null
6. [6, 3, 5, 7, 10, 2, 5]
A. input[0] = 6
B. counts[6] = 5
C. ans 5-1=4위치에 6를 삽입 = [N, N, N, N, 6, N, N]
D. counts[6]-- = [0, 0, 1, 2, 2, 4, 4, 6, 6, 7]
7. 모든 원소에 대하여 6. 반복
A. 3: [N, 3, N, N, 6, N, N] [0, 0, 1, 1, 2, 4, 4, 6, 6, 6, 7]
B. 5: [N, 3, N, 5, 6, N, N] [0, 0, 1, 1, 2, 3, 4, 6, 6, 6, 7]
C. 7: [N, 3, N, 5, 6, 7, N] [0, 0, 1, 1, 2, 3, 4, 5, 6, 6, 7]
D. 10: [N, 3, N, 5, 6, 7, 10] [0, 0, 1, 1, 2, 3, 4, 5, 6, 6, 6]
E. 2: [2, 3, N, 5, 6, 7, 10] [0, 0, 0, 1, 2, 3, 4, 5, 6, 6, 6]
F. 5: [2, 3, 5, 5, 6, 7, 10] [0, 0, 0, 1, 2, 2, 4, 5, 6, 6, 6]
8. 결과: [2, 3, 5, 5, 6, 7, 10]
즉, 최댓값이 작고 n이 많은 정렬에서 거의 선형 시간의 효과를 볼 수 있는 정렬 알고리즘입니다.
하지만 메모리가 크고 k의 범위에 제약이 있다는 단점이 있습니다. (k가 21억이라면..)
