Divide and Conqure Algorithm(2)

퀵 정렬

• 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
  • 오름차순으로 정렬한다고 가정

• 피벗

  : 주어진 배열을 두 부분배열로 분할할 때 기준이 되는 특정 원소

  • 보통 주워진 배열의 첫번째 원소로 지정한다.

개념과 원리

피벗이 제자리를 잡도록 하여 정렬하는 방식

왼쪽 부분배열의 모든 값 < **피벗** < 오른쪽 부분배열의 모든 값

• 분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할한다.
• 정복: 두 부분배열에 대해서 퀵 정렬ㄹ을 순환적으로 적용하여 각 부분배열을 정렬한다.
• 결합: 필요 없음

알고리즘

피벗 위치를 중심으로 분할함수 실행 > 중간 index를 중심으로 다시 중간 index로 퀵정렬 호출 반복

QuickShort(A[], n)
{
	if (n>1) {
		pivot = Partition(A[0..n-1], n); // 두 부분배열로 분할
		QuickSort(A[0...pivot-1], pivot); // 왼쪽 부분배열에 대한 순환 호출
		QuickSort(A[pivot+1...n-1], n-pivot-1); // 오른쪽 부분배열에 대한 순환 호출
	}
}

분할함수

int Partiction(A[], n)
{
	Left = 1; Right = n-1;
	while ( Left < Right ) { //피벗 A[0]
	//피벗보다 큰 값의 위치를 찾음
	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() 수행시간

→ O(n) 혹은 theta(n)

⇒데이터 계수에 선행적으로 비례하는 시간

퀵 정렬 QuickSort() 수행시간

T(n) = T(a) + T(b) + O(n)

→ T(n) = 오른쪽 정렬 시간 + 왼쪽 정렬 시간 + 피봇분할시간

T(1) = O(n)

분할된 두 부분배열의 크기에 따라 성능시간이 달라짐

성능분석

최악의 경우

• 배열이 항상 0:n 또는 n-1:0으로 분할되는 경우

  → 피벗만 제자리 잡고 왼쪽 오른쪽이 부분배열되는 경우

  피벗이 늘 가장 최댓값이나 가장 최솟값이 될 때

  즉, 극심한 균형적 분할

  입력 데이터가 정렬된 경우, 그리고 피벗을 배열의 처음 원소로 정한 경우

T(n) = T(n-1) + O(n)

→ T(n) = O(n2)

최선의 경우

• 배열이 항상 n/2:n/2로 분할되는 경우

  → 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우

  피벗이 항상 부분배열의 중간값이 되는 경우

합병정렬

• 분할: 배열을 동일한 크기의 두 개의 부분배열로 분할하고(왼쪽 오른쪽) - 입력크기 n인 배열을 n/2인 두 부분배열로 분할
• 정복: 각각의 부분배열을 순환적으로 정렬한 후,
• 결합: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

→ 더이상 분할이 불가능할 때까지 자르고(n/2 반복) 이후 각각을 합병

1. 재귀

MergeSort(A[], n) 
{
	if (n > 1) {
		Mid = n/2;
		B[0...Mid-1] = MergeSort(A[0...Mid-1], Mid); // 왼쪽 부분배열
		C[0...n-Mid-1] = MergeSort(A[Mid...n-1], n-Mid);// 오른쪽 부분배열
		A[0...n-1]=Merge(B[0...Mid-1], C[0...n-Mid-1], Mid, n-Mid);
	}
	return A;
}

1. 반복

Merge (B[], C[], n, m) {
i = j = k = 0;
while ( i<n && j<m ) {
if ( B[i] <= C[j] ) A[k++] = B[i++];
else
A[k++] = C[j++];
//A[n+m-1] ← B[n] + C[m]
//비교해서 작은 값을 A[]로 이동
}
for ( ; i<n; i++) A[k++] = B[i]; //남은 B[]의 데이터 → A[] for ( ; j<m; j++) A[k++] = C[j]; //남은 C[]의 데이터 → A[] return A[0..n+m-1];
}

• 합병함수 Merge() 수행 시간
  • B[n/2] + C[n/2] → A[n]

  • 비교횟수: n/2 ~ (n/2 + n/2 - 1 = n - 1)

    ⇒ n/2 (최소) ~ n-1 (최대) 비교

    ⇒ O(n)

  • 입력 데이터 개수 n만큼의 추가 저장 장소(B[] + c[])가 필요
• 점화식

⇒ T(n) = T(n/2) + T(n/2) + O(n), T(1) = 1

(왼쪽 정렬 + 오른쪽 정렬 + 합병)

⇒ T(n) = 2T(n/2) + O(n)

⇒ T(n) = O(nlogn)

• 비순환적 합병 정렬 (반복문)

  → 분할 과정 X 합병만을 반복해서 합병병렬 수행

선택문제

: n개의 원소가 임의의 순서로 저장된 배열A[0..n-1]에서 i번째로 작은 원소를 찾는 문제

• 직관적 방법

  1)오름차순으로 정렬한 후 i번째 원소를 찾는 방법 → O(nlogn)

  2)최솟값을 찾는 과정을 i번 반복(i-1번째까지는 최솟값 찾은 후 삭제) → O(in)

• 알고리즘 1) → 최악 O(n2), 평균 O(n)
• 알고리즘 2) → 최악 O(n), 평균 O(n)

1) 최솟값을 찾은 후 최댓값 찾기 (or 반대)

• n - 1번 비교 + n - 2번 비교

  ⇒ 2n - 3번의 비교 ⇒ O(n)

2) 모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값 비교

• 3/2n - 2번 비교

    FindMinMax (A[], n, min, max) {
    	if (A[0]<A[1]) { min = A[0]; max = A[1]; }
    	else { min = A[1]; max = A[0]; }
    	for (i=2; i<n; i+=2) {
    		if (A[i]<A[i+1]) { small = A[i]; large = A[i+1]; } 
    		else { small = A[i+1]; large = A[i]; }
    		if (small < min) min = small;
    		if (large > max) max = large;
    } }
  

정리!

i번째로 작은 원소 찾기 > 최악 O(n2) 평균 O(n)

• 알고리즘 1

  • 퀵 정렬의 분할함수 Partiion()을 순환적으로 적용하는 방식

    1) i = pivot

    2) i < pivot → 왼쪽 부분배열 순환적용

    3) i > pivot → 오른쪽 부분배열 순환적용

  • 개념 원리
    • 분할: 피벗 기준으로 두 부분배열 분할, i가 피벗의 p와 같으면 피벗 값 반환 종료
    • 정복: 인덱스 i가 포함된 부분배열에 대해서 알고리즘을 순환적으로 호출
    • 결합: x

  • 예제 알고리즘

      int Selection (A[], n, i) // 1 ≤ i ≤ n 
      {
      	Left = 0; Right = n-1;
      	p = Partition(A, n); // 0 ≤ p ≤ n-1
      	if (i == p+1) return A[p];
      		else if ( i<p+1 ) Selection(A[Left..p-1], (p-1)-Left+1, i);
      else Selection(A[p+1..Right], Right-(p+1)+1, i-p-1); 
      }
    

  • 성능분석
    • 최악의 경우 = 퀵 정렬의 최악의 경우
      • 분할함수가 항상 하나의 부분배열만 생성하는 경우