정렬04 - 퀵 정렬(Quick Sort)

4. 정렬

---

정렬의 개념들 중 여기서부터 조금씩 복잡하고 이해하기가 까다롭다고 느껴지는데 원리를 이해하고 실제로 코딩해보면 이해하기가 쉽습니다. 저도 아무것도 안보고 코딩하라고 하면 아직까지는 시간이 조금 소요되는 알고리즘이었습니다.

하단의 코드는 위키를 참고하여 작성하였습니다.

 

퀵 정렬은 피벗(Pivot)을 하나 정하고 리스트를 분할하여 정렬하는 방식입니다.

리스트 중 보통 끝 값을 피벗으로 정하고 리스트 앞에는 피벗보다 작은 값이 존재하도록 하고 뒤쪽에는 피벗보다 큰 값이 위치하도록 하면 됩니다.

 

 

원리 예시

1, 10, 4, 6, 7, 2, 5, 9, 3, 8 
                            P

8을 피벗(P)이라고 하면

1, 10, 4, 6, 7, 2, 5, 9, 3, 8 
i                        j  P

low 값 i와 high값 j를 비교하여 만약 i가 크다면 위치를 바꿔줍니다.

1, 10, 4, 6, 7, 2, 5, 9, 3, 8 
    i                    j  P

1, 3, 4, 6, 7, 2, 5, 9, 10, 8 
   i                     j  P

여기서 주의할 점은 피벗(P)보다는 i가 커야 합니다. 그 이유는 위의 원리에서도 설명했듯이 피벗(P)보다 작은 값을 앞으로 오게 하기 위함입니다.

위와 같이 i보다 j가 크면서 i가 P보다 작다면 i와 j의 위치를 변경합니다.

 

1, 3, 4, 6, 7, 2, 5, 9, 10, 8 
      i              j      P​

그 이후 i++와 j-- 를 진행합니다.

1, 3, 4, 6, 7, 2, 5, 9, 10, 8 
                    ij      P

1, 3, 4, 6, 7, 2, 5, 8, 10, 9 
                     P

이후 계속 i 가 증가하다가 i와 j가 같은 지점에 올 경우 피벗(P)과 i의 위치를 변경합니다.

 

1, 3, 4, 6, 7, 2, 5             10, 9 
                  P                 P

이후 피벗(P)을 기준으로 리스트를 분할하고 재귀적으로 수행합니다.

 

코드

#include <stdio.h>

int num = 10;
int arr[] = { 1, 10, 4, 6, 7, 2, 5, 9, 3, 8 };

void show() {
	int i;
	for (i = 0; i < num; i++)
		printf("%d ", arr[i]);
}

inline void swap(int& a, int& b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void quickSort(int arr[], int low, int high) {
	if (low >= high)
		return;
	int i = low - 1, j = low;
	int& pivot = arr[high];
	for (; j < high; j++) {
		if (arr[j] < pivot)
			swap(arr[++i], arr[j]);
	}
	swap(arr[++i], pivot);

	quickSort(arr, low, i - 1);
	quickSort(arr, i + 1, high);
}

int main(void) {
	quickSort(arr, 0, num - 1);
	show();
	return 0;
}

 

퀵 정렬은 최악의 경우에는 앞서 설명한 선택, 버블, 삽입 정렬과 마찬가지로 n^2의 시간복잡도를 가지지만 보통의 경우에는 n*logn 의 시간복잡도를 가집니다. 다른 정렬에 비해 보통 빠르다는 것을 의미합니다. 하지만 불완전 정렬이기 때문에 정렬 순서에 민감하다면 사용에 주의해야 합니다.