[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 기본 정렬
- 병합 정렬(Merge Sort)
- 퀵 정렬(Quick Sort)
- Counting Sort
- Radix Sort
- STL Sort
- Q&A
- 마치며
1. 기본 정렬
1) 선택 정렬(O(N²))
아이디어 / 구현이 가장 기초적인 정렬
원소 중 최댓값을 제일 앞 / 뒤로 순차적으로 이동시키는 정렬
int arr[5] = {3, 2, 7, 116, 62};
int n = 5;
for(int i = n - 1; i > 0; i--){
int mxidx = 0;
for(int j = 1; j <= i; j++){
if(arr[mxidx] < arr[j]) mxidx = j;
}
swap(arr[mxidx], arr[i]);
}int arr[5] = {3, 2, 7, 116, 62};
int n = 5;
for(int i = n - 1; i > 0; i--){
swap(*max_element(arr, arr + i + 1), arr[i]);
}2) 버블 정렬(O(N²))
구현이 가장 편한 정렬
앞에서부터 인접한 두 원소를 보면서, 앞의 원소가 더 클 때 자리를 바꾸는 정렬
int arr[5] = {-2, 2, 4, 6, 13};
int n = 5;
for(int i = 0; i < n; i++){
for(int j = 0; j < n - 1 - i; j++){
if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
}
}3) 삽입 정렬(O(N²))
2. 병합 정렬(Merge Sort) (O(NlgN))
(N이 10만정도일 때, O(N²)은 10초 ~ 1분, O(NlgN)은 겁나 빠름. N이 커지면 커질수록 격차는 더 커짐)
- 병합 정렬(Merge Sort)
: 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬
int idx1 = 0, idx2 = 0;
for(int i = 0; i < n + m; i++){
if(idx1 >= n){c[i] = b[idx2++]; continue;}
if(idx2 >= m){c[i] = a[idx1++]; continue;}
if(a[idx1] > b[idx2]) c[i] = b[idx2++];
else c[i] = a[idx1++];
}병합 정렬의 단계는 3단계로 나눌 수 있음.
- 주어진 리스트를 2개로 나눈다. O(N)
- 나눈 리스트 2개를 정렬한다.
- 정렬된 2개의 리스트를 합친다. O(Nk) = O(NlgN)
1) Stable Sort
만약 다음을 정렬한다고 해보자
20, 10(빨), 10(파), 10(초)
1. 10(빨) 10(파) 10(초) 20
2. 10(파) 10(빨) 10(초) 20
3. 10(초) 10(빨) 10(파) 20
위의 예시에서, 우선 순위가 같은 원소가 여러 개가 있음.
이 때, 우선 순위가 같은 원소들은 원래의 순서를 따라가게 하는 성질이 Stable Sort.
즉, 10(빨) 10(파) 10(초) 20이면, Stable Sort 성질을 가짐. 나머지 정렬은 Unstable Sort.
따라서, Merge Sort에서 Stable Sort를 만족시키려면,
앞의 리스트와 뒤의 리스트의 우선 순위가 같을 때, 앞의 리스트의 원소를 먼저 보내줘야 함.
3) 퀵 정렬(Quick Sort) (O(NlgN) ~ O(N²))
이름에서 알 수 있듯이, 거의 대부분의 정렬 알고리즘보다 빨라서 각종 라이브러리에서는 퀵 정렬을 바탕으로 만들어짐
하지만, 코테에서 STL을 못 쓴다면, 퀵 정렬이 아닌 반드시 Merge Sort를 사용해야 함.
(만약, 힙을 알고 있다면 Heap Sort, 아니면 다른 O(NlgN) 정렬 사용)
- 퀵 정렬(Quick Sort)
: pivot을 기준으로 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오게끔 재귀적으로 정렬
int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int tmp[8];
int tidx = 0;
int pivot = arr[0];
for(int i = 1; i < 8; i++)
if(arr[i] <= pivot) tmp[tidx++] = arr[i];
tmp[tidx++] = pivot;
for(int i = 1; i < 8; i++)
if(arr[i] > pivot) tmp[tidx++] = arr[i];
for(int i = 0; i < 8; i++) arr[i] = tmp[i];단, 위의 방식대로 코드를 작성하면 tmp라는 추가적인 공간이 필요함.
퀵 소트는 추가적인 공간을 사용하지 않고, pivot을 제자리에 보낼 방법을 고안해야함.
(이렇게 추가적인 공간을 사용하지 않는 정렬을 'In-Place Sort'라고 함)
int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int pivot = arr[0];
int l = 1, r = 7;
while(1){
while(l <= r && arr[l] <= pivot) l++;
while(l <= r && arr[r] > pivot) r--;
if(l > r) break;
swap(arr[l], arr[r]);
}
swap(arr[0], arr[r]);4. Counting Sort
- Counting Sort
: 수열에서 등장한, 원소의 개수를 세어, 원소의 개수만큼 나열한 정렬
1 5 4 2 3 1 4 3
1 : 2번
2 : 1번
3 : 2번
4 : 2번
5 : 1번
-> 1 1 2 3 3 4 4 5
정말 쉬운 정렬이지만, 명확한 단점이 있음.
만약, 원소가 999,999,999라면 크기가 10억인 배열이 필요함.
이론적으로는 수의 범위가 0 ~ 1억까지라도 사용가능하지만, 실제적으로는 1000만 이하일 때에는 COunting Sort를 사용함.
5. Radix Sort
- Radix Sort
수열에서 등장한, 원소의 자리수를 세어, 원소의 자리수를 기준으로 정렬
012 421 046 674 103 502 007 100 021 545
각 수의 1의 자리를 기준으로 0 ~ 9의 리스트에 구분하여 넣습니다.
0 : 100
1 : 421 021
2 : 012 502
3 : 103
4 : 674
5 : 545
6 : 046
7 : 007
8 :
9 :
-> 100 421 021 012 502 103 674 545 046 007
이후에는 0번 리스트부터 수를 보면서, 수열을 재배치함.
0 : 100
1 : 421 021
2 : 502 012
3 : 103
4 : 674
5 : 545
6 : 046
7 : 007
8 :
9 :
-> 100 421 021 502 012 103 674 545 046 007
이후에는, 10의 자리를 기준으로 넣고 재배치.
0 : 100 502 103 007
1 : 012
2 : 421 021
3 :
4 : 545 046
5 :
6 :
7 : 674
8 :
9 :
-> 100 502 103 007 012 421 021 545 046 674
마지막으로 100의 자리도 마찬가지.
0 : 007 012 021 046
1 : 100 103
2 :
3 :
4 : 421
5 : 502 545
6 : 674
7 :
8 :
9 :
-> 007 012 021 046 100 103 421 502 545 674
1) Comparison Vs Non-Comparision
(1) Comparision Sort
Merge, Quick, Bubble Sort같이 원소들끼리 크기를 비교하는 정렬
(2) Non-Comparision Sort
Counting, Radix Sort같이 원소들끼리 크기를 비교하지 않는 정렬
6. STL sort
STL sort는 기본적으로 퀵 소트를 기반으로 하지만, 리스트가 불균등하게 나눠져 재귀의 깊이가 너무 깊어지면 O(NlgN)이 보장되는 정렬 알고리즘으로 나머지 처리.
STL sort는 Stable Sort가 아니기 때문에, Stable Sort가 필요하다면 stable_sort함수를 사용!(사용법 동일)
pair, tuple은 제일 앞의 원소의 대소를 비교하고, 만약 같다면 다음 원소의 대소를 비교함.
pair1 : {2, 5}, pair2{3, -2}
-> pair1 < pair2
tuple1 : {2, 1, 0}, tuple2{2, -2, 6}
-> tuple1 > tuple2
따라서, 좌표를 정렬하거나 기타 속성이 있는 원소를 정렬할 때, 구조체보다는 pair나 tuple이 용이함.
1) 사용법
1. sort(시작, 끝)
2. sort(시작, 끝, 비교 함수)
2번에서 보듯이, 비교 함수를 사용자가 지정할 수 있음.
만약 배열을 정렬하고자 한다면 다음과 같이 하고
int a[5] = {1, 4, 5, 2, 7};
sort(a, a+5);주어진 배열에서,
5로 나눈 나머지 순으로, 나머지가 같다면 크기 순으로 정렬하고자 한다면
bool Cmp(int a, int b){
if(a % 5 != b % 5) return a % 5 < b % 5;
return a < b;
}
int a[5] = {1, 4, 5, 2, 7};
sort(a, a+5);2) 비교 함수의 주의 사항
(1) 두 값이 같거나 우선 순위가 같을 때, false를 반환
이 때, 비교함수에서는, a가 b의 앞에 와야할 때만 true를 반환해야하니,
두 값이 같거나 우선 순위가 같다면 반드시 false를 반환해야 함.
-> 런타임에러를 발생시키기도 함.
(2) 인자로, STL 혹은 클래스 객체 전달시 reference를 사용
만약 reference로 전달하지 않으면, 값의 복사가 일어나게 되는데 불필요함.
그냥 reference로 전달하면 복사 과정이 일어나지 않음.
따라서
bool cmp(string a, string b)보다는
bool cmp(const string& a, const string& b)가 바람직함.
-> 수행 시간에서 약간의 차이는 있을 수 있겠지만, 에러는 발생하지 않음
따라서, 두 값이 같을 때는 반드시 false를 반환하자!!
7. Q&A
-
8. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
