정렬(Sorting)

1. 단순한 정렬 알고리즘

이번 챕터에서는 각종 정렬 알고리즘을 소개하고자 한다.

다른 챕터처럼 코드에 중점을 두거나 설명을 자세히 하지 않고, 각각의 알고리즘이 갖는 특징에 집중해볼 것이다.

---

2. 버블 벙렬(Bubble Sort)

버블 정렬은 정렬의 대명사로 알려져 있는, 이미 알고 있을만한 정렬방법이다.

그만큼 이해하기도 구현하기도 쉽다.

물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있다.

위 그림에서 보이듯이, 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

두 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나간다.

다음은 버블 정렬의 코드이다.

#include <stdio.h>

void BubbleSort(int arr[], int n)
{
	int i, j;
	int temp;

	for(i=0; i<n-1; i++)
	{
		for(j=0; j<(n-i)-1; j++)
		{
			if(arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}


int main(void)
{
	int arr[4] = {3, 2, 4, 1};
	int i;

	BubbleSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

위의 코드에서는 버블 정렬을 구성하는 두 for문의 반복조건이 핵심이다.

버블 정렬의 빅-오는 for문이 중첩되어 있으므로 최악의 경우와 최선의 경우 구분 없이 다음과 같다.

$O(n^2)$

단순히 보면 반복문이 중첩되어 있을 뿐인데, 이렇듯 실제 활용하기 부담스러운 정도의 성능을 보여준다.

---

3. 선택 정렬(Selection Sort)

이번에 소개하는 선택 정렬은 버블 정렬보다도 쉽고 간단한 알고리즘이다.

다음 그림에서 1, 2, 4, 3이 나란히 저장된 배열의 오름차순 정렬과정을 보이는데, 이 그림만 봐도 이해할 수 있을 정도로 간단하다.

위 그림에서 보이듯이 선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘이다.

"그럼 선택 정렬은 정렬결과를 담을 별도의 메모리 공간이 필요하겠네요."

위 그림에서 보이는 대로 진행을 한다면 별도의 메모리 공간이 필요하다.

하지만 데이터를 하나 옮길 때마다 공간이 하나씩 비게 된다는 사실을 기반으로, 다음 그림에서 보이는 바와 같이 알고리즘을 개선시키면 메모리 공간을 마련할 필요가 없다.

그럼 3, 4, 2, 1의 정렬과정을 보이는 다음 그림을 보자.

위의 그림에서는 '교환'이라는 표현을 사용하고 있지만, 의미상 적절한 표현은 아니다.

따라서 다음과 같이 이해할 필요가 있다.

"정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈자리에 가져다 놓는다."

맞다! 결론적으로는 교환이 맞다.

하지만 '빈 자리를 활용하는 과정에서 비롯된 교환'이란 사실을 이해하기 바란다.

그럼 이어서 선택 정렬의 코드를 보자.

#include <stdio.h>

void SelSort(int arr[], int n)
{
	int i, j;
	int maxIdx;
	int temp;

	for(i=0; i<n-1; i++)
	{
		maxIdx = i;    // 정렬 순서상 가장 앞서는 데이터의 index

		for(j=i+1; j<n; j++)   // 최소값 탐색
		{
			if(arr[j] < arr[maxIdx])
				maxIdx = j;
		}

		/* 교환 */
		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}


int main(void)
{
	int arr[4] = {3, 4, 2, 1};
	int i;

	SelSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

코드에 for 반복문이 중첩되어 있는 것만 봐도 버블 정렬과 성능상 큰 차이가 없음을 알 수 있다.

선택 정렬의 빅-오 역시 최악, 최선의 경우 구분 없이 다음과 같다.

$O(n^2)$

---

4. 삽입 정렬(Insertion Sort)

이번에 소개하는 삽입 정렬은 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다.

하지만 전혀 다른 방법으로 정렬을 이뤄나간다.

위 그림의 배열은 정렬이 완료된 부분과 완료되지 않은 부분으로 나뉘어 있다.

이렇듯 삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘이다.

그럼 다음 그림을 통해서 5, 3, 2, 4, 1의 오름차순 정렬과정을 보이겠다.

위 그림의 가장 윗부분에서 보이듯이, 첫 번째 데이터와 두 번째 데이터를 비교하여, 정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬은 시작된다.

그리고 이로 인해서 첫 번째 데이터와 두 번째 데이터가 정렬이 완료된 영역을 형성하게 된다.

이어서 세 번째, 네 번째 데이터가 정렬이 완료된 영역으로 삽입이 되면서 정렬을 이어 나간다.

물론 정렬된 상태로 삽입하기 위해서는 특정위치를 비워야 하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야 한다.

참고로 구현에 도움이 될만한 말 몇 마디를 하면 다음과 같다.

"정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다."

"삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다."

위에서 언급한 '데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는다'는 것이 의미하는 바를 그림을 통해서 설명하겠다.

이 그림에서는 숫자 3을 정렬이 완료된 영역으로 옮기는 과정을 보이고 있다.

위 그림에서 보이듯이, 삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 없다.

어차피 정렬된 영역에서 삽입의 위치를 찾는 것이니, 삽입위치를 찾으면서 삽입을 위한 공간의 마련을 병행할 수 있는 것이다.

그럼 이어서 삽입 정렬의 구현의 예를 보이겠다.

#include <stdio.h>

void InserSort(int arr[], int n)
{
	int i, j;
	int insData;

	for(i=1; i<n; i++)
	{
		insData = arr[i];   // 정렬 대상을 insData에 저장

		for(j=i-1; j>=0 ; j--)
		{
			if(arr[j] > insData) 
				arr[j+1] = arr[j];    // 비교 대상 한 칸 뒤로 밀기
			else
				break;   // 삽입 위치 찾았으니 탈출!
		}

		arr[j+1] = insData;  // 찾은 위치에 정렬 대상 삽입!
	}
}


int main(void)
{
	int arr[5] = {5, 3, 2, 4, 1};
	int i;

	InserSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<5; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

삽입 정렬은 정렬대상의 대부분이 이미 정렬되어 있는 경우 매우 빠르게 동작한다.

하지만 역시나 for 문이 중첩되어 있기 때문에 빅-오가 다음과 같음을 쉽게 추측할 수 있다.

$O(n^2)$

---

5. 복잡하지만 효율적인 정렬 알고리즘

앞서 소개한 단순한 정렬 알고리즘들도 정렬대상의 수가 적은 경우 효율적으로 사용할 수 있어서 나름의 의미를 지닌다.

하지만 정렬대상의 수가 적지 않은 경우에는 보다 만족스러운 결과를 보장하는 알고리즘이 필요하다.

이번에 소개하는 알고리즘들이 바로 그러한 알고리즘들이다.

---

6. 힙 정렬(Heap Sort)

이번에 소개하는 '힙 정렬'은 힙을 이용한 정렬방식으로 앞서 힙을 제대로 공부했다면 별도로 공부할 것이 없는 알고리즘이다.

이는 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다.

"힙의 루트 노드에 저장된 값이 가장 커야 한다."

물론 이는 '최대 힙(max heap)'의 특징이다.

하지만 우리는 다음 특징을 갖도록 힙을 구성할 수도 있다.

"힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다."

그럼 이어서 코드를 보이겠다.

이 코드만 보아도 힙 정렬을 쉽게 이해할 수 있다.

#include <stdio.h>
#include "UsefulHeap.h"

int PriComp(int n1, int n2)
{
	return n2-n1;
//	return n1-n2;
}

void HeapSort(int arr[], int n, PriorityComp pc)
{
	Heap heap;
	int i;

	HeapInit(&heap, pc);

	// 정렬 대상을 가지고 힙을 구성한다.
	for(i=0; i<n; i++)
		HInsert(&heap, arr[i]);

	// 순서대로 하나씩 꺼내서 정렬을 완성한다.
	for(i=0; i<n; i++)
		arr[i] = HDelete(&heap);
}

int main(void)
{
	int arr[4] = {3, 4, 2, 1};
	int i;

	HeapSort(arr, sizeof(arr)/sizeof(int), PriComp);

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

보시다시피 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 것이 전부이다.

그럼에도 불구하고 정렬이 완료되는 이유는, 꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문이다.

지금까지 보였듯이 힙은 저장의 목적 이외에 정렬의 도구로도 사용이 될 수 있다.

그리고 그 성능은 예상과 달리 만족스러운 편이다.

언뜻 보면 저장된 데이터를 죄다 힙에 넣었다가 다시 꺼내기 때문에 성능상 이점이 별로 없어 보이지만, 힙 정렬은 지금까지 소개한 정렬들 중 가장 좋은 성능을 보이는 알고리즘이다.

앞서 힙의 데이터 저장 및 삭제의 시간 복잡도를 다음과 같이 계산한바 있다.

$O\left(\log n\right)$

따라서 삽입과 삭제를 하나의 연산으로 묶는다면, 이 연산에 대한 시간 복잡도는 다음과 같이 결론 내릴 수 있다.

$O\left(2\log n\right)$

하지만 숫자 2는 빅-오에서 무시할만한 수준이므로 삽입과 삭제를 하나의 연산으로 묶는다 해도, 이 연산에 대한 시간 복잡도는 여전히 다음과 같다.

$O\left(\log n\right)$

그럼 정렬과정에 대한 시간 복잡도는 어떻게 될까?

정렬대상의 수가 n개라면, 총 n개의 데이터를 삽입 및 삭제해야 하므로 위의 빅-오에 n을 곱해야 한다.

$O\left(n\log n\right)$

보기에 $nlogn$과 $n^2$에는 별 차이가 없다고 생각할지 모르겠지만 n에 몇몇 숫자만 넣어도 그 차이를 바로 알 수 있다.

위의 표에서 보이듯이, $nlogn$과 $n^2$에는 큰 차이가 있다.

참고로 말하자면 $O(n^2)$의 성능을 보이는 알고리즘을 $O(nlogn)$의 성능을 보이도록 개선한다면, 이는 낮은 성능으로 인하여 현실적으로 활용하기 어려운 알고리즘을 활용이 가능한 수준으로 개선한 결과로도 평가 받을 수 있다.

---

7. 병합 정렬(Merge Sort)

이번에 소개하는 병합 정렬은 '분할 정복(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다.

분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정복(conquer)'하는 방법이다.

단 분할해서 정복했으니 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다.

즉 다음 3단계를 거치도록 알고리즘을 디자인 하는 것이 분할 정복법이다.

- 1단계 분할(Divide): 해결이 용이한 단계까지 문제를 분할해 나간다.

- 2단계 정복(Conquer): 해결이 용이한 수준까지 분할된 문제를 해결한다.

- 3단계 결합(Combine): 분할해서 해결한 결과를 결합하여 마무리한다.

그럼 이 방법을 근거로 어떻게 병합 정렬 알고리즘이 디자인 되었을까?

기본 원리는 다음과 같다.

"8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고,

또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다."

그럼 그림을 통해서 병합 정렬의 과정 전체를 보자.

위 그림에서 보이듯이 우선은 분할의 과정을 거친다.

전체 데이터를 둘로 나누는 과정을, 데이터가 하나씩 구분이 될 때까지 진행을 한다.

그림에서는 총 8개의 데이터가 존재하므로 둘로 나누는 과정을 3회 진행하면 데이터가 하나씩 구분이 된다.

이렇듯 분할을 할 때에는 정렬을 고려하지 않고 그저 분할만 하면 된다.

분할이 완료되었다면 이제 병합을 진행할 차례이다.

위 그림에서 보이듯이, 우선 나뉘었던 둘을 하나로 묶는다.

8과 2가 원래 하나였으니, 이 둘을 하나로 묶는다.

단, 그냥 묶는 것이 아니라 정렬순서를 고려해서 묶는다.

그리고 그 다음 단계에서는 원래 한 덩이였던 2와 8, 그리고 3과 7을 정렬기준을 고려하여 하나로 묶는다.

이렇듯 분할이 총 3회 진행되었으니, 묶는 과정도 총 3회에 걸쳐 진행된다.

그리고 그 결과 정렬이 완료된다.

그럼 지금까지 설명한 병합 정렬과 관련해서 질문을 하나 하고자 한다.

이 질문은 이어지는 병합 정렬의 구현에 도움이 될 듯하여 데시하는 것이니, 다음 질문에 답을 해보자.

"분할의 과정에서 하나씩 구분이 될 때까지 둘로 나누는 과정을 반복하는 이유는 무엇인가?"

"처음부터 하나씩 구분을 해버리면 더 간단하지 않겠는가?"

답을 하였는가? '재귀적 구현을 위한 것'이라고 답을 했다면 정답이다!

그럼 병합 정렬의 코드를 소개하겠다.

#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid+1;
	int i;

	int * sortArr = (int*)malloc(sizeof(int)*(right+1));
	int sIdx = left;

	while(fIdx<=mid && rIdx<=right)
	{
		if(arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if(fIdx > mid)
	{
		for(i=rIdx; i<=right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for(i=fIdx; i<=mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for(i=left; i<=right; i++)
		arr[i] = sortArr[i];
	
	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if(left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left+right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid+1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

int main(void)
{
	int arr[7] = {3, 2, 4, 1, 7, 6, 5};
	int i;

	// 배열 arr의 전체 영역 정렬 
	MergeSort(arr, 0, sizeof(arr)/sizeof(int)-1);

	for(i=0; i<7; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

병합 정렬의 비교연산에 대한 빅-오는 다음과 같다.

$O\left(n\log n\right)$

참고로 병합 정렬에는 임시 메모리가 필요하다는 단점이 있다.

하지만 이는 정렬의 대상이 배열이 아닌 연결 리스트일 경우 단점이 되지 않기 때문에, 연결 리스트의 경우에는 병합 정렬에서 그만큼 더 좋은 성능을 기대할 수 있다.

---

8. 퀵 정렬(Quick Sort)

이번에 소개하는 퀵 정렬도 앞서 소개한 병합 정렬과 마찬가지로 '분할 정복(divide and conquer)'에 근거하여 만들어진 정렬 방법이다.

실제로 퀵 정렬 역시 정렬 대상을 반씩 줄여나가는 과정을 반복한다.

자! 그럼 이어서 몇몇 그림을 통해서 퀵 정렬의 기본 원리를 오름차순 정렬을 기준으로 설명하겠다.

참고로 퀵 정렬은 글보다 그림으로 이해하는 편이 낫다.

위 그림에서는 퀵 정렬의 대상이 되는 배열을 보이고 있다.

이 배열의 5개 지점에 이름을 부여하였다.

그리고 그 이름은 구현과정에서 실제로 사용할 이름이다.

그 중 left와 right가 의미하는 바는 각각 다음과 같다.

- left: 정렬대상의 가장 왼쪽 지점을 가리키는 이름

- right: 정렬대상의 가장 오른쪽 지점을 가리키는 이름

이어서 low와 high에 대해서 설명할 차례인데, 그에 앞서 '피벗(pivot)'에 대한 소개가 필요하다.

우선 피벗의 사전적 의미를 소개하겠다.

- pivot: 피벗이라 발음하고 중심점, 중심축의 의미를 담고 있다.

즉 피벗은 정렬을 진행하는데 필요한 일종의 '기준'이라 할 수 있다.

때문에 정렬의 진행을 위해서는 피벗이라는 것을 지정해야 한다.

피벗에 대해서는 일단 이 정도만 알고 있기로 하고 다시 위의 그림을 보자.

위의 그림에서는 가장 왼쪽에 위치한, 색이 칠해져 잇는 숫자 5를 피벗으로 정하고 있다.

물론 다른 데이터를 피벗으로 둘 수도 있는데, 이에 대한 논의는 퀵 정렬을 이해한 다음으로 미루겠다.

따라서 다음과 같이 단순한 결정을 하겠다.

"우리는 가장 왼쪽에 위치한 데이터를 퀵 정렬에 필요한 피벗으로 정한다."

다시 한번 말하지만 이는 우리의 결정일 뿐이다.

자 그럼 이어서 low와 high가 의미하는 바를 설명하겠다.

- low: 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름

- high: 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름

결과적으로 right과 high는 같은 위치를 가리킨다.

하지만 피벗을 가장 왼쪽 데이터가 아닌 가장 오른쪽 데이터로 결정한다면 이야기는 달라진다.

자! 이제 본격적으로 퀵 정렬의 과정을 보여야 하는데, 이때에는 low와 high가 중요한 역할을 한다.

위 그림에서 보이듯이 low는 오른쪽으로, high는 왼쪽으로 이동시킨다.

이때 이동의 기준은 다음과 같다.

- low의 오른쪽 방향 이동: 피벗보다 큰 값을 만날 때까지

- high의 왼쪽 방향 이동: 피벗보다 작은 값을 만날 때까지

물론 이는 오름차순 정렬의 경우를 대상으로 한 설명이다.

따라서 이를 일반화한다면 다음과 같이 정리해야 한다.

- low의 오른쪽 방향 이동: 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지

- high의 왼쪽 방향 이동: 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지

여기서 low와 high의 이동은 완전히 별개이다.

서로 사이 좋게 한 칸씩 왼쪽으로, 그리고 오른쪽으로 이동을 한다거나 할 필요가 없다.

그리하여 위 그림의 상황에서 low는 7이 저장된 위치에 머물고, high는 4가 저장된 위치에 머물게 된다.

이렇게 해서 low와 high는 각각 7과 4를 가리키게 되는데, 이때 이 둘이 가리키는 데이터를 서로 교환하여 다음의 상태가 된다.

지금 하는 일이 무슨 의미가 있는지 모르기 때문에 답답하겠지만 조금만 더 따라오자.

곧 결과를 알게 되니 말이다.

자! 7과 4의 교환 후에도 계속해서 low는 오른쪽으로, high는 왼쪽으로 이동한다.

마찬가지로 low는 피벗보다 큰 값(피벗보다 우선순위가 낮은)을 찾고, high는 피벗보다 작은 값(피벗보다 우선순위가 높은)을 찾는다.

따라서 low와 high는 각각 9와 2를 가리키게 되고, 이번에도 이 둘을 교환하여 다음 그림의 상태가 되게 한다.

교환 후에도 low는 피벗보다 큰 값을 찾을 때까지 오른쪽으로, high는 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동해 나간다.

그러면 결국에는 다음과 같이 low와 high가 가리키는 위치가 교차되는 상황이 발생한다.

이때는 low와 high가 가리키는 값을 교환하지 않는다.

이 상황은 low와 high의 이동 및 교환의 과정이 완료되었음을 의미하기 때문이다.

따라서 이번에는 다음 그림에서 보이듯이 피벗과 high가 가리키는 데이터를 서로 교환하여 다음 그림의 상태가 된다.

지금까지 설명한 내용이 퀵 정렬의 핵심연산이라 할 수 있다.

이를 제외하면 이어서 설명하는 과정은 병합 정렬과 유사하다 느낄 것이다.

"근데 뭘 했기에 이것이 퀵 정렬의 핵심연산이라 할 수 있는 건가요?"

아직 눈치채지 못했다면 피벗의 값과 그 위치를 눈 여겨보자.

피벗이였던 5가 정렬되었을 때의 제 위치를 찾지 않았는가!

피벗의 왼편에는 피벗보다 작은 값들이 위치하고, 피벗의 오른편에는 피벗보다 큰 값들이 위치하고 있으니 말이다.

이로써 피벗이었던 숫자 5는 홀로 정렬이 완성되었다.

그럼 병합 정렬을 경험해봤으니, 다음 단게가 다음과 같이 진행되어야 함을 짐작할 수 있을 것이다.

위 그림에서 보이듯이, 제자리를 찾은 5를 기준으로 왼쪽 영역과 오른쪽 영역을 대상으로 지금 설명한 과정을 반복하게 된다.

그러면 왼쪽 영역의 피벗인 2와 오른쪽 영역의 피벗인 9가 제 자리를 찾을 것이다.

그렇다면 이 과정은 언제까지 진행이 되어야 하겠는가?

left와 right가 각각 정렬대상의 시작과 끝을 의미하므로 다음 상황에 놓이게 될 때 더 이상 정렬할 대상이 없다는 의미가 된다.

left > right

이로써 퀵 정렬의 기본원리를 모두 설명하였으니, 퀵 정렬의 코드를 보이겠다.

#include <stdio.h>

void Swap(int arr[], int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}	


int Partition(int arr[], int left, int right)
{
	int pivot = arr[left];    // 피벗의 위치는 가장 왼쪽! 
	int low = left+1;
	int high = right;

	while(low <= high)    // 교차되지 않을 때까지 반복
	{	
		while(pivot > arr[low])
			low++;

		while(pivot < arr[high])
			high--;
		
		/*
		while(pivot >= arr[low] && low <= right)
			low++;

		while(pivot <= arr[high] && high >= (left+1))
			high--;
		*/

		if(low <= high)    // 교차되지 않은 상태라면 Swap 실행
			Swap(arr, low, high);    // low와 high가 가리키는 대상 교환
	}

	Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환
	return high;    // 옮겨진 피벗의 위치 정보 반환
}

void QuickSort(int arr[], int left, int right)
{
	if(left <= right)
	{
		int pivot = Partition(arr, left, right);    // 둘로 나눠서 
		QuickSort(arr, left, pivot-1);    // 왼쪽 영역을 정렬
		QuickSort(arr, pivot+1, right);    // 오른쪽 영역을 정렬
	}
}

int main(void)
{
//	int arr[7] = {3, 2, 4, 1, 7, 6, 5};
	int arr[3] = {3, 3, 3};

	int len = sizeof(arr) / sizeof(int);
	int i;

	QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);

	for(i=0; i<len; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

퀵 정렬에서의 빅-오는 다음과 같다.

$O\left(n\log n\right)$

하지만 퀵 정렬의 경우 약간의 예외를 두는데, 위의 시간 복잡도는 최악의 경우가 아닌 평균의 경우에 대한 빅-오이다.

늘 최선의 경우를 보이는 것은 아니지만 최선의 경우에 가까운 성능을 평균적으로 보이기 때문이다.

그래도 최악의 경우에 대한 빅-오를 계산해보면 $O(n^2)$이 나온다.

이는 앞서 for문을 중첩으로 하여 구현한 단순 정렬 알고리즘에서나 볼 수 있는 빅-오이다.

하지만 걱정하지 말자.

아무도 이 결과를 기준으로 퀵 정렬을 평가하지는 않으니 말이다.

실제로 퀵 정렬은 $O(nlogn)$의 복잡도를 갖는 다른 정렬 알고리즘과 비교했을 때에도 평균적으로 제일 빠른 것으로 알려져 있다.

데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 별도의 메모리 공간을 요구하지 않기 때문이다.