[알고리즘] 정렬 -2

정렬

퀵 정렬

특정 데이터를 기준으로 주어진 배열을 2개의 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
피벗이 제자리를 잡도록 하여 정렬하는 방식
피벗
- 주어진 배열을 두 부분배열로 분할하는 기준이 되는 특정 데이터
- 보통 주어진 배열의 첫 번째 데이터로 지정

QuickSort(A[], n){
	if(n > 1) {
		//1. 피벗을 기준으로 두 부분 배열로 분할
		// 피벗은 제자리를 잡은 피벗의 인덱스를 표시
		pivot = Partition(A[0..n-1], n);
		
		//2. 왼쪽 부분 배열에 대한 퀵 정렬의 순환 호출
		QuickSort(A[0..pivot-1], pivot);
		
		//3. 오른쪽 부분 배열에 대한 퀵 정렬의 순환 호출
		QuickSort(A[pivot+1..n-1], n-pivot=1);
	}
}

int Partition(A[], n) {
	Left = 1; Right = n-1;
	while(Left<Right) {
		while(Left<n && A[Left]<A[0]) Left++;
		while(Right>0 && A[Right]>=A[0]) Right--;
		if(Left<Right) A[Left]와 A[Right]의 위치 교환
		else 피벗 A[0]와 A[Right]의 위치 교환
	}
	return (Right);
}

분할 함수 Partition()의 특징
- 각 데이터는 피벗과 1회 또는 많아야 2회씩 비교
- 성능 : O(n)
퀵 정렬 QuickSort()의 특징
- 수행시간은 분할되는 두 부분 배열의 크기에 따라 달라짐
- 최악의 경우 = 0:n-1 or n-1:0, 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우 = 입력데이터가 정렬되어있고 피벗을 첫번째 원소로 정한 경우 : O(n^2^)
- 최선의 경우 = n/2:n/2, 피벗을 중심으로 항상 동일한 크기의 두 부분 배열로 분할되는 경우 = O(nlogn)
- 평균 : O(nlogn)
- 따라서 피벗 선택의 임의성만 보장되면 평균 수행시간을 보장 => 배열에서 임의의 값을 선택한 후 첫 번째 원소와 교환

평균 성능	최선 성능	최악 성능	제자리 정렬	안정적 정렬
O(nlogn)	O(nlogn)	O(^2^)	O	X

분할 정복 방법이 적용된 알고리즘
- 분할 : 피벗을 기준으로 주어진 배열을 두 부분배열로 분할, 두 부분배열의 크기는 일정하지 않음
- 정복 : 두 부분 배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분 배열을 정렬함
- 결합 : 필요 없음

합병 정렬

주어진 배열을 동일한 크기의 두 부분배열로 분할하고, 각 부분배열에 순환적으로 합병 정렬을 적용하여 정렬시킨 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

MergeSort(A[], n){
	if(n > 1) {
		Mid = └n/2┘
		
		//1. 왼쪽 부분 배열의 순환 호출, 크기 n/2인 정렬된 배열 반환
		B[0..Mid-1] = MergeSort(A[0..Mid-1], Mid);
		
		//2. 오른쪽 부분 배열의 순환 호출, 크기 n/2인 정렬된 배열 반환
		C[0..n-Mid-1] = MergeSort(A[Mid..n-1], n-Mid);
		
		//3. 정렬된 두 부분배열 B[]와 C[]의 합병
		A[0..n-1] = Merge(B[0..Mid-1], C[0..n-Mid-1], Mid, n-Mid);
	}
	return(A);
}

Merge(B[], C[], n, m) {
	i =j = k = 0;
	// 1. 정렬된 부분배열 B[i]와 C[j]를 비교해서 작은 데이터를 A[k]에 복사
	while(i<n && j<m){
		if(B[i]<=C[j] A[k++] = B[i++];
		else A[K++] = C[j++];
	}
	// 2. 정렬된 부분배열 B[] 또는 C[]에 남아있는 모든 데이터를 A[]로 복사
	for(;i<n;i++) A[k++] = B[i];
	for(;i<m;j++) A[k++] = C[j];
	return (A[0..n+m-1]);
}

합병 함수 Merge()의 특징
- 최악의 경우 : O(n)
합병 정렬 MergeSort()의 특징
- 최선, 최악, 평균 : O(nlogn)

평균 성능	최선 성능	최악 성능	제자리 정렬	안정적 정렬
O(nlogn)	O(nlogn)	O(nlogn)	X	O

전형적인 분할 정복 방법이 적용된 알고리즘
- 분할 : 주어진 배열을 동일한 크기의 2개의 부분 배열로 분할
- 정복 : 각 부분 배열에 대해서 합병 정렬을 순환적으로 적용하여 정렬
- 결합 : 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

IM

정렬

퀵 정렬

합병 정렬