0x0E 정렬 I
0x00 기초정렬
Selection Sort
int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
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]);
}
//STL
for(int i=n-1; i>0; i--) {
swap(*max_element(arr, arr+i+1), arr[i]);
}max_element(arr, arr+k)는 arr[0], arr[1], arr[2], ..., **arr[k-1]**에서 최댓값인 원소의 주소를 반환해주는 함수. arr[k]까지가 아니라 **arr[k-1]**까지라는걸 주의해야 한다.
전체 배열에서 가장 큰 원소가 들어있는 인덱스를 알고 싶다고 하면 k = max_element(arr, arr+n) - arr : 포인터끼리 빼서 인덱스를 구하는 방식이다.
시간복잡도 : O(N²)
Bubble Sort
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]);
}
}시간복잡도 : O(N²)
삽입, 선택, 버블 정렬 3개는 O(N²)에 동작하는 대표적인 정렬 방법
0x01 Merge Sort
시간복잡도 : O(NlgN)
11728번 : 배열 합치기
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000002], b[1000002], c[2000004];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
int aidx = 0, bidx = 0;
for(int i=0; i<n+m; i++) {
if(aidx= n) c[i]= b[bidx++];
else if(bidx= m) c[i]= a[aidx++];
else if(a[aidx] >= b[bidx]) c[i] = b[bidx++];
else c[i] = a[aidx++];
}
for(int i=0; i<n+m; i++) cout << c[i] << " ";
}Stable Sort라는 성질을 만족시키기 위해서는 가능하면 둘의 크기가 같을 때 앞쪽의 원소, 즉 a[aidx]가 c에 들어가야 한다. 조금 있다가 Stable Sort에 대해 설명할 때 지금 내용을 기억하기.
Merge Sort
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수
// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en){
int mid = (st+en)/2;
int lidx = st;
int ridx = mid;
for(int i=st; i<en; i++) {
if(lidx= mid) tmp[i]= arr[ridx++];
else if(ridx= en) tmp[i]= arr[lidx++];
else if(arr[lidx] >= arr[ridx]) tmp[i] = arr[ridx++];
else tmp[i] = arr[lidx++];
}
for(int i=st; i<en; i++) arr[i]= tmp[i];
}
// arr[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en){
if(en-st= 1) return; // 길이 1인 경우
int mid= (st+en)/2;
merge_sort(st, mid); // arr[st:mid]을 정렬한다.
merge_sort(mid, en); // arr[mid:en]을 정렬한다.
merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
merge_sort(0, n);
for(int i= 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357
}Stable Sort
Stable Sort : 우선순위가 같은 원소들은 원래의 순서를 따라가도록 하는 정렬
예제로 파일을 정렬하는 것과 2차원 좌표들을 x가 작은 순으로, x가 동일하다면 y가 작은 순으로 정렬하는 것이 있다.
0x02 Quick Sort
추가적인 공간을 사용하지 않는 정렬 ( In-Place Sort ) Cache hit rate가 높아서 굉장히 빠르다.
0번을 pivot으로 두고 pivot보다 작은건 왼쪽, 큰건 오른쪽에 배치하도록 하는 방법 (추가적인 공간을 사용하지 않고 Ex_tmp 배열)
#include <bits/stdc++.h>
using namespace std;
int n = 8;
int arr[1000001];
void quick_sort(int st, int en) { // arr[st to en-1]을 정렬할 예정
if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
int pivot= arr[st]; // 제일 앞의 것을 pivot으로 잡는다. 임의의 값을 잡고 arr[st]와 swap해도 상관없음.
int l= st+1; // 포인터 l
int r= en-1; // 포인터 r
while(1) {
while(l <= r && arr[l] <= pivot) l++;
while(l <= r && arr[r] > pivot) r--;
if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
swap(arr[l], arr[r]);
}
swap(arr[st], arr[r]);
quick_sort(st, r);
quick_sort(r+1, en);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
quick_sort(0, n);
for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}시간복잡도
O(NlgN), 하지만 최악의 경우 O(N²)
따라서 코딩테스트에서 STL 사용하지 못하면 퀵소트 사용하지 말기. 머지소트도 O(NlgN)에 돌아가서 충분히 빠르다.
STL은 pivot을 랜덤하게 선택하는 처리, pivot 후보를 3개 정해서 그 3개 중에서 중앙값을 피벗으로 두기도 한다. 그리고 최악의 경우에도 O(NlgN)을 보장하기 위해서 일정 깊이 이상 들어가면 퀵 소트 대신 힙 소트로 정렬한다. 이를 Introspective sort라고 한다.
Merge Sort vs Quick Sort
리뷰
대학수업시간에 했던 정렬의 내용이여서 다시 리마인드하는 느낌으로 들을 수 있었다.
다시 들으니 새롭고 강의를 멈춰놓고 생각을 쥐어짜니 코드들도 생각이 났다.
가볍게 정리하고 다음은 0X0F 정렬 II로 돌아오겠다.
출처: 바킹독님의 실전알고리즘 강의