Sorting Problem - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:25:05Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:25 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]

Pinkgo: /* Linear Sorting Approach */

2025-10-02T01:57:57Z

Linear Sorting Approach

← 이전 판		2025년 10월 2일 (목) 01:57 판
270번째 줄:		270번째 줄:
	==Linear Sorting Approach==		==Linear Sorting Approach==
	위에서 다룬 알고리즘들은 비교 기반 정렬(comparison-based sorting)으로, 시간 복잡도는 아무리 효율이 좋은 알고리즘이더라도 O(n log(n))에 그친다. 이는 우연이 아니라 비교 기반 정렬의 근본적인 한계에서 기인한 문제이다.		위에서 다룬 알고리즘들은 비교 기반 정렬(comparison-based sorting)으로, 시간 복잡도는 아무리 효율이 좋은 알고리즘이더라도 O(n log(n))에 그친다. 이는 우연이 아니라 비교 기반 정렬의 근본적인 한계에서 기인한 문제이다.
			[[파일:Figure 6. Decision Tree .png\|섬네일\|300x300픽셀\|Figure 6. Decision Tree ]]
	Figure 6는 3개의 원소 a1, a2, a3를 정렬하는 과정을 결정 트리로 표현한 것이다. 결정 트리(Decision Tree)는 특정 기준(질문)에 따라 데이터를 구분하는 자료 구조로, 보통 이진 트리로 표현된다. 해당 figure에서는 루트 노드에서 "<math>a1 < a2</math>?"를 물어보고, 그에 따라 왼쪽/오른쪽으로 분기한다. 그 이후로도 "<math>a2 < a3</math>?", "<math>a1 < a3</math>?" 같은 비교를 통해 리프에 도달하며, 리프 노드에는 <math>(1,2,3), (1,3,2), (2,1,3)</math>과 같은 최종 정렬된 순열이 기록된다. 이때 중요한 것은 이 결정 트리의 높이(height)가 바로 최악의 경우 비교 횟수, 즉 정렬의 최악 시간 복잡도라는 것이다. 이를 통해 비교 기반 정렬의 최선의 시간 복잡도가 O(n log(n))이라는 것을 증명할 수 있다:		Figure 6는 3개의 원소 a1, a2, a3를 정렬하는 과정을 결정 트리로 표현한 것이다. 결정 트리(Decision Tree)는 특정 기준(질문)에 따라 데이터를 구분하는 자료 구조로, 보통 이진 트리로 표현된다. 해당 figure에서는 루트 노드에서 "<math>a1 < a2</math>?"를 물어보고, 그에 따라 왼쪽/오른쪽으로 분기한다. 그 이후로도 "<math>a2 < a3</math>?", "<math>a1 < a3</math>?" 같은 비교를 통해 리프에 도달하며, 리프 노드에는 <math>(1,2,3), (1,3,2), (2,1,3)</math>과 같은 최종 정렬된 순열이 기록된다. 이때 중요한 것은 이 결정 트리의 높이(height)가 바로 최악의 경우 비교 횟수, 즉 정렬의 최악 시간 복잡도라는 것이다. 이를 통해 비교 기반 정렬의 최선의 시간 복잡도가 O(n log(n))이라는 것을 증명할 수 있다:
	# n개의 정렬할 원소가 존재한다면, 서로 다른 n!개의 순열이 만들어질 수 있다.		# n개의 정렬할 원소가 존재한다면, 서로 다른 n!개의 순열이 만들어질 수 있다.
	# 결정 트리의 리프 수도 최소한 n!개가 필요하다.		# 결정 트리의 리프 수도 최소한 n!개가 필요하다.
	# 높이가 h인 이진 트리의 리프 수는 최대 2<sup>h</sup>이므로, <math>n! \le 2^h \rightarrow h \ge log(n!)</math>		# 높이가 h인 이진 트리의 리프 수는 최대 2<sup>h</sup>이므로, <math>n! \le 2^h \rightarrow h \ge log(n!)</math>

Pinkgo: /* Bucketsort */

2025-10-02T01:56:36Z

Bucketsort

@@ 268번째 줄: / 268번째 줄: @@
 다만, 어떤 방법을 써도 최악의 경우는 여전히 O(n<sup>2</sup>)이지만, 발생 확률이 매우 낮아진다.
-==Bucketsort==
+==Linear Sorting Approach==
 위에서 다룬 알고리즘들은 비교 기반 정렬(comparison-based sorting)으로, 시간 복잡도는 아무리 효율이 좋은 알고리즘이더라도 O(n log(n))에 그친다. 이는 우연이 아니라 비교 기반 정렬의 근본적인 한계에서 기인한 문제이다.
@@ 278번째 줄: / 278번째 줄: @@
 # 근사식을 사용하면, <math>log(n!) \approx \theta(n\,log(n))</math>
 # 따라서, 시간 복잡도는 <math>\Omega(log(n!)) \approx \Omega(n\,log(n))</math>이다.
 ==각주==

Pinkgo: /* Improving Quicksort */

2025-10-02T00:56:59Z

Improving Quicksort

@@ 267번째 줄: / 267번째 줄: @@
 # Median-of-Three: 첫 번째, 마지막, 중간 원소 중 중간값을 pivot으로 선택한다.<ref>평균(mean)이 아니라 중앙값(median)을 쓰는 이유는 극단값에 덜 민감하기 때문이다.</ref>
 다만, 어떤 방법을 써도 최악의 경우는 여전히 O(n<sup>2</sup>)이지만, 발생 확률이 매우 낮아진다.
 ==각주==

Pinkgo: /* Time Complexity Analysis */

2025-09-22T04:40:23Z

Time Complexity Analysis

← 이전 판		2025년 9월 22일 (월) 04:40 판
171번째 줄:		171번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	[[파일:Figure 3. Mergesort Time Complexity.png\|섬네일~~\|300x300픽셀~~\|Figure 3. ~~Merge Sort~~ Time Complexity]]		[[파일:Figure 3. Mergesort Time Complexity.png.png\|섬네일\|Figure 3. Mergesort Time Complexity.png]]
	앞서 설명했듯이, 각 단계에서 합병(merge) 과정은 O(n) 시간이 걸린다. 이때 분할 작업은 주어진 배열을 log<sub>2</sub>(n) 단계로 나누기 때문에 전체 시간 복잡도는 O(n log(n))의 시간복잡도이다. 이는 figure 3를 참고하여 더욱 쉽게 이해할 수 있다.		앞서 설명했듯이, 각 단계에서 합병(merge) 과정은 O(n) 시간이 걸린다. 이때 분할 작업은 주어진 배열을 log<sub>2</sub>(n) 단계로 나누기 때문에 전체 시간 복잡도는 O(n log(n))의 시간복잡도이다. 이는 figure 3를 참고하여 더욱 쉽게 이해할 수 있다.

244번째 줄:		244번째 줄:

	===Time Complexity Analysis===		===Time Complexity Analysis===
			[[파일:Figure 4. Best Case for Quicksort.png\|섬네일\|300x300픽셀\|Figure 4. Best Case for Quicksort]]
	Quicksort는 입력으로 받아들인 배열에 따라 그 시간 복잡도가 달라진다. 예를 들어, quicksort에 대한 최상의 경우는 pivot이 배열을 항상 정확히 절반으로 나눌 때이다. 이는 figure 4에 나타나 있다. 각 단계에서 배열이 2등분되면, 각 단계에서 partition의 비용이 O(n)이고, 분할 깊이는 log<sub>2</sub>n이므로 최종 시간 복잡도는 O(n log(n))이다.		Quicksort는 입력으로 받아들인 배열에 따라 그 시간 복잡도가 달라진다. 예를 들어, quicksort에 대한 최상의 경우는 pivot이 배열을 항상 정확히 절반으로 나눌 때이다. 이는 figure 4에 나타나 있다. 각 단계에서 배열이 2등분되면, 각 단계에서 partition의 비용이 O(n)이고, 분할 깊이는 log<sub>2</sub>n이므로 최종 시간 복잡도는 O(n log(n))이다.
			[[파일:Figure 5. Worst Case for Quicksort.png\|섬네일\|Figure 5. Worst Case for Quicksort]]
	반면, quicksort에서 최악의 경우는 pivot이 배열을 극단적으로 한쪽으로만 쏠리게 분할할 때이다. 예를 들면, pivot이 항상 최댓값/최솟값으로 선택되는 경우이다. 분할 깊이는 n이므로 최종 시간 복잡도는 O(n<sup>2</sup>)이다. 이는 figure 5에 나타나있다.		반면, quicksort에서 최악의 경우는 pivot이 배열을 극단적으로 한쪽으로만 쏠리게 분할할 때이다. 예를 들면, pivot이 항상 최댓값/최솟값으로 선택되는 경우이다. 분할 깊이는 n이므로 최종 시간 복잡도는 O(n<sup>2</sup>)이다. 이는 figure 5에 나타나있다.

Pinkgo: /* Time Complexity Analysis */

2025-09-22T04:35:39Z

Time Complexity Analysis

← 이전 판		2025년 9월 22일 (월) 04:35 판
249번째 줄:		249번째 줄:

	하지만, 평균적으로는 quicksort라는 이름처럼 매우 빠르다. pivot이 항상 극단적이지 않고 “적당히” 중간 근처에서 분할한다면, 기대 시간 복잡도는 O(n log(n))이다.		하지만, 평균적으로는 quicksort라는 이름처럼 매우 빠르다. pivot이 항상 극단적이지 않고 “적당히” 중간 근처에서 분할한다면, 기대 시간 복잡도는 O(n log(n))이다.

			시간 복잡도만 분석할 때에는, quicksort가 heapsort와 같은 다른 O(n log(n))의 시간 복잡도를 가지는 정렬 알고리즘보다 더욱 빠르다고 보기에는 어렵다. 하지만 실전에서는 quicksort가 보통 2~3배 더 빠르다. 이는 아래와 같은 이유를 가진다:
			# quicksort의 내부 루프 연산이 훨씬 단순하다.
			# 메모리 접근 패턴이 연속적이라 캐시 친화적이다.
			따라서 실제 구현에서 상수 계수가 작아서 더욱 빠른 속도를 자랑한다.

			===Improving Quicksort===
			위에서 살펴보았듯이, 기본적인 quicksort는 데이터가 이미 정렬되거나 특정 패턴을 만족하면 O(n<sup>2</sup>)의 시간복잡도를 가진다. 이 경우 적대적인 상황(“worst enemy”)에서 실행해야 한다면, 적은 항상 최악 입력을 줄 수 있다. 하지만 pivot을 무작위로 선택하면 이야기가 달라진다. 이렇게 무작위로 pivot 값을 정하는 quicksort를 randomized quicksort라고 한다. Randomized quicksort의 장점은 어떤 입력이 들어오든 항상 같은 확률로 좋은 pivot을 뽑을 수 있다는 것이다. 이는 일반적인 quicksort와는 아래와 같이 다르다:
			* 일반 quicksort: "무작위 입력일 때 기대 성능은 O(n log(n))"
			* Randomized quicksort: "임의의 입력일 때 기대 성능은 O(n log(n))"
			즉, 입력 데이터 분포에 기대지 않고, 알고리즘 자체가 랜덤성을 내장하기 때문에 더욱 강한 성능을 보장한다.

			이와 같이 pivot을 선택하는, 적어도 기본적인 quicksort보다는 더욱 좋은 방식이 존재한다. 이는 아래와 같다:
			# 중간 원소 사용: 항상 가운데 원소를 pivot으로 선택한다. 이미 정렬된 경우에 대해 유효하다.
			# 무작위 원소 사용: 배열에서 무작위 원소를 pivot으로 선택한다.
			# Median-of-Three: 첫 번째, 마지막, 중간 원소 중 중간값을 pivot으로 선택한다.<ref>평균(mean)이 아니라 중앙값(median)을 쓰는 이유는 극단값에 덜 민감하기 때문이다.</ref>
			다만, 어떤 방법을 써도 최악의 경우는 여전히 O(n<sup>2</sup>)이지만, 발생 확률이 매우 낮아진다.

	==각주==		==각주==

Pinkgo: /* Quicksort */

2025-09-22T04:21:09Z

Quicksort

← 이전 판		2025년 9월 22일 (월) 04:21 판
242번째 줄:		242번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			===Time Complexity Analysis===
			Quicksort는 입력으로 받아들인 배열에 따라 그 시간 복잡도가 달라진다. 예를 들어, quicksort에 대한 최상의 경우는 pivot이 배열을 항상 정확히 절반으로 나눌 때이다. 이는 figure 4에 나타나 있다. 각 단계에서 배열이 2등분되면, 각 단계에서 partition의 비용이 O(n)이고, 분할 깊이는 log<sub>2</sub>n이므로 최종 시간 복잡도는 O(n log(n))이다.

			반면, quicksort에서 최악의 경우는 pivot이 배열을 극단적으로 한쪽으로만 쏠리게 분할할 때이다. 예를 들면, pivot이 항상 최댓값/최솟값으로 선택되는 경우이다. 분할 깊이는 n이므로 최종 시간 복잡도는 O(n<sup>2</sup>)이다. 이는 figure 5에 나타나있다.

			하지만, 평균적으로는 quicksort라는 이름처럼 매우 빠르다. pivot이 항상 극단적이지 않고 “적당히” 중간 근처에서 분할한다면, 기대 시간 복잡도는 O(n log(n))이다.

	==각주==		==각주==

Pinkgo: /* Quicksort */

2025-09-22T04:09:11Z

Quicksort

← 이전 판		2025년 9월 22일 (월) 04:09 판
204번째 줄:		204번째 줄:
	* Before: 17, 12, 6, 19, 23, 8, 5, 10		* Before: 17, 12, 6, 19, 23, 8, 5, 10
	* After: 6, 8, 5, 10, 23, 19, 12, 17		* After: 6, 8, 5, 10, 23, 19, 12, 17
	이때 중요한 것은 pivot은 한 번 자리를 잡으면 최종 정렬된 배열에서의 위치가 확정된다는 것이다. 예를 들어, 위의 after에서의 10의 위치는 정렬이 완료된 후에도 바뀌지 않는다.		이때 중요한 것은 pivot은 한 번 자리를 잡으면 최종 정렬된 배열에서의 위치가 확정된다는 것이다. 예를 들어, 위의 after에서의 10의 위치는 정렬이 완료된 후에도 바뀌지 않는다. 즉, 한번 고정된 pivot의 위치는 더 이상 움직일 필요가 없다. 또한 분할 후에는 pivot 기준으로 왼쪽에는 항상 pivot보다 작은 값들만, 오른쪽에는 큰 값들만 존재한다. 따라서, 왼쪽 부분 배열과 오른쪽 부분 배열만 각각 독립적으로 정렬하면 전체 배열이 정렬된다.

	배열은 pivot 기준으로 한 번 선형 스캔(linear scan) 하면서 ~~분할한다~~. 분할의 목적은 배열을 pivot 값 기준으로 두 그룹으로 나누는 것이다:		따라서 중요한 것은 어떻게 분할을 수행하는지이다. 배열은 pivot 기준으로 한 번 선형 스캔(linear scan) 하면서 분할된다. 분할의 목적은 배열을 pivot 값 기준으로 두 그룹으로 나누는 것이다:
	* pivot의 왼쪽: pivot보다 작은 값들		* pivot의 왼쪽: pivot보다 작은 값들
	* pivot의 오른쪽: pivot보다 큰 값들		* pivot의 오른쪽: pivot보다 큰 값들
214번째 줄:		214번째 줄:
	* > pivot (오른쪽 경계): pivot보다 큰 값 (아직 다 정리되진 않았지만 위치상 오른쪽으로 보냄)		* > pivot (오른쪽 경계): pivot보다 큰 값 (아직 다 정리되진 않았지만 위치상 오른쪽으로 보냄)
	* Unexplored (미탐색 영역): 아직 검사하지 않은 원소		* Unexplored (미탐색 영역): 아직 검사하지 않은 원소
	~~Pivot을 배열의 마지막 원소로 지정할 때~~, ~~분할은~~ 아래와 같이 ~~이루어진다~~:		이러한 quicksort는 아래와 같은 코드를 통해 구현된다:
	* 왼쪽부터 오른쪽으로 원소를 ~~검사하면서,~~		<syntaxhighlight lang="c">
	** 현재 값이 pivot보다 ~~작으면 → 왼쪽 구간으로 보내고~~(~~left boundary 확장~~)		void quicksort(item_type s[], int l, int h) {
	** 현재 값이 pivot보다 ~~크거나 같으면 → 그대로 두고 다음으로 넘어감~~		int p; // partition index
	* 마지막에 pivot을 왼쪽 구간의 끝(=firsthigh)~~과 교환~~		if ((h - l) > 0) { //배열 크기가 1 이하이면 재귀 종료
			p = partition(s, l, h);
			quicksort(s, l, p - 1);
			quicksort(s, p + 1, h);
			}
			}
			</syntaxhighlight>
			위에서 partition() 함수는 pivot 기준으로 배열을 두 부분으로 나누고, pivot 위치를 반환한다. 이후 pivot 왼쪽 구간과 오른쪽 구간을 각각 재귀적으로 정렬하여 전체 배열을 정렬한다. 이때 partition() 함수는 아래와 같이 구현된다:
			<syntaxhighlight lang="c">
			int partition(item_type s[], int l, int h) {
			int i, p, firsthigh;
			p = h; // 마지막 원소를 pivot으로 선택
			firsthigh = l; // pivot보다 크거나 같은(high) 값들이 시작되는 위치.
			// 배열을 처음부터 끝까지 스캔하면서 pivot보다 작은 값들을 앞으로 몰아넣음.
			for (i = l; i < h; i++) {
			if (s[i] < s[p]) {
			swap(&s[i], &s[firsthigh]);
			firsthigh++;
			}
			}
			swap(&s[p], &s[firsthigh]); // pivot을 올바른 위치에 두기
			return firsthigh;
			}
			</syntaxhighlight>

	==각주==		==각주==

Pinkgo: /* Quicksort */

2025-09-22T00:49:15Z

Quicksort

← 이전 판		2025년 9월 22일 (월) 00:49 판
201번째 줄:		201번째 줄:

	==Quicksort==		==Quicksort==
			Quicksort는 내부 정렬(internal sorting) 알고리즘 중 가장 빠른 알고리즘으로 알려져 있다. Quicksort의 핵심 아이디어는 분할(Partitioning)인데, 이는 하나의 원소(pivot)를 기준으로, pivot보다 작은 값들은 왼쪽에, pivot보다 큰 값들은 오른쪽에 두도록 배열을 나누는 것이다. 예를 들어 pivot = 10일 때,
			* Before: 17, 12, 6, 19, 23, 8, 5, 10
			* After: 6, 8, 5, 10, 23, 19, 12, 17
			이때 중요한 것은 pivot은 한 번 자리를 잡으면 최종 정렬된 배열에서의 위치가 확정된다는 것이다. 예를 들어, 위의 after에서의 10의 위치는 정렬이 완료된 후에도 바뀌지 않는다.

			배열은 pivot 기준으로 한 번 선형 스캔(linear scan) 하면서 분할한다. 분할의 목적은 배열을 pivot 값 기준으로 두 그룹으로 나누는 것이다:
			* pivot의 왼쪽: pivot보다 작은 값들
			* pivot의 오른쪽: pivot보다 큰 값들
			* pivot: 둘 사이에 정확히 위치를 확정
			이 과정에서 분할 과정에서는 배열을 pivot 기준으로 한 번 선형 스캔(linear scan) 하면서, 아래의 세 가지 영역을 유지한다:
			* < pivot (왼쪽 경계): 이미 처리된 값 중 pivot보다 작은 값
			* > pivot (오른쪽 경계): pivot보다 큰 값 (아직 다 정리되진 않았지만 위치상 오른쪽으로 보냄)
			* Unexplored (미탐색 영역): 아직 검사하지 않은 원소
			Pivot을 배열의 마지막 원소로 지정할 때, 분할은 아래와 같이 이루어진다:
			* 왼쪽부터 오른쪽으로 원소를 검사하면서,
			** 현재 값이 pivot보다 작으면 → 왼쪽 구간으로 보내고(left boundary 확장)
			** 현재 값이 pivot보다 크거나 같으면 → 그대로 두고 다음으로 넘어감
			* 마지막에 pivot을 왼쪽 구간의 끝(=firsthigh)과 교환

	==각주==		==각주==

Pinkgo: /* Merge Sort */

2025-09-22T00:25:54Z

Merge Sort

← 이전 판		2025년 9월 22일 (월) 00:25 판
125번째 줄:		125번째 줄:
	</syntaxhighlight>		</syntaxhighlight>

	==~~Merge Sort~~==		==Mergesort==
	~~Merge sort는~~ 재귀적인 알고리즘으로, 큰 문제를 작은 문제로 나누어 해결하는 방식을 취한다. 이는 배열을 두 그룹으로 나눈 뒤, 각각을 재귀적으로 정렬하고, 마지막에 두 정렬된 리스트를 합쳐서 최종적으로 정렬된 리스트를 얻는 방법이다. 이는 “Divide and Conquer(분할 정복)”이라는 알고리즘 개념의 전형적인 예시이다. 아래는 ~~merge sort를~~ 구현한 코드이다:		Mergesort는 재귀적인 알고리즘으로, 큰 문제를 작은 문제로 나누어 해결하는 방식을 취한다. 이는 배열을 두 그룹으로 나눈 뒤, 각각을 재귀적으로 정렬하고, 마지막에 두 정렬된 리스트를 합쳐서 최종적으로 정렬된 리스트를 얻는 방법이다. 이는 “Divide and Conquer(분할 정복)”이라는 알고리즘 개념의 전형적인 예시이다. 아래는 mergesort를 구현한 코드이다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	// 인자: s는 배열, low와 high는 정렬 구간의 시작과 끝 인덱스		// 인자: s는 배열, low와 high는 정렬 구간의 시작과 끝 인덱스
140번째 줄:		140번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	~~Merge sort의~~ 핵심적인 성능은 두 개의 정렬된 리스트를 얼마나 효율적으로 합치는가에 달려 있다. 이때 합치는 과정은, 가장 작은 원소를 두 리스트의 맨 앞에서 비교해 하나씩 빼내고, 그 과정을 반복하는 것이다. 예를 들어, 두 리스트 A = {5,7,12,19}, B = {4,6,13,15}를 합칠 경우:		Mergesort의 핵심적인 성능은 두 개의 정렬된 리스트를 얼마나 효율적으로 합치는가에 달려 있다. 이때 합치는 과정은, 가장 작은 원소를 두 리스트의 맨 앞에서 비교해 하나씩 빼내고, 그 과정을 반복하는 것이다. 예를 들어, 두 리스트 A = {5,7,12,19}, B = {4,6,13,15}를 합칠 경우:
	# 먼저 4 vs 5 비교 → 4 선택		# 먼저 4 vs 5 비교 → 4 선택
	# 5 vs 6 비교 → 5 선택		# 5 vs 6 비교 → 5 선택
171번째 줄:		171번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	[[파일:Figure 3. ~~Merge Sort~~ Time Complexity.png\|섬네일\|300x300픽셀\|Figure 3. Merge Sort Time Complexity]]		[[파일:Figure 3. Mergesort Time Complexity.png\|섬네일\|300x300픽셀\|Figure 3. Merge Sort Time Complexity]]
	앞서 설명했듯이, 각 단계에서 합병(merge) 과정은 O(n) 시간이 걸린다. 이때 분할 작업은 주어진 배열을 log<sub>2</sub>(n) 단계로 나누기 때문에 전체 시간 복잡도는 O(n log(n))의 시간복잡도이다. 이는 figure 3를 참고하여 더욱 쉽게 이해할 수 있다.		앞서 설명했듯이, 각 단계에서 합병(merge) 과정은 O(n) 시간이 걸린다. 이때 분할 작업은 주어진 배열을 log<sub>2</sub>(n) 단계로 나누기 때문에 전체 시간 복잡도는 O(n log(n))의 시간복잡도이다. 이는 figure 3를 참고하여 더욱 쉽게 이해할 수 있다.

	===Divide and Conquer===		===Divide and Conquer===
	~~Merge sort는~~ 대표적인 devide and conquer 알고리즘인데, 이는 큰 문제를 작은 문제들로 나누어서 해결하고, 그 결과를 이용하여 큰 문제도 푸는 알고리즘이다. 이 절차는 아래와 같다:		Mergesort는 대표적인 devide and conquer 알고리즘인데, 이는 큰 문제를 작은 문제들로 나누어서 해결하고, 그 결과를 이용하여 큰 문제도 푸는 알고리즘이다. 이 절차는 아래와 같다:
	# Divide: 문제를 두 개의 작은 문제로 나눔.		# Divide: 문제를 두 개의 작은 문제로 나눔.
	# Conquer: 각 부분 문제를 재귀적으로 해결.		# Conquer: 각 부분 문제를 재귀적으로 해결.
	#Combine: 두 해를 합쳐서 전체 문제의 해를 구함.		#Combine: 두 해를 합쳐서 전체 문제의 해를 구함.
	~~Merge sort에서~~ 정렬 문제를 풀기 위해서 필요한 시간을 T(n)이라고 하고, 크기 n 문제를 반으로 쪼갠 뒤 왼쪽 절반과 오른쪽 절반을 각각 정렬하는 데 걸리는 시간을 2T(n/2)라고 하자. 마지막으로 두 개의 정렬된 리스트를 병합(merge)하는 과정에서 걸리는 시간을 <math>\Theta</math>(n)이라고 하면, 아래와 같은 점화식을 도출할 수 있다.		Mergesort에서 정렬 문제를 풀기 위해서 필요한 시간을 T(n)이라고 하고, 크기 n 문제를 반으로 쪼갠 뒤 왼쪽 절반과 오른쪽 절반을 각각 정렬하는 데 걸리는 시간을 2T(n/2)라고 하자. 마지막으로 두 개의 정렬된 리스트를 병합(merge)하는 과정에서 걸리는 시간을 <math>\Theta</math>(n)이라고 하면, 아래와 같은 점화식을 도출할 수 있다.
	<math>T(n)=2T(n/2)+\Theta(n)=\Theta(n\,\,log(n))</math>		<math>T(n)=2T(n/2)+\Theta(n)=\Theta(n\,\,log(n))</math>
	이를 일반화 하면 아래와 같다:		이를 일반화 하면 아래와 같다:
198번째 줄:		198번째 줄:
	랜덤 액세스란 저장 장치의 어느 위치든 “임의로” 바로 접근하는 방식이다. 예를 들면, 어떤 파일이나 데이터의 2004번째 데이터에 직접 바로 접근하는 것이다. 메모리(RAM)는 진짜 랜덤 액세스를 수행할 수 있지만, 디스크(HDD/SSD)에서는 해당 데이터의 위치를 찾기 위해서 물리적으로 탐색(Seek)하는 과정이 필요하다. 반면, 순차 액세스란 데이터를 “앞에서부터 차례차례” 읽거나 쓰는 방식이다. 이때 RAM에서는 랜덤과 순차 차이가 거의 없지만, 디스크에서는 둘 사이에 매우 큰 차이가 발생한다.		랜덤 액세스란 저장 장치의 어느 위치든 “임의로” 바로 접근하는 방식이다. 예를 들면, 어떤 파일이나 데이터의 2004번째 데이터에 직접 바로 접근하는 것이다. 메모리(RAM)는 진짜 랜덤 액세스를 수행할 수 있지만, 디스크(HDD/SSD)에서는 해당 데이터의 위치를 찾기 위해서 물리적으로 탐색(Seek)하는 과정이 필요하다. 반면, 순차 액세스란 데이터를 “앞에서부터 차례차례” 읽거나 쓰는 방식이다. 이때 RAM에서는 랜덤과 순차 차이가 거의 없지만, 디스크에서는 둘 사이에 매우 큰 차이가 발생한다.

	~~Merge sort가~~ 디스크를 사용하는 외부 정렬에서 효율적인 이유는 순차 액세스 기반으로 작동하기 때문이다. 각 run 파일을 “앞에서부터 쭉” 읽고, 결과를 “앞에서부터 쭉” 쓰면 된다. 이는 디스크에 불필요한 탐색 절차를 요구하지 않는다. 반대로 QuickSort 같은 알고리즘은 중간 위치를 계속 참조해야 해서 랜덤 액세스 패턴이 많다.		Mergesort가 디스크를 사용하는 외부 정렬에서 효율적인 이유는 순차 액세스 기반으로 작동하기 때문이다. 각 run 파일을 “앞에서부터 쭉” 읽고, 결과를 “앞에서부터 쭉” 쓰면 된다. 이는 디스크에 불필요한 탐색 절차를 요구하지 않는다. 반대로 QuickSort 같은 알고리즘은 중간 위치를 계속 참조해야 해서 랜덤 액세스 패턴이 많다.

	==Quicksort==		==Quicksort==

	==각주==		==각주==