[C++ algorithm] 각종 정렬에 대해

버블 정렬

버블 정렬은 앞에서부터 2개씩 짝을 지어 두개의 값을 비교해 순서를 바꾼다. 한 사이클이 끝나면 맨 뒤의 가장 큰 값이 배치하는 것을 보장할 수 있다. 따라서, 다음 사이클에 2번째의 값을 찾아내고 이 사이클을 계속하면 순서가 정렬이 될 것이다. 효율성은 거의 최악에 가깝다.

void BubbleSort(vector<int>& v)
{
	const int n = (int)v.size();
	for (int i = 0; i < n-1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (v[j] > v[j + 1])
			{
				swap(v[j], v[j + 1]);
			}
		}
	}
}

int main()
{
	vector<int> v{1, 5, 3, 4, 2};

	BubbleSort(v);
}

시간복잡도를 보면 N-1 + N-2 + N-3.... 2 + 1 까지 연산을 하기에 등차수열의 합으로 N^2임을 알 수 있다.

O(N^2)은 현실에서 쓰기 매우 어려운 효율성을 가진다.

선택 정렬

선택 정렬은 가장 작은 값을 가진 인덱스를 찾아 저장했다가 지금 가리키는 인덱스의 값이랑 위치를 바꾸는 정렬이다.

void SelectionSort(vector<int>& v)
{
	const int n = (int)v.size();
	for (int i = 0; i < n-1; i++)
	{
		int bestIdx = i;

		for (int j = i + 1; j < n; j++)
		{
			if (v[j] < v[bestIdx])
			{
				bestIdx = j;
			}
		}
		swap(v[i], v[bestIdx]);
	}
}

시간복잡도는 결국엔 버블정렬과 동일한 O(N^2)이다. 물론 버블정렬보단 그나마 조금 더 빠르게 동작할 것이다.

삽입 정렬

선택 정렬과 비슷하지만 실시간으로 정렬된 데이터를 만들어 나가는 것이다. 원래 있던 데이터에서 값을 순차적으로 추출해서 값을 정렬되게 새로운 컨테이너에 넣는 것이다. 물론 실제 배열을 새로 만드는 것은 아니다. 데이터의 영역을 구분해서 작업을 하는 것이다.

void InsertionSort(vector<int>& v)
{
	const int n = (int)v.size();
	for (int i = 1; i < n; i++)
	{
		int insertData = v[i];

		int j;
		for (j = i - 1; j >= 0 ; j--)
		{
			if (v[j] > insertData)
			{
				v[j + 1] = v[j];
			}
			else
			{
				break;
			}
		}
		v[j + 1] = insertData;
	}
}

역시 시간복잡도가 O(N^2)이다. 그래도 위에랑 다르게 만약 데이터가 어느정도 정렬이 되어있다면 조금 더 효율적일 것이다.

힙 정렬

우리가 이전에 우선순위 큐를 다루면서 힙에 대해 알아봤다. 그것과 동일한 방식으로 힙의 특성을 이용해서 정렬하는 것이다.

void HeapSort(vector<int>& v)
{
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int num : v)
		pq.push(num);
	v.clear();

	while (pq.empty() == false)
	{
		v.push_back(pq.top());
		pq.pop();
	}
}

시간 복잡도는 O(NlogN)이다. 위의 N^2에 비해 훨씬 현실성이 있는 효율적인 방식이다.

병합 정렬

병합 정렬은 조금 어려운 개념이다. 그 이유는 분할 정복(Divide and Conquer)를 하기 때문이다.

• 분할 : 문제를 더 단순하게 분할한다.
• 정복 : 분할된 문제를 해결
• 결합 : 결과를 취합하여 마무리

병합 정렬은 데이터를 쪼개서 그 데이터들을 각각 정렬하게 된다. 그리고 정렬된 데이터들로 부터 값을 가져와서 결합하는  것이다. 재귀적으로 진행한다.

void MergeResult(vector<int>& v, int left, int right, int mid)
{
	int leftIdx = left;
	int rightIdx = mid + 1;

	vector<int> temp;
	while (leftIdx <= mid && rightIdx <= right)
	{
		if (v[leftIdx] <= v[rightIdx])
		{
			temp.push_back(v[leftIdx]);
			leftIdx++;
		}
		else
		{
			temp.push_back(v[rightIdx]);
			rightIdx++;
		}
	}

	if (leftIdx > mid)
	{
		while (rightIdx <= right)
		{
			temp.push_back(v[rightIdx]);
			rightIdx++;
		}
	}
	else 
	{
		while (leftIdx <= mid)
		{
			temp.push_back(v[leftIdx]);
			leftIdx++;
		}
	}

	for (int i = 0; i < temp.size(); i++)
	{
		v[left + i] = temp[i];
	}
}

void MergeSort(vector<int>& v,int left, int right)
{
	// 더이상 데이터가 없거나 하나만 있는 경우
	if (left >= right)
		return;

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

	MergeResult(v, left, right, mid);
}

시간복잡도는 O(NlogN)인 것을 알 수 있다.

퀵 정렬

병합 정렬과 같이 데이터를 나눠서 보는 관점은 같지만 처음부터 반으로 나누는 것이 아니다. 처음에 특정 알고리즘을 통해 적용한 후에 반으로 나누어 진행한다. pivot을 첫번째로, low를 두번째, 마지막은 high로 지정한다. 그리고 low는 증가 high를 감소하며 비교한다.

1)

pivot >= arr[low]일동안 low를 오른쪽으로 이동

pivot <= arr[high]일 동안 high를 왼쪽으로 이동

2)

low < high라면 arr[low] 와 arr[high]의 데이터를 교체

 

1, 2를반복한다. 

3)

high <= low 반복을 멈추고 pivot과 arr[high]를 교체한다 

 

4)

그리고 자리를 찾은 숫자를 제외하고 나머지 부분을 재귀적으로 처리한다.

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

	while (low <= high)
	{
		while (low <= right && pivot >= v[low])
			low++;

		while (high >= left + 1 && pivot <= v[high])
			high--;
		if (low < high)
			swap(v[low], v[high]);
	}

	swap(v[left], v[high]);
	return high;
}

void QuickSort(vector<int>& v, int left, int right)
{
	if (left > right)
		return;

	int pivot = Partition(v, left, right);
	QuickSort(v, left, pivot - 1);
	QuickSort(v, pivot + 1, right);
}

Quicksort는 최악의 경우 N^2의 시간복잡도를 가진다. 하지만 평균적으로 NlogN의 시간복잡도를 가진다.