04 정렬 (1)

선택 정렬 (Selection Sort)

selectionSort(A[n], n)
{
	for last ← n downto 2{
		A[1…n] 중 가장 큰 수 A[k]를 찾는다;
		A[k] ↔ A[last];
	}
}

선택 정렬의 수행 시간은 모든 경우에 $\Theta(n^2)$

 

버블 정렬 (Bubble Sort)

bubbleSort(A[], n)
{
	for last ← n downto 2
		for i ← 1 to last-1
			if (A[i] > A[i+1]) then A[i] ↔ A[i+1];
}

버블 정렬의 수행 시간은 $\Theta(n^2)$

 

중간에 정렬이 완료될 경우, 무의미한 순환을 멈추기 위한, 변형된 버블 정렬

bubbleSort2(A[], n)
{
	for last ← n downto 2{
		sorted ← TRUE;
		for i ← 1 to last-1{
			if (A[i] > A[i+1]) then {
				A[i] ↔ A[i+1];
				sorted ← FALSE;
			}
		}
		if (sorted == TRUE) then return;
	}
}

 

삽입 정렬 (Insertion Sort)

insertionSort(A[], n)
{
	for i ← 2 to n
		A[1…i]의 적합한 자리에 A[i]를 삽입한다;
}

최악의 경우에도 수행 시간은 $\Theta(n^2)$

 

선택 정렬, 버블 정렬, 삽입 정렬은 모두 수학적 귀납법으로 증명 가능

 

병합 정렬 (Merge Sort)

mergeSort(A[], p, r)
{
	if(p<r) then{
		q ← (p+r)/2;
		mergeSort(A, p, q);
		mergeSort(A, q+1, r);
		merge(A, p, q, r);
	}
}

merge(A[], p, q, r)
{
	정렬되어 있는 두 배열 A[p…q]와 A[q+1…r]을 합쳐
	정렬된 하나의 배열 A[p…r]을 만든다.
}

병합정렬에서 시간복잡도를 계산하면,

$$\begin{align}T(n)&\leq 2T(n/2)+cn\\ &\leq 2(2T(n/4) +c\cdot (n/2)) +cn = 2^2 T(n/2^2) + 2cn\\ &\leq 2^2 (2T(n/2^3) + c\cdot (n/2^2 ))+2cn = 2^3 T(n/2^3) +3cn\\ &\cdots \\&\leq 2^k T(n/2^k) +kcn\\ &= nT(1) + kcn = an+cnlogn\\ &= \Theta(nlogn)\end{align}$$

병합 정렬의 수행 시간은 최악의 경우 $\Theta(nlogn)$

 

퀵 정렬 (Quick Sort)

quickSort(A[], p, r)
{
	if (p<r) then{
		q ← partition(A, p, r);
		quickSort(A, p, q-1);
		quickSort(A, q+1, r);
	}
}

partition(A[], p, r)
{
	x ← A[r];
	i ← p-1;
	for j ← p to r-1
		if (A[j]≤x) then A[++i] ↔ A[j];
	A[i+1] ↔ A[r];
	return i+1;
}

평균적인 경우 시간복잡도는,

$$T(n)=2T(n/2) + \Theta(n)$$

$$\therefore T(n)=\Theta(nlogn)$$

최악의 경우 시간복잡도는,

$$T(n)=T(n-1)+\Theta(n)$$

$$\therefore T(n)=\Theta(n^2)$$