정렬 알고리즘(퀵, 병합)

오늘은 정렬 알고리즘 중에 퀵, 병합 정렬에 대해 알아보도록 하겠습니다.

---

1. 개요

저번 포스팅에서는 버블, 삽입, 선택 정렬에 대해 알아보았다면 요번에는 퀵, 병합, 힙 정렬에 대해 알아봅시다.

버블, 삽입, 선택은 시간 복잡도가 그렇게 좋진않았지만 단순한 알고리즘이였습니다.

그에 반대로 퀵, 병합, 힙은 시간복잡도가 좋지만 복잡한 알고리즘입니다.

 

 

---

2. 퀵 정렬(Bubble Sort)

퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬하는 방식입니다.

 

여기서 분할 정복 이란?

분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 입니다.

 

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한, 합병 정렬과 달리 퀵 정렬은 비균등하게 분할한다.

 

퀵 정렬의 과정은 다음과 같습니다.

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
4. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

퀵 정렬은 다음의 단계들로 이루어진다.

- 정복

부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

void QuickSort(int *a,int left, int right)
{
	if (left >= right)
		return;
	int pivot = partition(a,left, right);
	QuickSort(a,left, pivot - 1);
	QuickSort(a,pivot + 1, right);
}

-분할

입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)로 분할한다.

int partition(int *a,int left, int right)
{
	int pivot = a[right];
	int pivot_index = right;

	right--;

	while(1)
	{
		while (a[left] < pivot)
			left++;
		while (a[right] > pivot)
			right--;

		if (left >= right)
			break;
		else
		{
			swap(a[left], a[right]);
			left++;
		}
	}
	swap(a[left], a[pivot_index]);

	return left;
}

출처 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

 

시간 복잡도

퀵 정렬에 경우 최선 평균 모두 O(NlogN)이라는 시간 복잡도가 나온다.

출처 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

하지만 최악인 경우에는 O(N^2)가 나오는데 그 이유는 배열이 이미 오름차순 정렬되여있거나 내림차순으로 되어있는경우이다. 그래서 트리가 한쪽으로 치우처져있기 때문이다.

출처 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

출처 : https://hongjw1938.tistory.com/192

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

 

단점

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.\

평균적으로 정렬 알고리즘 중에서 정렬된 배열만 아니면 최고의 빠름을 보여준다.

 

---

3. 병합 정렬

보통 합병 정렬이라고 부르며, 분할 정복 방법을 통해 구현합니다.

빠른 정렬로 분류되며 퀵소트와 함께 많이 언급되는 정렬 방식입니다.

퀵소트와는 반대로 안정 정렬에 속합니다.

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사

 

-정복

void MergeSort(int *arr, int left, int right)
{
	if(left<right)
	{
		int mid = (left + right) / 2;
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		Merge(arr, left, right);
	}

정렬 로직에 있어서 Merge() 함수가 핵심이다.

퀵소트와의 차이점은

 

퀵정렬 : 우선 피벗을 통해 정렬(partition) -> 영역을 쪼갬(quicksort)

합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergesort) -> 정렬(merge)

 

또한, 이러한 경우로 인해 

 

-분할

int arr2[6];
void Merge(int* arr, int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while(i<=mid&&j<=right)
	{
		if(arr[i]<=arr[j])
		{
			arr2[k++] = arr[i++];
		}
		else
		{
			arr2[k++] = arr[j++];
		}
	}
	int tmp = i > mid ? j : i;
	while (k <= right)
		arr2[k++] = arr[tmp++];

	for (int i = left; i <= right; i++)
		arr[i] = arr2[i];
}

이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할수가 있다.

 

합병정렬은 순차적인 비교에 정렬을 진행하므로 연결리스트의 정렬이 필요할 때 사용하면 효율적이다.

퀵정렬은 연결리스트 정렬에 좋지않은데 이유는 순차접근이 아닌 임의 접근이기때문

 

시간복잡도

평균 최선 최악 모두 O(NlogN)이 나온다. 하지만 상황만 좋다면 퀵정렬보다 느리다

 

출처 : https://hongjw1938.tistory.com/192

 

장점

• 안정 정렬(stable Sort) 이다.

 

단점

• 지역 참조를 많이 하므로 최선의 퀵정렬 보다는 느리다
• 다른 메모리 공간이 필요하므로 메모리 공간을 잡아먹는다..

평균적으로 정렬 알고리즘 중에서 정렬된 배열만 아니면 최고의 빠름을 보여준다.

 

---

4. 요약

종류	시간복잡도	안정 vs 불안정
버블	전부 O(N^2)	안정
삽입	전부 O(N^2)	불안정
선택	최악, 평균 O(N^2) 최선 O(N)	안정
퀵	최악 O(N^2), 평균 최선 O(NlogN)	불안정
병합	전부 O(NlogN)	안정

 

---

5. Ref

https://gyoogle.dev/blog/

👨🏻‍💻 Tech Interview

https://hongjw1938.tistory.com/192

알고리즘 - Quick(퀵) vs Merge(병합) 정렬(+TCO, 참조 지역성)