quick_sort

quick_sort

quick_sort(퀵 정렬)은 정렬 알고리즘 중 한 종류이다 퀵정렬은 최악의 경우에는 O(n2)번의 비교를 수행하지만 평균적으로 O(n log n)번의 비교를 수행한다

quick_sort의 특징

• 추가적인 공간이 필요하지 않다 퀵 정렬은 기존에 할당된 배열에서 swap만 이루어지기 때문에 추가적인 공간을 할당할 필요없이 정렬을 시킬 수 있다
• 평균적인 경우 다른 O(n log n) 정렬보다 빠르다 같은 O(n log n)시간복잡도를 가지고있는 정렬 방식이여도 퀵정렬을 경우 추가적인 공간을 할당하는 시간이 없고 계속 같은 주소를 참조해서 cpu의 캐시 메모리를 잘 활용하기 때문에 더 빠른 속도를 얻을 수 있다
• 최악의 경우 O(N2)의 시간복잡도로 동작된다 만약 pivot이 계속 가장 낮은 수나 가장 큰 수만 고를경우 O(N2)만큼 동작하게 된다 이를 방지하기 위해서는 pivot을 설정할때 랜덤값으로 설정하게 하면 최악의 경우로 동작활 확률을 낮출 수 있다

quick_sort의 동작 방식

퀵정렬은 재귀적으로 동작하는 정렬방식이다 매 재귀마다 pivot이라고 불리는 원소 하나를 설정하여 해당 pivot보다 작은 값들을 왼쪽으로 큰 값들을 오른쪽으로 보내고 새로 pivot을 설정해 다시 반복시키는 과정을 재귀적으로 반복하여 정렬을 마무리한다
아래는 실제로 Push_swap과제 도중 qucik_sort를 구현한 코드이다

void	mid_quick_sort(int *temp_stack, int left, int right)
// temp_stack : 정렬해야될 배열
// left, right : 정렬을 할 범위
{
	int	low;
	int	high;
	int	pivot;

	if (left >= right)
    // left가 right보다 크거나 같다는 말은 정렬이 다 이루어진것이므로 재귀를 종료한다
		return ;
	low = left + 1; // 배열을 이동하면서 탐색할 low 와 high를 초기 세팅해준다
	high = right;
	pivot = temp_stack[left]; // left값을 pivot으로 설정한다
	while (1)
	{
		while (temp_stack[low] < pivot && low <= right)
        // pivot보다 low위치의 값이 클때까지 반복한다
			low++;
		while (temp_stack[high] > pivot && high > left)
        // pivot보다 high의 값이 작을때까지 반복한다
			high--;
		if (low >= high)
        // 만약 low가 high보다 같거나 커지면 배열의 값들을 다 테스트 한 것이므로 반복을 탈출한다
			break ;
		ft_swap(&temp_stack[low], &temp_stack[high]);
        // 두 값을 바꿔준다 이렇게 하면 pivot을 기준으로 좌 우로 분리가 된다
	}
	ft_swap(&temp_stack[left], &temp_stack[high]);
    // pivot을 자신이 들어갈 위치로 보내준다
	mid_quick_sort(temp_stack, left, high);
    // 재귀함수를 호출하는데 right인자에 high값을 넣어 pivot을 기준으로 왼쪽 부분을 정렬 시킨다
	mid_quick_sort(temp_stack, high + 1, right);
    // 재귀함수를 호출하는데 left부분에 high + 1값을 넣어 pivot을 기준으로 오른쪽 부분을 정렬 시킨다
}