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);
	}
}

나의 친절함이 보이는가 퀵소트랑 머지소트 둘다 짰다. 함수포인터 까지!
cmp
68ms가 merge sort이고
64ms가 quick sort이다.
이름값 하는거 같다. 여기서 뭐 quick sort가 O(N^2)이니 이런소리는 하지말자.
너 나 우리가 다 아는내용이다.

근데 약간의 팁을주자면(지금까지의 경험상) 정렬이 문제 푸는데에 있어서 크리티컬한 복잡도를 주는 문제면 merge sort를 쓰고 그게 아니라면 quick sort를 쓰자. 대부분 quick sort가 더 빠르더라 ㄹㅇ.

Q. cmp함수 왜저러케짬 ㅋㅋㅋ 삼항연산자 슥삭인데 ㅋㅋㅋㅋ
A. 아 ㅋㅋㅋㅋㅋ 춤마렵네 ㅋㅋㅋㅋㅋㅋ
---1
난 내가 알아보기 쉬워야함 ㅋㅋㅋㅋ

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