정렬 알고리즘 - 힙,병합,퀵 O(NlogN) - 10장

본문은 오름차순을 기준으로 정렬을 설명합니다.

힙 정렬

힙 정렬은 앞서 구현한 자료구조인 '힙(heap)' 자료구조를 이용한 정렬 알고리즘이다.

 

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

"힙의 루트 노드에 저장된 값이 가장 커야 한다." - 최대 힙의 특징.

 

즉 이 특성을 이용해 힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다.

앞서 힙을 제대로 공부했다면 바로 이해가 가능하니 코드를 통해 확인해본다.

 

template <typename T>
void Sort<T>::HeapSort(T* ptr, int len)
{
	Heap hp(Sort::PriComp);

	int i;
	for (i = 0; i < len; ++i)
		hp.Insert(ptr[i]);
	
	for (i = 0; i < len; ++i)
		ptr[i] = hp.Delete();
}

간단하게 데이터를 모두 힙에 집어넣고.

다시 빼오면 되는 구조.

 

힙 정렬의 성능 평가 : O(NlogN)

정확히는 2NlogN이다. 왜냐하면 데이터의 수를 N 개라고 하고, 하나의 데이터를 삽입/삭제하는 과정은 힙에서

logN의 시간복잡도를 가진다. 즉 N개의 데이터를 대상으로 삽입/삭제는 NlogN. 

삽입과 삭제의 연산을 두 번 하니 NlogN + NlogN = 2 NlogN;

 

하지만 숫자 2는 빅-오에서 무시하는 수이므로 성능은 O(NlogN)

 

NlogN의 성능 평가.

 

O(n)보다는 성능이 떨어지지만 n² 보다는 훨씬 좋은 성능을 보인다.

 

병합 정렬

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

 

분할 정복이란 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법. 정복한 후에는 결합의 과정을 거친다.

 

간단하게 풀어써보면

8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이를 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.

 

위 그림에서 보이듯이 우선은 분할의 과정을 거친다. 전체 데이터를 둘로 나누고, 데이터가 하나씩 구분이 될 때까지 진행을 한다.

 

그리고 나뉘었던 둘을 하나로 묶는다. 8과 2를 대상으로 정렬을 하면 2와 8 3과 7을 대상으로 정렬하면 3과 7.

 

재귀의 과정을 거치면 간단하므로 함수의 원형을 살펴본다.

void merge(int arr[], int left,int right)

 이때까지 소개한 알고리즘과는 달리 원형이 조금 다르다.

원래는 배열의 주소와 길이를 전달했다면 이 녀석은 배열의 길이와 int형 left와 right란 인자를 받는다.

이 left와 right는 정렬 대상이 배열의 전체라면 left에는 첫 번째 인덱스(0) right에는 배열의 마지막 인덱스(길이 - 1)

 

이런 이유는 병합 정렬이 계속해서 반으로 분할해나가는데 그 인덱스 길이 정보를 전달하기 위함이다.

 

병합 정렬의 구현에서 임시 배열이 필요한데 그 이유는 분할 대상의 요소들끼리 비교를 하고 요소를 옮기기 위함이다.

 

예를 들어 

출처 - 나동빈 알고리즘

67과 58이라는 분할된 녀석들을 대상으로 비교를 진행한다.

어떻게 진행하냐면 저 왼쪽 박스 67과 오른쪽 박스 58을 대상으로 현재 i와 j라는 변수가 인덱스를 통해 기억하고 있다.

그렇게 값을 비교하고 더 작은 녀석이 k 쪽으로 들어가게 되는 것.

 

실제로는 그림처럼 저렇게 박스가 구분이 되지 않기에 mid라는 변수를 통해서 서로의 박스를 구분해준다. ( / 2 )

저게 끝은 아니다.

 

정복의 과정을 잠깐 살펴보면

1. 6과 5를 비교해서 5가 들어간 뒤 j는 8을 가리킨다. ( 5 x x x )

2. 6과 8을 비교해서 6이 들어간다 i는 7을 가리킨다. ( 5 6 x x )

3. 7과 8을 비교해서 7이 들어간다. i는 범위(mid)를 벗어난다. ( 5 6 7 x ) (오른쪽의 끝은 right)

4. 둘 중 하나라도 범위를 벗어나면 남은 데이터는 k번째로 반복문을 통해 다 집어넣는다.

 

이제 코드를 보면서 확인해 본다.

(클래스에서 정의하다 보니 코드는 조금 변형되었습니다.)

template <typename T>
class Sort
{
public:
	
	static void BubbleSort(T* ptr, int len);
	static void SelectionSort(T* ptr, int len);
	static void InsertionSort(T* ptr, int len);
	static void HeapSort(T* ptr, int len);
	static void MergeSort(T* ptr, int left, int right, int size); // size매개변수는 tmpArrPtr제거를 위해.
private:
        static void MergeArrAssign(int left, int right);
        static T PriComp(T n1, T n2);
        static bool check;
        static T* tmpArrPtr; // 머지함수에서 쓰일 임시 배열
};

// static멤버는 개체간 존재하는것이 아닌 개체간 공유하는 단 하나의 멤버
bool Sort<T>::check = false;
T* Sort<T>:: tmpArrPtr = nullptr;

 

병합 정렬의 내부 구현 코드.

template <typename T>
void Sort<T>::MergeSort(T* ptr, int left, int right, int size)
{
	int sizeCheck = right - left; // sizeCheck값이 배열 길이 -1이라면 마지막 정복과정.
	Sort<T>::MergeArrAssign(left, right); // 임시 메모리 동적할당.
	Sort<T>::check = true; // 여러번 동적할당 못하게 막기위해 존재하는 static check변수.

	int mid; // 서로를 반으로 나누기 위한 인덱스 변수.
	int p1, p2, p3; // 각각 그림의 i,j,k

	if (left < right) // right가 left보다 작아지면 분할 종료.
	{
		mid = (left + right) / 2;
		MergeSort(ptr, left, mid, size); // 왼쪽부분 분할
		MergeSort(ptr, mid + 1, right, size); // 오른쪽 부분 분할

		// 재귀가 끝났다면 그 데이터를 대상으로 병합.
		p1 = left;
		p2 = mid + 1;
		p3 = left;
		while (p1 <= mid && p2 <= right) // 그림의 비교부분 + 임시배열에 요소 집어넣기.
		{
			if (ptr[p1] < ptr[p2])
				tmpArrPtr[p3++] = ptr[p1++];
			else tmpArrPtr[p3++] = ptr[p2++];
		}

		while (p1 <= mid) // 왼쪽박스가 남았다면
			tmpArrPtr[p3++] = ptr[p1++];
		while (p2 <= right) // 오른쪽박스가 남았다면
			tmpArrPtr[p3++] = ptr[p2++];

		for (int i = left; i <= right; ++i) // 임시배열에 있던것을 원래 배열로.
			ptr[i] = tmpArrPtr[i];

		if (sizeCheck == size - 1) // 정복이 끝났다면 해제.
		{
			Sort<T>::check = false;
			delete[] tmpArrPtr;
		}
	}

	
}

 

병합 정렬의 성능 평가 : O(NlogN)

 

분할의 과정을 제외하고, 정복의 과정을 보면 

 

정렬의 대상인 데이터의 수가 n개 일 때, 각 병합의 단계마다 최대 n번의 비교 연산이 진행된다.

그리고 n개의 데이터에서 n개를 8개로 가정해보면. 정복의 과정에서

3단계밖에 거치지 않는다. (logN)

 

마찬가지로 데이터의 수가 16개 일 때 병합의 과정은 4회가 진행이 된다.

 

그렇기에 각 단계마다 n번의 비교 연산 * 병합 단계의 시간 복잡도. 빅-오를 구하면 O(NlogN)이 되는 것.

 

퀵 정렬

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

퀵 정렬에서는 피벗(pivot)이라는 개념이 추가가 되는데 그림을 통해 확인해본다.

 

퀵 정렬의 정렬방법은 다음과 같다.

left와 right는 그림의 설명을.

 

피벗은 정렬을 위한 일종의 '기준'이다.

위 그림에서는 맨 왼쪽에 위치한 5를 피벗으로 잡고있다. (다른 수로도 피벗잡기 가능)

 

이제 또 중요한 low와 high의 역할.

위 그림에서 보듯이 low는 오른쪽으로 이동하고 high는 왼쪽으로 이동한다.

 

이동 기준은 이렇다.

 

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

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

 

즉 low와 high는 딱히 같이 움직인다는 개념이라기 보단 요소와 피벗을 비교해가면서 서로가 오른쪽,왼쪽으로 이동한다.

위 그림의 상황에선 피벗보다 큰 값을 만나는 경우는 7. 작은 값을 만나는 경우는 4.

 

이 때 low와 high가 멈춰서게 될 경우 서로의 요소의 값을 교환한다.

1. 5 1 3 4 9 2 7 6 8 -> 첫번째 정렬이 완료되었다.

교환 이후에도 계속해서 low는 오른쪽으로 high는 왼쪽으로 이동한다.

마찬가지로 9를 바로 만나고 2를 바로 만나 서로 교환.

 

그리고 다시 움직여보면 high와 low가 서로 역전된 상황. 이 경우에는 교환을 하지 않고

high의 값과 pivot의 값을 서로 교환한다.

그럼

 

위와 같이 5의 왼쪽자리와 오른쪽자리는 정렬이 이미 완료된 상태가 되었다.

(5를 기준으로 왼쪽은 작은 수, 오른쪽은 큰 수)

이제 기존의 피벗. 즉 high와 교환이 된 pivot은 그 자리에 머물게 되며 더 이상 어떠한 일도 하지않는다.

그리고 이제 다시 두 개의 영역으로 나누어 반복실행한다.

 

이 과정이 퀵 정렬의 핵심연산.

 

코드를 통해 확인해본다.

template <typename T>
class Sort
{
public:
	static void QuickSort(T* ptr, int left, int right); // 추가
	static void BubbleSort(T* ptr, int len);
	static void SelectionSort(T* ptr, int len);
	static void InsertionSort(T* ptr, int len);
	static void HeapSort(T* ptr, int len);
	static void MergeSort(T* ptr, int left, int right, int size);
private:
	static bool check;
	static T* tmpArrPtr;
	static T PriComp(T n1, T n2);
	static void MergeArrAssign(int left, int right);
	static T Partition(T* ptr, int left, int right); // 추가
	static void Swap(T* ptr, int idx1, int idx2); // 추가
	
};

 

QuickSort메소드에서 Partition,Swap 메소드를 활용한다.

 

먼저 Partition 코드.

template <typename T>
T Sort<T>::Partition(T* ptr, int left, int right)
{
	int pivot = ptr[left]; // 맨 왼쪽을 피벗으로.
	int low = left + 1;
	int high = right;

	while (low <= high) // 역전되지 않을때까지 반복.
	{
		while (pivot >= ptr[low] && low <= right) // 큰 값 만날때까지.
			++low;

		while (pivot <= ptr[high] && high >= (left + 1)) // 작은 값 만날때까지.
			--high;

		if(low <= high)
			Swap(ptr, low, high); // 인덱스를 넘기고 스왑.
	}

	// 빠져나오면 low와 high가 역전된 상황.
	Swap(ptr, left, high); // left는 피벗의 인덱스.
	return high; // high가 가리키는 곳은 이제 피벗이므로.
}

설명을 시작하기전 

while (pivot >= ptr[low] && low <= right) // 큰 값 만날때까지.
	++low;

while (pivot <= ptr[high] && high >= (left + 1)) // 작은 값 만날때까지.
	--high;

이 부분에서 왜 같은녀석까지 while문의 참조건에 포함하였으며 low <= right, high >= left + 1이란 조건이 있느냐.

우선 <=, >=의 조건으로 한 이유는 예로들어 요소의 수가 모두 같은 배열

ex) int arr[] = {3,3,3} 이 경우에는 pivot > ptr[low], pivot < ptr[high]에서 항상 거짓이 나오게 된다.

즉 low <= high의 바깥 while문의 조건은 무한루프에 빠져버리게 되는 것.

 

하지만 <=와 >=를 추가할 경우 low와 high가 가리키는 인덱스의 값이 배열의 정렬 범위를 넘어서는 문제가 발생가능하다. 그렇기에 경계검사를 추가해준 것. ( left + 1은 우리가 left를 피벗으로 정했기에 제외한 것)

 

돌아와서,

우리는 맨 왼쪽을 피벗으로 정했기에 left는 맨 왼쪽을 의미하면서 피벗을 가리키는 인덱스를 의미한다.

 

low와 high변수의 값을 초기화 해주고 low와 high가 역전되지 않을때까지 while 반복문.

반복문이 종료되었다면 low와 high는 역전되었으므로 피벗의 자리와 high의 자리를 교체해준다.

 

그리고 high의 값을 반환해주는데 그 이유는 high는 이제 맨 왼쪽의 피벗이 high의 자리와 교체되었으므로 

high를 리턴해주는 것.

 

그것을 받는 녀석은 QuickSort메소드.

template <typename T>
void Sort<T>::QuickSort(T* ptr, int left, int right)
{
	if (left <= right)
	{
		int pivot = Partition(ptr, left, right); // 나누기(분할).
		QuickSort(ptr, left, pivot - 1); // 왼쪽 영역
		QuickSort(ptr, pivot + 1, right); // 오른쪽 영역
	}
}

바로 분할을 위해서다.

 

설명의 그림에서 맨 왼쪽의 피벗이 5였고 역전된 high는 2를 가리켰다. 서로가 자리를 바꾸면서,

그 피벗은 자기를 기준으로 왼쪽,오른쪽은 정렬이 되었기때문에 그 두영역(왼쪽,오른쪽)을 분할하여 다시 정렬을 진행.

 

 

 

퀵 정렬의 성능평가 : O(NlogN) 하지만 정말 배드 케이스의 경우 O(N²)

 

퀵 정렬의 피벗 선택은 사실 가장 왼쪽의 값보다는 중간에 해당하는 값을 피벗으로 결정할 때 좋은 성능을 보인다.

 

그 이유는 피벗이 중간에 해당하는 값일 경우, 정렬대상은 균등하게 나뉘기 때문.

퀵 정렬은 중간 값이 적절히 선택된 피벗의 정렬일 경우에 병합정렬과 같이 NlogN의 성능을 보인다.

 

데이터의 수(N)만큼 반으로 나뉜 상태에서 각각 low와 high가 오른쪽/왼쪽으로 이동하면서 비교연산을 하는데

비교연산의 횟수는 데이터의 수에 해당하는 N.

 

그리고 pivot을 중심으로 좌/우로 나뉜 영역이 반복해서 나눠지고 정렬이 되는 구조이기떄문에 logN.

예를들어 31개의 데이터라면

31개의 데이터는 15개의 데이터로 나누어 정렬 - 1

15개의 데이터는 7개의 데이터로 나누어 정렬  - 2

7개의 데이터는 3개의 데이터로 나누어 정렬 - 3

3개의 데이터는 1개의 데이터로 나누어 정렬 - 4.

 

총 4번을 진행.