merge sort, quick sort를 구현해 보자
걱정이다. 이제 슬슬 내가 알고있는게 다 떨여저 간다. 근데 글쓰는거 왤케 재밋냐.
제목보고 들어왔을테니 정렬구현할꺼다.
머지소트랑 퀵소트(+ 간단한 함수포인터)
그리고 문제로 검증받아야 하니 여러문제의 풀이코드를 올리도록 하겠다.
그전에 신세한탄좀 하자
내가 std::sort()이 함수때문에 C++를 진입하지 못하고 '하... 모르겠다 걍 구현하고 말지' 라는 생각으로 'C'로 문제를 풀어왔다.
이 문제를 보자 이 문제를 정렬기준이 2개이다. 이렇게 정렬기준이 여러개 있을때 sort(a, a + n, cmp);로 호출하는데 이 cmp함수가 뭔지 몰라따......
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>
using namespace std;
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) {
if (a.second == b.second) return (a.first < b.first);
return (a.second < b.second);
}
int main() {
int N, i, j, k;
vector< pair<int, int> > v;
scanf("%d ", &N);
for(i = 0; i < N; i++) {
scanf("%d %d", &j, &k);
v.push_back(pair<int, int>(j, k));
}
sort(v.begin(), v.end(), sortbysec);
for(i = 0; i < N; i++) {
printf("%d %d\n", v[i].first, v[i].second);
}
return 0;
}
위 코드 출처 : https://sihyungyou.github.io/baekjoon-11651/
저 sortbysec함수의 뜻을 이해 못했던것....
그리고 이후에도 한동안은 y기준 오름차순 정렬을 하고 y가 같은 구간을 뽑아서 x를 오름차순 정렬을 해서 문제풀이를 해와따... 특히나 const가 왜 붙는지 킹직히 아직도 이해못한다.
이 문제를 보자 (이거 정렬안쓰고도 풀림)
이 문제는 cpp로도 한번 풀어봤다.
#include<stdio.h>
#include<algorithm>
using namespace std;
struct info
{
int num, idx;
};
struct info list[200000];
int answer, n;
int cmp(struct info, struct info);
int make_answer();
int main(void)
{
int i, t;
scanf("%d", &t);
for (i = 1; i <= t; i++)
{
answer = make_answer();
printf("#%d %d\n", i, answer);
}
return 0;
}
int make_answer()
{
register int i, count;
scanf("%d", &n);
for (i = count = 0; i < n; i++)
{
scanf("%d", &list[i].num);
list[i].idx = i;
}
sort(list, list + n, cmp);
for (i = count = 0; i < n - 1; i++)
{
if (list[i].idx > list[i + 1].idx)
{
count++;
}
}
return count + 1;
}
int cmp(struct info a, struct info b)
{
return a.num < b.num;
}
위는 내 cpp풀이 코드인다.cmp함수 보면은 const없이도 ac받았다. 음... 그냥 생각나는건는 '값 안바뀌게 할려고(안전) 넣은건데 내가 뭐 PS하면서 쓰레드 돌릴것도 아니니 const없어도 된다.' 라고 그냥 지금은 생각하고 있다.
신세한탄 끝
우리는 이 문제를 풀어볼 것이다. 정렬기준이 두가지 이다.
"y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서"
바로 코드를 보자.
#include<stdio.h>
struct point
{
int x, y;
};
struct point list[100000], sorted[100000];
int n;
void msort(struct point[], int, int, int (*cmp) (struct point, struct point));
void merge(struct point[], int, int, int, int (*cmp) (struct point, struct point));
void qsort(struct point[], int, int, int (*cmp) (struct point, struct point));
int cmp(struct point, struct point);
void make_answer();
int main(void)
{
make_answer();
return 0;
}
void make_answer()
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d %d", &list[i].x, &list[i].y);
}
msort(list, 0, n - 1, cmp);
qsort(list, 0, n - 1, cmp);
for (i = 0; i < n; i++)
{
printf("%d %d\n", list[i].x, list[i].y);
}
}
void msort(struct point list[], int left, int right, int (*cmp) (struct point, struct point))
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
msort(list, left, mid, cmp);
msort(list, mid + 1, right, cmp);
merge(list, left, mid, right, cmp);
}
}
void merge(struct point list[], int left, int mid, int right, int (*cmp) (struct point, struct point))
{
int i, j, k, l;
i = k = left;
j = mid + 1;
while (i <= mid && j <= right)
{
if (cmp(list[i], list[j]))
{
sorted[k++] = list[i++];
}
else
{
sorted[k++] = list[j++];
}
}
if (mid < i)
{
for (l = j; l <= right; l++)
{
sorted[k++] = list[l];
}
}
else
{
for (l = i; l <= mid; l++)
{
sorted[k++] = list[l];
}
}
for (l = left; l <= right; l++)
{
list[l] = sorted[l];
}
}
int cmp(struct point a, struct point b)
{
if (a.y < b.y)
{
return 1;
}
else if (a.y == b.y)
{
if (a.x < b.x)
{
return 1;
}
else
{
return 0;
}
}
else
{
return 0;
}
}
void qsort(struct point list[], int l, int r, int (*cmp) (struct point, struct point))
{
int i, j;
struct point p, t;
i = l;
j = r;
p = list[(i + j) / 2];
do
{
while (cmp(list[i], p))
{
i++;
}
while (cmp(p, list[j]))
{
j--;
}
if (i <= j)
{
t = list[i];
list[i] = list[j];
list[j] = t;
i++;
j--;
}
} while (i <= j);
if (l < j)
{
qsort(list, l, j, cmp);
}
if (i < r)
{
qsort(list, i, r, cmp);
}
}
나의 친절함이 보이는가 퀵소트랑 머지소트 둘다 짰다. 함수포인터 까지!
68ms가 merge sort이고
64ms가 quick sort이다.
이름값 하는거 같다. 여기서 뭐 quick sort가 O(N^2)이니 이런소리는 하지말자.
너 나 우리가 다 아는내용이다.
근데 약간의 팁을주자면(지금까지의 경험상) 정렬이 문제 푸는데에 있어서 크리티컬한 복잡도를 주는 문제면 merge sort를 쓰고 그게 아니라면 quick sort를 쓰자. 대부분 quick sort가 더 빠르더라 ㄹㅇ.
Q. cmp함수 왜저러케짬 ㅋㅋㅋ 삼항연산자 슥삭인데 ㅋㅋㅋㅋ
A. 아 ㅋㅋㅋㅋㅋ 춤마렵네 ㅋㅋㅋㅋㅋㅋ
난 내가 알아보기 쉬워야함 ㅋㅋㅋㅋ
Q. quick sort에서
while (cmp(list[i], p))
{
i++;
}
while (!cmp(list[j], p))
{
j--;
}
는 안대나요??
A. 안된다. 실제로 해보면 아나 rte가 날 것이다.
이유는 Strict weak orderings이란게 있다.(존나 유식해 보이지 않는가?) 이걸 검색해 보도록
(사실 나도 잘 모름 ㅋ) 혹은 이 글을 보자
함수 포인터 저 부분이 C++ std::sort 에서
sort(list, list + n, cmp);
cmp 인자이다.
문제를 풀다보면 똑같은 배열에서 다른 기준으로 문제를 풀어야 할 상황이 있다. 예를들어 이 문제를 처음 풀때 나는 정렬을 다른기준으로 2번했었던 기억이 있다.
(근데 뭐 두번 정렬할 필요는 없다;;;; 한번이면 된다. 참고로 이 문제를 정렬만 가지고는 못푼다.나중에 풀이에 필요한 준비물을 포스팅 아마 할것같다.)
이런 상황일떄 예전의 나처럼 msort1, msort2이렇게 만들지 말고 cmp1, cmp2 이렇게 비교함수만 짧게 짧게 만들고 구현을 하자!
아 그리고 비교기반의 자료구조를 사용할때 저런 비교함수 사용하면 편하다. 예를들어
https://www.acmicpc.net/problem/11286 혹은 https://www.acmicpc.net/problem/14428