C언어) quick sort

<설명>

퀵 정렬(quick sort)은 기준값(pivot)을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.

 

<로직>

양쪽에 포인트를 잡고, 정렬 기준에 맞는지를 판단하여 맞지않는 점끼리 스왑한다.

스왑이 끝나면 pivot을 기준 위치에 넣어준다.

재귀

 

<코드>

void	ft_swap(int *l_arr, int *r_arr)
{
	int tmp;

	tmp = *l_arr;
	*l_arr = *r_arr;
	*r_arr = tmp;
}

void	quick_sort(int *arr, int start, int end)
{
	int	s_pnt;
	int	e_pnt;
	int	pivot;

	s_pnt = start;
	e_pnt = end;
	pivot = arr[start];
	if (start >= end)
		return ;
	while (s_pnt < e_pnt)
	{
		while (arr[s_pnt] <= pivot && s_pnt < end)
			s_pnt++;
		while (arr[e_pnt] > pivot && e_pnt > start)
			e_pnt--;
		if (s_pnt >= e_pnt)
			break ;
		ft_swap(&arr[s_pnt], &arr[e_pnt]);
	}
	ft_swap(&arr[start], &arr[e_pnt]);

	quick_sort(arr, start, e_pnt - 1);
	quick_sort(arr, e_pnt + 1, end);
}

ft_swap 함수는 말 그대로 swap해주는 함수이다, 코드가 길어져 따로 만들었다.

 

 

quick_sort의 인자값은 배열과, 배열의 시작과 끝 인덱스이다.

시작과 끝 인덱스는 재귀를 위해 넣었다.

 

 

왼쪽과 오른쪽 포인트를 s_pnt, e_pnt로 두고,

while문을 돌면서 기준에 맞지 않는 점들끼리 swap한다.

(작거나 같은 값을 지닌 데이터는 기준점 앞으로, 큰 값을 지닌 데이터는 기준점 뒤로 가도록 )

 

 

정렬이 끝나 s_pnt와 e_pnt가 엊갈리면 while문을 나와, pivot을 제자리에 넣어준다.

나는 pivot을 start점으로 잡았으므로, &arr[start]가 pivot을 나타낸다.

e_pnt가 멈춘 점은 어짜피 pivot보다 작거나 같은 점이므로, 피봇과 스왑해 위치를 맞춰준다.

 

 

다시 e_pnt를 기준으로 앞과 뒤를 쪼개 재귀한다.

 

 

<참고하면 좋을 자료>

https://www.youtube.com/watch?v=cWH49IKDIiI&t=256s 

https://hongku.tistory.com/149

자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)