4강. 정렬 ( 2 )

1. 퀵 정렬 - QuickSort( )

• 특정 데이터를 기준으로 주어진 배열을 2개의 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
• 피벗( Pivot ) : 분할 원소
  • 주어진 배열을 두 부분배열로 분할하는 기준이 되는 특정 데이터
  • 보통 주어진 배열의 첫 번째 데이터로 지정

2. 퀵 정렬의 원리

• 피벗이 제자리를 잡도록 하여 정렬하는 방식
• 예시
  • 입력배열 A에 저장된 원소 중 첫번째 원소인 30을 피벗으로 지정
  • 피벗 30을 제자리 잡도록하여 왼쪽 부분 배열과 오른쪽 부분 배열로 구분
    • 피벗을 기준으로 왼쪽은 피벗보다 작은 원소, 오른쪽은 큰 원소가 위치
      • 왼쪽 부분배열의 모든 데이터 < 오른쪽 부분배열에서 가장 작은 데이터
      • 왼쪽 부분배열에서 가장 큰 데이터 < 오른쪽 부분배열의 모든 데이터
  • 왼쪽 부분배열의 모든 값 < 피벗 < 오른쪽 부분배열의 모든 값이 적용되면 피벗은 제자리를 잡은 것이기에 다음 원소를 피벗으로 삼는다.

3. 퀵 정렬 알고리즘

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

4. 퀵 정렬 - 분할 과정

• 왼 → 오 : 피벗보다 큰( 같은 ) 값을 찾음 [Left]
• 오 → 왼 : 피벗보다 작은 값을 찾음 [Right]
• 각 조건에 해당하는 Left 위치와 Right 위치를 파악하여 서로 위치를 교환
• 교환하다가 Left 위치 값 > Right 위치값으로 되는 순간 Right위치와 피벗과 위치를 교환 후 분할 과정을 끝냄

5. 분할 함수 - Partition( )

int Partition (A[ ], n){
	Left = 1; Right = n-1;
	while (Left < Right) {
	
		// 오른쪽으로 진행하면서 피벗 A[0]보다
		// 큰 값의 위치를 찾음
		while (Left < n && A[Left] < A[0]) Left++;
		
		// 왼쪽으로 진행하면서 피벗 A[0]보다
		// 작은 값의 위치를 찾음
		while (Right > 0 && A[Right] >= A[0]) Right--;
		
		if (Left < Right)
			A[Left]와 A[Right]의 위치 교환
		else
			// 피벗과의 위치 교환 후 첫 번째 while문 종료
			피벗 A[0]와 A[Right]의 위치 교환
	}
	return (Right);
}

6. 분할 함수의 성능과 특징

• 피벗과의 비교 횟수
  • 각 데이터는 피벗과 1회 또는 많아야 2회씩 비교
  • Θ(n)

7. 퀵 정렬의 성능

• 퀵 정렬 QuickSort( )의 수행시간은 분할되는 두 부분배열의 크기에 따라 달라짐
  • T(n) = T(nL)[왼쪽 부분배열에 걸리는 시간] + T(nR) [오른쪽 부분배열에 걸리는 시간] + Θ(n)
• 최악의 경우
  • 배열이 항상 0:n-1 또는 n-1:0으로 분할되는 경우 ( 극심한 불균형적 분할 )
  • 이는 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열이 되는 경우에는
  • 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우가 됨
  • 이 경우 T(n) = T(n-1) + Θ(n) → T(n) = O(n2)
• 최선의 경우
  • 배열이 항상 n/2 : n/2로 분할되는 경우 ( 가장 균형적인 분할 )
  • 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
  • 이는 피벗이 항상 배열의 중간값이 되는 경우
  • 이 경우 T(n) = 2T(n/2) + Θ(n) → T(n) = O(nlogn)
• 평균 수행시간
  • 부분배열의 모든 분할 비율에 따른 수행시간의 평균
  • 피벗은 동일한 확률을 가지고 분할 후 배열의 어느 곳에나 위치 가능
  • T(n) = O(nlogn)

8. 퀵 정렬의 특징

• 피벗 선택의 임의성만 보장되면 평균 수행시간을 보장
  • 최선 / 평균 수행시간 → O(nlogn)
  • 최악의 수행시간 → O(n2)
  • 피벗을 배열의 첫 번째 원소로 지정하는 경우가 아닌 배열에서 임의의 값을 선택한 후, 배열의 첫 번째 원소와 서로 교환한 후 정렬 수행하면 해결 가능
• 제자리 정렬 알고리즘
  • 입력 배열 이외에 추가적인 저장 공간을 상수 개( Left, Right, tmp, n, pivot )만 사용
• 안정적이지 않은 정렬 알고리즘
• 분할정복 방법이 적용된 알고리즘 → 순환한다는 의미
  • 분할
    • 피벗을 기준으로 주어진 배열을 두 부분배열로 분할
    • 두 부분배열의 크기는 일정하지 않음
  • 정복
    • 두 부분배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬함
  • 결합
    • 필요 없음

9. 합병 정렬

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

10. 합병 정렬 알고리즘

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

11. 합병 함수 - Merge( )

Merge (B[ ], C[ ], n, m){
	i = j = k = 0;
	
	// 정렬된 부분배열 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++];
		
	// 정렬된 부분배열 B[ ] 또는 C[ ]에 남아 있는 모든 데이터를 A[ ]로 복사
	for ( ; i < n; i++) A[k++] = B[i];
	for ( ; j < m; j++) A[k++] = C[j];
	
	return (A[0..n+m-1]);
}

12. 합병 함수의 성능

• 합병 함수의 수행시간
  • 두 부분배열 B[ ]와 C[ ]간의 비교 횟수
  • Θ(n)

13. 합병 정렬의 성능

• 합병 정렬의 수행시간
  • T(n) = 2T(n/2) + Θ(n) → T(n) = O(nlogn)

14. 합병 정렬의 특징

• 안정적인 정렬 알고리즘
  • 합병 과정에서 동일한 두 데이터에 대해서 항상 왼쪽 데이터를 먼저 선택함
• 제자리 정렬 알고리즘 X
  • A[n] = B[n/2] + C[n/2] → 입력 크기 𝑛만큼의 추가적인 공간을 요구
• 전형적인 분할정복 방법 적용
  • 분할
    • 주어진 배열을 동일한 크기의 2개의 부분배열로 분할
  • 정복
    • 각 부분배열에 대해서 합병 정렬을 순환적으로 적용하여 정렬함
  • 결합
    • 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

15. 요약

• 퀵 정렬
  • ”피벗”, 분할 함수 O(n)
  • 분할되는 두 부분배열의 크기에 따라 성능이 달라짐
    • 최악 O(n2), 최선/평균 O(nlogn)
  • 불안정적, 제자리
  • 피벗 선택의 임의성만 보장되면 평균적인 성능 O(nlogn)을 보임
  • 분할정복 방법이 적용됨
• 합병 정렬
  • 합병 함수 O(n), 최악/최선/평균 O(nlogn)
  • 안정적 정렬, 제자리 정렬이 아님
  • 전형적인 분할정복 방법이 적용됨