5. 퀵정렬

퀵정렬 또한 분할통치법에 기초한 정렬 알고리즘 중 하나이다.

🔍분할 통치법

분할: 기준 윈소 (pivot)을 택하여 리스트를 세부분으로 분할한다.

• LT(pivot보다 작은 원소들)
• EQ(pivot과 같은 원소들)
• GT( pivot보다 큰 원소들)

통치: 위 세개를 결합해나감

재귀: LT, GT를 정렬함.

합병정렬엔 합병이 중요했으나, 퀵정렬은 분할이 중요하다.

🔍알고리즘

리스트의 크기를 보고 L안의 k(pivot)을 정함.

이후 해당 k를 기준으로 LT, EQ, GT를 나눈 후

• 나누면서 정렬되어감.

각 부분별로 재귀하여 똑같이 분할

이후 병합.

🔍분할

L을 기준으로 맨앞, 맨뒤에서 리스트 삽입 혹은 삭제함.

삭제한 리스트는 LT, EQ, GT에 결과에 맞게 삽입해줌.

🔍피봇 선택 기준

기준 원소 선택 실패 시 분할결과, 퀵정렬 수행성능에 영향을 준다.

• 가장 큰 수, 가장 작은 수가 피봇으로 설정될 경우. O(n^2

결정적이며 쉬운 방법: 맨앞, 맨뒤, 중간 원소를 추출

• 약점: 이미 정렬되었을 경우 가장 큰수, 작은수가 피봇이 된다.

결정적이며 조금 복잡한 방법

1. 맨앞, 중간, 맨뒤 위치의 세 원소의 중앙값
2. 5등분한 위치의 다섯 원소의 중앙값
3. 전체 원소의 중앙값

무작위 방법: 랜덤으로 돌림

🔍제자리 퀵정렬

위의 퀵정렬은 제자리가 아닌 다른 공간에 정렬시키는 방식을 사용했다. 제자리가 아닌 다른 공간에 정렬시키는

제자리로 알고리즘을 직접 구현하는 방법이 있을까?

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int findPivot(int l, int r) {
	return rand() % (r - l + 1) + l;
}

int inPlacePartition(int* L, int l, int r) {
	if (l >= r) {
		return l;
	}
	int pivot = findPivot(l, r);
	int pivotValue = L[pivot];

	int tmp = L[pivot];
	L[pivot] = L[r];
	L[r] = tmp;

	int left = l;
	int right = r-1;
	while (left <= right) {
		while (left <= right && L[left] <= pivotValue) {
			left++;
		}
		while (left <= right && L[right] >= pivotValue) {
			right--;
		}
		if (left < right) {
			tmp = L[left];
			L[left] = L[right];
			L[right] = tmp;
		}
	}
	tmp = L[left];
	L[left] = L[r];
	L[r] = tmp;

	return left;
}

void quickSort(int* L, int l, int r) {
	if (l > r) {
		return;
	}
	int part = inPlacePartition(L, l, r);
	quickSort(L, l, part - 1);
	quickSort(L, part + 1, r);
}

int main() {
	int n;
	int* ar;

	scanf("%d", &n);
	ar = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &ar[i]);
	}
	quickSort(ar, 0, n - 1);
	for (int i = 0; i < n; i++) {
		printf(" %d", ar[i]);
	}
	free(ar);
	return 0;
}

위는 내가 직접 구현한 퀵정렬 코드이다. 하나하나 살펴보자.

🔍분할부

int inPlacePartition(int* L, int l, int r) {
	if (l >= r) {
		return l;
	}
	int pivot = findPivot(l, r);
	int pivotValue = L[pivot];

	int tmp = L[pivot];
	L[pivot] = L[r];
	L[r] = tmp;

	int left = l;
	int right = r-1;
	while (left <= right) {
		while (left <= right && L[left] <= pivotValue) {
			left++;
		}
		while (left <= right && L[right] >= pivotValue) {
			right--;
		}
		if (left < right) {
			tmp = L[left];
			L[left] = L[right];
			L[right] = tmp;
		}
	}
	tmp = L[left];
	L[left] = L[r];
	L[r] = tmp;

	return left;
}

1. 피봇은 findpivot을 통해 랜덤으로 분할한다.
2. 여기서 피봇을 맨 뒤 원소와 바꾸어 둔다.
   • 이유: 제자리이므로 피봇이 들어갈 자리를 유연하게 해줌.(알고리즘에서 설명)
3. 이후 왼쪽 포인터는 l로 오른쪽 포인터는 맨 뒤 한칸 뺀 r-1로 초기화 해줌
4. 반복문을 통해 왼쪽 포인터는 피봇보다 클때까지 오른쪽은 피봇보다 작을때까지(내림차순일 경우 반대) 움직임.
5. 만약 두 포인터가 멈췄으면 교환, 혹은 만나면 정지
6. 정지되었을 경우 피봇이 그자리에 들어감.
   • 이렇게 하여 피봇을 기준으로 LT, EQ,GT가 나뉘어진다.

🔍재귀부

void quickSort(int* L, int l, int r) {
	if (l > r) {
		return;
	}
	int part = inPlacePartition(L, l, r);
	quickSort(L, l, part - 1);
	quickSort(L, part + 1, r);
}

위에서 분할 함수를 통해 피봇의 위치를 반환받은 후

해당 피봇을 기준으로 재귀 실행한다.

왼쪽 부와 오른쪽 부를 두번 실행.

배열을 통해 제자리 정렬했으므로 Merge할 필요가 없다.

🔍퀵정렬의 장점

합병정렬은 최악의 경우에도 O(n log n)의 실행시간이 소요되지만,

퀵정렬은 최악의 경우 O(n^2)의 실행시간이 소요된다.

그러나 퀵정렬이 실제 실행에서는 더 빠르다

1. 메모리 사용 효율퀵정렬은 제자리정렬알고리즘으로 메모리 효율이 좋고 추가 복사 작업이 필요 없다.
2. 합병정렬은 분할후 병합과정에서 추가 메모리 공간이 필요하다. 따라서 메모리 할당과 복사에 시간이 걸려 연산 비용이 증가된다. 그러나
3. 캐시 사용퀵정렬: 배열을 직접 수정하여 특정 피벗을 기준으로 교환하므로 지역성이 좋아 캐시 히트율이 늘어난다.
4. 합병정렬은 배열의 요소를 순차 접근 하긴 하지만, 임시 배열을 사용하기 때문에 메모리 접근 패턴이 분산된다. (캐시 히트율 감소)
5. 상수항의 차이
6. 합병정렬은 상수항에서 복사, 비교과정이 들어가므로 실제 상수 연산량이 많다.

위같은 이유로 퀵정럴이 실제 실행에선 더 빠르다.