정렬알고리즘_퀵 정렬 [4/8]

[ 퀵 정렬이란? ]

• 특정 값을 기준으로 정렬해야할 데이터그룹을 소규모 그룹으로 쪼개가며 정렬하는 방식
• 일반적으로 정렬은 n의 크기에 따라 O(n^2)로 시간 복잡도가 증가하지만, n의 크기를 일정하게 유지해 나가며 데이터를 정렬하기 때문에 O(n*logN)의 평균 시간 복잡도를 지니게 됨
• 이미 정렬이 잘 되어 있는 경우는 삽입 정렬에 비해 비효율적인 방식이 될 수 있음

---

 

1. 가장 첫 값을 피봇값으로 지정해서 시작
2. 오른쪽으로는 피봇값보다 큰 숫자를 찾고 왼쪽으로는 작은 숫자를 찾음
3. 둘 다 찾았는데 큰값의 위치와 작은 값의 위치가 교차되지 않았다면 두 숫자를 바꿔줌
4. 두 위치가 교차되었다면, pivot값과 left 값을 바꿔줌

 

크로스가 발생했다는 것은, 현 left의 위치까지 피봇값보다 큰 값은 없다는 것을 의미

 

기준값보다 큰 숫자보다, 작은 숫자가 더 왼쪽에 있기 때문에 그 위치에 피봇값을 가져다두면 피봇값보다 작은 왼쪽그룹, 큰 오른쪽 그룹으로 나눠지게 되는 것이죠. 이 상태에서 각 아래와 같이 그룹별로 다시 동일 로직을 수행합니다.

 

 

이렇게 하나하나 쪼개서 수행하다보면 언젠가 정렬이 다 되게 됩니다. 한 배열에 대한 시간 복잡도가 본래 O(n^2)이라면, 퀵 정렬은 계속 그룹을 작게 쪼개주기 때문에 데이터 갯수인 n이 증가하더라도 한번에 정렬해야하는 그룹의 크기가 일정하게 유지됩니다. 따라서 평균적인 시간 복잡도가 O(n*logN)이 되는 것이죠.

​

예를 들어 10개짜리 배열을 선택정렬이나 버블정렬하면 9+8...+1 = 45번의 과정을 거치지만, 퀵 정렬의 경우 3그룹으로 나눠서 정렬한다고 하면 3+2+1이 세 번이니 총 18번의 과정을 거치게 됩니다.

​

물론 원래부터 정렬이 돼 있는 경우, 선택정렬, 버블정렬과 같이 이를 인지하지 못하고 로직대로 정렬을 수행하기 때문에 효율성이 떨어지게 됩니다. 분할을 해가면서 해야 빨라지는데 이미 돼있는 정렬에서는 분할할 일이 없어지기 때문입니다. 정렬이 거의 돼있는 상태에서는 삽입정렬이 가장 빠른 이유입니다.

 

---

 

범위를 계속 바꿔주며 동일 로직을 수행해야하기 때문에 재귀함수를 사용하는 것이 효율적입니다.

 

1. 범위를 제공해주면 Cross가 될때까지 정렬해주는 함수를 하나 만듦
2. Cross가 발생하면 발생한 지점을 기준으로 좌, 우 범위가 생김
3. 좌측 범위를 argument로 한 재귀함수 호출
4. 우측 범위를 argument로 한 재귀함수 호출
5. 좌측, 우측 범위가 더 이상 조건에 맞지 않으면 return

#include <stdio.h>
#define SIZE 15

void swap(int* arr, int x, int y);
void quick_arrange(int* arr, int start, int end);


void main()
{
	int arr[SIZE] = { 1,5,9,3,1,14,2,1,1,7,2,10,11,13,4 };

	printf("\n    정렬 전 : ");
	/* 배열 출력 */
	for (int i = 0; i < SIZE; ++i)
		printf("%d ", arr[i]);
	printf("\n");

	/* 배열 정렬 */
	quick_arrange(arr, 0, SIZE - 1);

	printf("\n    정렬 후 : ");
	/* 배열 출력 */
	for (int i = 0; i < SIZE; ++i)
		printf("%d ", arr[i]);
	printf("\n");
}


/* 정렬함수 */
/* parameter : 정렬대상(arr), 시작범위(시작점~끝점+1) */
/* return : void */
void quick_arrange(int* arr, int start, int end)
{
	/* 함수 실행 시 원소가 하나라면 바로 리턴 */
	/* 마지막 또는 첫 값이 넘어오는 경우 start > end 발생 */
	if (start >= end)
		return;

	int right = start + 1, left = end;

	while (right <= left)
	{
		
		/* 오른쪽 검색, 범위를 넘어가서 끝나면 무조건 Cross가 발생하는 것으로 처리 */
		while (right <= end && arr[right] <= arr[start])
			right++;

		while (left > start && arr[left] >= arr[start])
			left--;

		/* Cross 된 경우, 시작값이 제일 작을 경우 굳이 swap하지 않는다. */
		if (start == left)
			continue;
		
		else if (right > left)
			swap(arr, left, start);

		else
			swap(arr, left, right);
	}

	quick_arrange(arr, start, left - 1);
	quick_arrange(arr, left + 1, end);

}


/* swap, 배열 값 바꾸기 */
/* parameter : 배열주소, 바꿀 인덱스 두 개 */
/* return : void */
void swap(int* arr, int x, int y)
{
	int temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}