[알고리즘] 정렬 알고리즘 - 선택 정렬, 힙 정렬, 병합 정렬, 퀵 정렬

버블 정렬과 삽입 정렬에 대해서는 다음 글을 참고 바랍니다. 

 

[백준][알고리즘][C++] 2750 수 정렬하기, 버블 정렬, 삽입 정렬

 

---

1. 선택 정렬

 

선택 정렬은 시간 복잡도가 O(n^2)인 알고리즘입니다. 

 

이름에서 알 수 있듯이 선택 정렬은 정렬 대상 중에 가장 작은 값(가장 앞에 정렬되어야 하는 값)을 선택하여 배치하는 방법입니다. 

 

그런 방식으로 정렬하려면 메모리 공간이 추가적으로 더 필요하겠네? 라고 생각하실 수도 있지만, 데이터를 하나 옮기려고 할 때마다 빈 메모리가 생긴다는 점을 고려하면 굳이 메모리를 추가적으로 마련할 필요가 없습니다. 

 

 

즉, 선택정렬의 알고리즘을 말로 요약하자면, 정렬할 대상에서 가장 작은 요소와 현재 대상에서 가장 앞에 놓여있는 요소를 교환하는 것입니다.

3 4 2 1 와 같이 놓여있다면, 탐색을 통해 1을 '선택'하고 3과 교환, 그 후 나머지 정렬 대상인 4 2 3 중 탐색을 통해 2를 선택하고 4와 교환... 과 같은 과정을 거칩니다. 

 

코드로는 다음과 같습니다. 

 

#include <iostream>
#include <vector>

void SelSort(std::vector<int>& arr)
{
	int minIdx = 0;
	for (int i = 0; i < arr.size(); ++i)
	{
		int min = arr[i];
		for (int j = i + 1; j < arr.size(); ++j)
		{
			if (arr[j] < min) //최솟값 탐색
			{
				min = arr[j];
				minIdx = j;
			}

			//교환
			arr[minIdx] = arr[i];
			arr[i] = min;
		}
	}
}

 

 

---

2. 힙 정렬

 

힙 정렬은 이름에서 알 수 있듯이 힙을 사용하여 힙에 데이터를 모두 넣은 뒤 다시 꺼내는 방법입니다. 

 

힙은 데이터의 저장과 삭제가 각각 모두 log2(n)의 시간복잡도를 가지고 있으므로, 하나의 데이터를 저장 후 꺼내게 되면 2log2(n)의 시간복잡도가 됩니다.(상수곱은 무시할 수 있습니다.)

데이터가 총 n개이므로 따라서 n개의 데이터를 정렬하기 위해서는 nlog2(n)의 시간복잡도가 필요할 것입니다. 

 

 

C++에서 힙을 사용한 대표적인 자료구조로 우선순위 큐가 있으므로, 우선순위 큐를 통해 정렬을 해보면 다음과 같습니다. 

 

#include <iostream>
#include <queue>
#include <vector>

void HeapSort(std::vector<int>& arr)
{
	std::priority_queue<int, std::vector<int>, std::greater<int>> que;
	for (int i = 0; i < arr.size(); ++i)
	{
		que.push(arr[i]);
	}
	for (int i = 0; i < arr.size(); ++i)
	{
		arr[i] = que.top();
		que.pop();
	}
}

 

---

3. 병합 정렬

 

병합 정렬은 분할 정복을 사용한 알고리즘입니다. 

 

분할 정복이란 복잡한 문제를 하위 문제로 분할(divide)하여 정복(conquer)한 후, 하위 문제의 해결책을 다시 상위 문제로 결합(combine)하는 방법입니다. 

 

병합 정렬의 경우, 정렬해야할 대상을 잘게 쪼개는 것부터 출발합니다. 

하나만 남아 더이상 정렬할 대상이 없을 때까지 쪼개고 나면 이들을 다시 결합합니다. 

 

분할 정복의 특성이 그렇듯이, 병합 정렬은 재귀적인 형태를 띄고 있습니다. 

재귀적인 디자인이 용이하도록 다시 설명하자면, 병합 정렬은 정렬 대상을 절반으로 쪼갠 후 양쪽을 각각 정렬한 후 이들을 결합하는 식으로 정렬하는 방법입니다. 중요한 점은 쪼개진 양쪽을 정렬할 때 역시 같은 방법으로 정렬이 진행된다는 것입니다. 

 

코드로 옮기면 다음과 같습니다. 

 

#include <iostream>
#include <vector>

void MergeTwoArea(std::vector<int>& arr, int left, int mid, int right)
{
	int* tempMem = new int[right - left + 1];

	int idx1 = left;
	int idx2 = mid + 1;
	int memIdx = 0;

	while (idx1 <= mid && idx2 <= right)
	{
		if (arr[idx1] < arr[idx2])
			tempMem[memIdx++] = arr[idx1++];
		else
			tempMem[memIdx++] = arr[idx2++];
	}
	
	while (idx1 <= mid)
		tempMem[memIdx++] = arr[idx1++];
	while (idx2 <= right)
		tempMem[memIdx++] = arr[idx2++];

	memIdx = 0;
	for (int i = left; i <= right; ++i, ++memIdx)
	{
		arr[i] = tempMem[memIdx];
	}

	delete[] tempMem;
}

void MergeSort(std::vector<int>& arr, int left, int right)
{
	if (left >= right) return;

	int mid = (left + right) / 2;
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);

	MergeTwoArea(arr, left, mid, right);
}

 

병합 정렬의 경우 nlog2(n)의 시간복잡도를 가지고 있습니다. 

 

---

4. 퀵 정렬

 

퀵 정렬 역시 병합 정렬과 마찬가지로 분할 정복을 사용한 알고리즘입니다. 

또한 퀵 정렬은 평균적으로 다른 정렬 알고리즘보다 빠른 속도를 보입니다.

 

퀵 정렬은 pivot을 지정하고, 해당 pivot의 적절한 위치를 찾은 뒤 그 pivot을 기준으로 양쪽으로 나누어 같은 방식으로 계속해나가면서 정렬하는 방법입니다.

 

pivot의 위치를 찾기 위해 두가지의 변수를 정의합니다.

먼저 pivot을 제외하고 가장 왼쪽에 위치한 요소를 low, pivot을 제외하고 가장 오른쪽에 위치한 요소를 high라고 할 때, 

low와 high를 각각 증가시키고 감소시키며 low는 pivot보다 큰 요소를 찾고, high는 pivot보다 작은 요소를 찾습니다. 찾고 나면 두 값을 교환합니다. 

이를 low와 high가 서로 교차할 때까지 반복하고, 교차하게 되면 그때의 high의 위치가 pivot의 위치가 되며, high와 pivot의 값을 교환합니다. 

 

pivot은 어느 지점을 선택하든 상관 없으나, 중간값에 가까운 피봇을 선택하는 편이 평균적으로 더 좋은 성능을 보인다고 합니다.

 

아래의 코드는 제일 왼쪽의 요소를 pivot으로 지정하여 작성한 코드입니다.

 

#include <iostream>
#include <vector>

int Partition(std::vector<int>& arr, int left, int right)
{
	int pivot = arr[left];
	int low = left + 1;
	int high = right;

	while (low <= high)
	{
		while (low <= right && pivot >= arr[low])
			++low;
		while (high >= left + 1 && pivot <= arr[high])
			--high;

		if (low <= high)
		{
			int temp = arr[low];
			arr[low] = arr[high];
			arr[high] = temp;
		}
	}

	arr[left] = arr[high];
	arr[high] = pivot;

	return high;
}

void QuickSort(std::vector<int>& arr, int left, int right)
{
	if (left >= right) return;
	int pivot = Partition(arr, left, right);
	QuickSort(arr, left, pivot - 1);
	QuickSort(arr, pivot + 1, right);
}

 

퀵 정렬은 최악의 경우엔 O(n^2), 최선의 경우에는 O(nlog2(n))의 시간 복잡도를 보입니다. 

그러나 퀵 정렬은 평균적으로 최선의 경우와 가까운 성능을 보이므로 O(nlog2(n))의 시간복잡도를 갖는 알고리즘으로 평가합니다. 

 

 

---

추가적으로 stl에서 제공하는 정렬 함수로 sort가 있습니다. sort는 퀵 정렬 방식을 사용한 함수로, O(log2(n))의 시간복잡도를 가지고 있습니다. 

 

 

sort 함수의 경우 sort(begin, end)와 같이 인자를 넣어줄 수 있으며 begin<= arr <end 범위의 수들을 정렬해 줍니다. 

또한 함수를 세번째 인자로 전달해 정렬 기준을 설정할 수도 있습니다.