push_swap(2) - 퀵정렬, 병합정렬

push_swap 프로젝트를 진행할 때 많이 사용하는 정렬 알고리즘 중 대표적인 2개 퀵정렬(quick sort)와 병합정렬(merge sort)
정렬 알고리즘에 대한 개념을 이해하고 넘어가겠습니다.

버블, 선택, 삽입 정렬의 경우 시간복잡도가 O(n^2)으로 효율적이지 못해 평균 시간 복잡도가O(n log n)인 분할 정복 알고리즘 퀵정렬과 병합정렬에 대해 설명하겠습니다.

퀵정렬(quick sort)

void	swap(int *a, int *b)
{
	int	temp;

	temp = *a;
	*a = *b;
	*b = temp;
}

void	quick(int start, int end, int *arr)
{
	int	pivot;
	int	i;
	int	j;

	if (start >= end)
		return ;
	pivot = end;
	i = start;
	j = end - 1;
	while (i <= j)
	{
		while (i <= end && arr[i] < arr[pivot])
			++i; // start에서 피봇보다 큰 값이 나올때까지 탐색
		while (j >= start && arr[j] > arr[pivot])
			--j; // end에서 피봇보다 작은 값이 나올때까지 탐색
		if (i < j)
			swap(&arr[i], &arr[j]); //큰 값과 작은값의 위치를 교환
	}
	swap(&arr[i], &arr[pivot]); // 피봇 위치를 arr[i]로 교환
	quick(start, i - 1, arr); // 피봇보다 작은값을 퀵정렬
	quick(i + 1, end, arr); // 피봇보다 큰 값을 퀵정렬
}

arr : 숫자를 담은 배열
start : 시작 index 번호
end : 끝 index 번호
pivot : 퀵 정렬의 기준이 되는 원소, 이 글에선 마지막 원소로 지정

1. 배열을 시작과 끝 양쪽에서 순회하면서 pivot을 기준으로 큰값과 작은값을 찾은다음에 두 값을 서로 교환합니다.

2. start에서 시작한 인덱스 i와 end에서 시작한 인덱스 j가 만나면,
   해당 위치로 pivot을 옮겨서 왼쪽에는 pivot보다 작은값이, 오른쪽에는 pivot보다 큰 값이 존재하게 됩니다.

3. 이렇게 pivot의 위치를 찾게되고 두개로 나뉜 배열을 똑같은 방법으로 계속 진행합니다.

4. 해당 방식을 start >= end가 될때까지 즉 배열사이즈가 1이 될 때 까지 반복하면 정렬이 완료됩니다.

퀵정렬은 이름에서 유추할 수 있듯 가장 빠른 정렬로 평균 시간 복잡도가O(n log n)이지만, 최악의 경우 O(n^2)의 시간이 걸리므로 주의해야 합니다.

병합정렬(merge sort)

void ft_merge(int *arr, int *temp, int st, int ed)
{
	int mid = (st + ed) / 2;
	int i = st;
	int j = st;
	int k = mid + 1;

	while (i <= mid && k <= ed)
	{
		if (arr[i] > arr[k])
		{
			temp[j] = arr[k];
			j++;
			k++;
		}
		else
		{
			temp[j] = arr[i];
			j++;
			i++;
		}
	}
	if (i > mid)
	{
		while (k <= ed)
		{
			temp[j] = arr[k];
			j++;
			k++;
		}
	}
	else
	{
		while (i <= mid)
		{
			temp[j] = arr[i];
			j++;
			i++;
		}
	}
	for (int i = st; i <= ed; i++)
		arr[i] = temp[i];
}

void ft_sort(int *arr, int *temp, int st, int ed)
{
	if (st < ed)
	{
		int mid = st + (ed - st) / 2;
		ft_sort(arr, temp, st, mid); // 스타트부터 중간값까지 배열을 계속 분할
		ft_sort(arr, temp, mid + 1, ed); // 중간 + 1 부터 엔드값 까지 배열을 계속 분할
		ft_merge(arr, temp, st, ed); // 정렬 후 병합
	}
}

이전에 작성한 포스트에도 사용한 병합정렬 입니다. [BOJ]1920번 수찾기

위와 같은 방식으로 배열의 사이즈가 1이 될때까지 재귀적으로 분할하고 병합하면서 정렬하는 방식입니다.

병합정렬의 장점은 시간복잡도가 O(n log n)로 안정적이라는 점 입니다.

내장 정렬 알고리즘을 사용하지 못하는 상황이라면 퀵소트 대신 시간복잡도가 일정한 병합정렬을 사용해야 합니다.