정렬 알고리즘 2

1) 합병 정렬 (Merge sort)

분할 정복(devide and conquer) 방식으로 설계된 알고리즘이다. 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다. a[i]와 a[j]값을 비교하여 더 작은 값을 새 배열에 저장하고 인덱스를 한 칸 옮긴다. 그리고 선택되지 못한 값들을 마지막에 순서대로 새 배열에 저장하고 그 배열을 원래 배열에 할당한다.

공간 복잡도

• O(n)

시간 복잡도

• 최선의 경우 : O(nlogn)
• 평균의 경우 : O(nlogn)
• 최악의 경우 : O(nlogn)

2) 퀵 정렬 (Quick sort)

마찬가지로 분할 정복을 이용하는 알고리즘이다. pivot point를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기며 진행한다. 이를 반복하여 분할된 배열의 크기가 1이면 종료한다.

공간 복잡도

• O(logn)

시간 복잡도

• 최선의 경우 : O(nlogn)
• 평균의 경우 : O(nlogn)
• 최악의 경우 : O(n²)

- 코드

#include <iostream>

using namespace std;

int a[10] = { 9, 5, 3, 4, 6, 7, 1, 10, 2, 8 };
int b[10];

void Merge(int left, int right)
{
	int i, j, k, mid, t;
	mid = (left + right) / 2;
	i = left;
	j = mid + 1;
	k = left;
	while (i <= mid && j <= right)
	{
		if (a[i] <= a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}
	t = i > mid ? j:i;
	while (k <= right)
	{
		b[k++] = a[t++];
	}
	for (int i = left; i <= right; i++)
	{
		a[i] = b[i];
	}
}

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

void Quick_sort(int left, int right)
{
	int pivot, i, j, tmp;
	if (left >= right)
		return;
	pivot = left;
	i = pivot + 1;
	j = right;
	while (i <= j)
	{
		while (i <= right && a[i] <= a[pivot])
		{
			i++;
		}
		while (j > left && a[j] >= a[pivot])
		{
			j--;
		}
		if (i > j)
		{
			tmp = a[j];
			a[j] = a[pivot];
			a[pivot] = tmp;
		}
		else
		{
			tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
		}
	}
	Quick_sort(left, j - 1);
	Quick_sort(j + 1, right);
}

int main(void)
{
	
	Merge_sort(0, 10 - 1);
	//Quick_sort(0, 10 - 1);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}