[알고리즘] 힙 / 병합 정렬 (Heap / Merge Sort)

힙(Heap)

완전 이진트리의 자료구조로 값의 최대 힙과 최소 힙의 유형을 가지고 있습니다.

삽입, 삭제의 시간복잡도는 O(log N)을 가지고 있습니다.

 

힙 정렬

주어진 데이터를 힙(Heap)을 사용하여 정렬하는 알고리즘입니다.

• 최대 힙(Max Heap) : 내림차순 정렬
• 최소 힙(Min Heap) : 오름차순 정렬

힙정렬 과정 - https://taaewoo.tistory.com/6

 

 

힙 정렬 과정

1. 리스트의 원소들을 모두 힙에 넣는다.

2. 힙의 루트 원소를 뽑아 정렬시킬 배열에 놓고 힙에서는 제거한다.

3. 2번의 과정을 재귀적으로 오름차순 또는 내림차순으로 정렬될때까지 반복한다.

 

특징 및 장단점

• 제자리 정렬 (In-Place Sorting) : 추가적인 메모리 공간을 필요로 하지 않으며, 주어진 배열에서 바로 정렬을 수행한다.
• 데이터를 비교하며 정렬을 수행한다.
• 최선,평균,최악의 시간 복잡도는 O(log n)으로 일정한 시간복잡도를 보장한다.
• 정렬하는 원소가 동일한 값일 경우, 순서를 보장하지 않는다.

 

힙정렬 구현

// Heap (완전 이진 트리 형태)
// 정렬할 배열 , 배열의 크기, 루트가 될 원소
void heapify(int arr[], int n, int i)
{
	int largest = i;
	int left = 2 * i + 1;
	int right = 2 * i + 2;

	// (right < n && arr[left] < arr[smallest]) -> 최소 힙
	if (left < n && arr[left] > arr[largest])
	{
		largest = left;
	}

	// (right < n && arr[right] < arr[smallest] -> 최소 힙
	if (right < n && arr[right] > arr[largest])
	{
		largest = right;
	}

	if (largest != i) {
		std::swap(arr[i], arr[largest]);
		heapify(arr, n, largest);
	}
}

// 힙정렬
void heapSort(int arr[], int n)
{
	for (int i = n/2 - 1; i >= 0; i--)
	{
		heapify(arr, n, i);
	}

	for (int i = n - 1; i > 0; i--)
	{
		std::swap(arr[0], arr[i]);
		heapify(arr, i, 0);
	}
}

 

HeapSort - 정렬 결과

 

 

---

 

병합 정렬 (Merge Sort)

• 리스트의 원소들을 재귀적으로 반으로 나누고, 각 부분들을 정렬한 후 병합(Merge) 과정을 통해 다시 합치는 방식
  • 분할정복 알고리즘
• 두 개의 정렬된 리스트를 합쳐서 하나의 정렬된 리스트로 만드는 과정

 

병합정렬 분할 / 정복 과정- https://anweh.tistory.com/85

 

 

특징 및 장단점

• 분할정복 알고리즘
• 동일한 값에대한 순서를 보장한다.
• 리스트를 분할하고 병합하는 단계에서 병렬 처리에 유용하다.
• 최선,최악,평균 시간복잡도 O(n lon n)을 유지한다.
• 정렬시 추가적인 메모리 공간이 O(n)만큼 필요하다.

 

병합정렬 구현

// 병합
void merge(std::vector<int>& arr, int left, int right)
{
	if (left >= right) return;

	int mid = left + (right - left) / 2;

	merge(arr, left, mid);
	merge(arr, mid + 1, right);

	// 병합 단계
	int n1 = mid - left + 1;	// 왼쪽 크기
	int n2 = right - mid;		// 오른쪽 크기

	// 임시배열. 공간복잡도 O(n)이 추가적으로 필요한 이유
	std::vector<int> leftArr(n1), rightArr(n2);

	// 값 복사
	for (int i = 0; i < n1; i++)
	{
		leftArr[i] = arr[left + i];
	}

	for (int i = 0; i < n2; i++)
	{
		rightArr[i] = arr[mid + 1 + i];
	}

	// 두 배열 병합
	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2)
	{
		if (leftArr[i] <= rightArr[j])
		{
			arr[k] = leftArr[i];
			i++;
		}
		else
		{
			arr[k] = rightArr[j];
			j++;
		}
		k++;
	}

	// 왼쪽 배열의 나머지 항목 복사
	while (i < n1) 
	{
		arr[k] = leftArr[i];
		i++;
		k++;
	}

	// 오른쪽 배열의 나머지 항목 복사
	while (j < n2)
	{
		arr[k] = rightArr[j];
		j++;
		k++;
	}
}

// 병합정렬 (분할)
void mergeSort(std::vector<int>& arr, int left, int right) {
	if (left < right)
	{
		int mid = left + (right - left) / 2;	// 중간값 계산

		mergeSort(arr, left, mid);				// 왼쪽 절반
		mergeSort(arr, mid + 1, right);			// 나머지 오른쪽 절반

		merge(arr, left, right);				// 마지막 병합
	}
}

MergeSort - 정렬 결과