5강. 정렬 (3)

1. 힙 자료구조

• 힙 정렬이란?
  • ‘힙’ 자료구조의 장점을 활용한 정렬
• 힙 자료구조의 장점
  • 임의의 값 삽입과 최댓값 삭제가 쉬움
• (최대) 힙 heap
  • 완전 이진 트리 ( complete binary tree )
    • 각 레벨별로 노드가 있어야 함
    • 마지막 레벨에서 왼쪽부터 오른쪽으로 노트를 확인했을 때 빈자리가 없어야 함
  • 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같아야 함
• 최소 힙
  • 완전 이진 트리 ( complete binary tree )
  • 각 노드의 값은 자신의 자식 노드의 값보다 작거나 같아야 함

2. 힙의 구현

• 일차원 배열로 구현
  • 레벨을 인덱스로 노드값을 원소 값으로 구현
  • 간단한 인덱스 조작을 통해 자식 노드를 확인할 수 있다.
    • 자식 노드 찾는 방법 : 2 * 부모노드인덱스 + 1, 2 * 부모노드인덱스 + 2
  • 간단한 인덱스 조작을 통해 부모 노드를 확인할 수 있다.
    • 부모 노드 찾는 방법 : ( 자식노드인덱스 / 2 ) - 1, ( 자식노드인덱스 - 1 ) / 2

3. 힙의 장점

• 임의의 값의 삽입하기에 편리
  • 노드는 왼쪽부터 오른쪽으로 확인했을 때 빈자리가 없아야 하기에 가장 마지막 레벨의 자식 노드에 임의의 값 삽입 → 삽입 후 부모 노드와 값을 비교하면서 자리를 교환
• 최댓값 삭제
  • 최댓값은 가장 첫번째 원소이기에 가장 마지막 인덱스의 원소와 가장 첫번째 인덱스의 원소의 자리를 교환 → 마지막 인덱스로 이동한 최댓값 삭제 → 자식 노드와 부모 노드를 비교하면서 자리를 교환하며 힙 재구성
  • 첫번째 인덱스와 마지막 인덱스의 원소의 자리를 교환하는 이유는 완전 이진 트리 구조를 유지하기 위함

4. 힙의 정렬

• 힙 정렬이란?
  • 힙 구조의 장점을 활용한 정렬 방식
• 정렬의 처리 과정
  • 1단계
    • 1차원 배열을 힙으로 변환
  • 2단계 ( 1차원 배열을 데이터 개수만큼 반복 )
    • 힙의 최댓값 삭제
    • 힙의 재구성

5. 힙의 정렬 알고리즘

HeapSort (A[ ], n) {
	// --- 단계1 --(새 노드의 삽입)-------
	for (i=0; i<n; i++) {
		par = | i/2 | -1;
		while ( par>=0 && A[par]<A[i] ) {
			// A[par]과 A[i]의 교환;
			i = par;
			par = | (i-1)/2 |;
		}
	}
	// ------------- 단계2 ---------------
	return (A);
}

for (i=n-1; i>0; i-- ) { 
	// ----- 단계2 -----
	// 최댓값 A[0]와 마지막노드 A[i]의 교환;
	cur = 0; lch = 1; rch = 2;
	do { 
		// ------- 힙의 재구성 ---------
		if ( rch < i && A[lch] < A[rch] ) lch = rch;
		if ( A[lch] > A[cur] ) {
			A[cur]과 A[lch]의 교환;
			cur = lch;
			lch = cur*2 + 1;
			rch = cur*2 + 2;
		}
		else lch = i;
	} while ( lch < i )
}

6. 힙 정렬의 처리 과정

• 1단계
  • 1차원 배열을 힙으로 변환
• 2단계 ( 데이터 개수만큼 반복 )
  • 최대값 삭제
  • 힙의 재구성

7. 초기 힙 구축 ( 1단계 )

• 1차원 입력 배열을 힙으로 변환하는 것
• 두 가지 접근 방법
  • 방법 1
    • 주어진 입력 배열의 각 원소를 힙에 삽입하는 과정을 반복
  • 방법 2
    • 주어진 입력 배열을 우선 완전 이진 트리로 만든 후,
    • 각 노드에 대해 아래에서 위로 그리고 오른쪽에서 왼쪽으로 진행하면서
    • 해당 노드의 아랫부분이 힙의 조건을 만족할 수 있도록
    • 트리를 따라 내려가면서 자신의 자손 노드들과의 위치 교환을 계속해 나가는 방법

8. 초기 힙 구축 - 방법 1

• 1차원 입력 배열의 원소를 첫번째부터 차례대로 힙에 삽입
• 자식 노드에 차례대로 넣은 후, 부모와 자식 노드 값을 비교하여 힙 재구성

9. 초기 힙 구축 - 방법 2

• 완전 이진 트리 형태로 일단 값을 입력
• 가장 마지막 레벨의 자식노드의 값과 그 바로 위의 부모 노드의 값을 비교하는 것을 반복하여 힙 재구성
• 비교 / 위치 교환은 힙의 조건이 만족될 때까지 트리를 따라 내려가면서 계속 진행

10. 힙 정렬 2단계

• 가장 부모레벨의 노드와 가장 마지막 인덱스의 자식 노드를 바꾼 후, 삭제 및 힙 재구성을 반복

11. 힙 정렬의 성능

• 최선, 최악, 평균 수행시간 모두 → O(nlogn)
• 초기 힙 생성, 최댓값 삭제 및 힙 재구성
  • 바깥 루프 → 입력 크기 n에 비례
  • 안쪽 루프 → 완전 이진 트리의 높이 logn에 비례

12. 힙 정렬의 특징

• 안정적이지 않은 정렬 알고리즘
• 제자리 정렬 알고리즘

13. 정렬 알고리즘

• 비교 기반의 정렬 알고리즘
  • 기본 성능 O(n2) → 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬
  • 향상된 평균 성능 O(nlogn) → 퀵 정렬, 합병 정렬, 힙 정렬
  • 비교 기반 정렬 알고리즘 성능의 하한 → O(nlogn)
    • 아무리 빨라도 O(nlogn) 보다 효율적인 알고리즘은 구할 수 없음
• 이미 얻어진 데이터 분포 정보를 활용하는 정렬 알고리즘
  • 계수 정렬, 기수 정렬, 버킷 정렬 → 선형 시간 O(n)이 가능
  • 보편성이 떨어짐 ( 제한적 )

14. 계수 정렬

• 주어진 데이터 중에서 자신보다 작거나 같은 값을 갖는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식
  • 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우에 적용 가능
  • k보다 작거나 같은 값을 갖는 데이터의 개수 == 정렬 순서상 k의 마지막 위치
  • 자신보다 작거나 같은 값을 갖는 데이터의 개수의 효율적인 계산 방법
    • 입력값의 범위 a ~ b에 해당하는 크기의 배열 COUNT[a..b]를 할당하고, 주어진 값들을 한 번 쭉 훑으면 각 입력값의 출현횟수의 누적값 계산이 가능

15. 계수 정렬 알고리즘

• 입력값의 정렬 : B[ COUNT[ A[i] ] ] = A[i], COUNT[ A[i] ]—

CountingSort (A[1..n], n){
	MIN = MAX = A[1]; 
	
	for (i=2; i<=n; i++) { // 입력값의 범위 MIN~MAX 계산 
		if (A[i] < MIN) MIN = A[i];
		if (A[i] > MAX) MAX = A[i];
	}
	
	for (j=MIN; j <= MAX; j++) COUNT[j] = 0;
	
	for (i=1; i <= n; i++) COUNT[ A[i] ]++; // 각 입력값의 출현횟수 계산
	
	for (j=MIN+1; j <= MAX; j++) { // 각 입력값의 출현횟수의 누적값 계산
		COUNT[j] = COUNT[j] + COUNT[j-1]; 
	}
	
	for (i=n; i > 0; i--) { // 입력 배열 A[] → 정렬 배열 B[]
		B[ COUNT[ A[i] ] ] = A[i];
		COUNT[ A[i] ]--;
	}
	return (B);
}

16. 계수 정렬의 성능과 특징

• 입력값의 범위가 데이터의 개수보다 작거나 비례할 때 유용
  • 입력값의 범위를 k라고 할 때 O(n+k) 시간
  • → k=O(n)이 되어야 선형 시간 O(n)에 동작
• 안정적인 정렬 알고리즘
  • 입력 배열 A[ ]의 오른쪽의 것부터 뽑아서 결과 배열 B[ ]의 오른쪽에서부터 저장
• 제자리 정렬 알고리즘이 아님
  • 입력 배열 A[1..n] + ( COUNT[a..b], B[1..n] )와 같은 추가적인 저장 장소 필요
• 보편적이지 못한 정렬 알고리즘
  • 입력값의 범위를 미리 알아야 함 + 추가적인 배열이 필요

17. 기수 정렬

• 입력값을 자릿수별로 구분해서 부분적으로 비교하여 정렬하는 방식
  • 주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리즘을 적용하여 정렬
• 구분
  • LSD ( Least Significant Digit ) 기수 정렬 → 낮은 자리부터 높은 자리로 진행, ”Right-to-Left”
  • MSD ( Most Significant Digit ) 기수 정렬 → 높은 자리부터 낮은 자리로 진행, ”Left-to-Right”

18. 기수 정렬 알고리즘

RadixSort (A[ ], n) {

	for (i=1; i<=d; i++) { // d 자릿수, LSD 기수 정렬
		각 데이터의 i자리의 값에 대해서 안정적인 정렬 알고리즘 적용;
	}
	
	return (A);
}

19. 기수 정렬의 성능과 특징

• 입력 데이터의 자릿수가 상수일 때 유용
  • d 자릿수 n개의 숫자들에 대해 계수 정렬을 적용하면 O(dn)
    • 여기서 d를 입력 크기 n가 무관한 상수로 간주하면 O(n)
• 안정적인 정렬 알고리즘
  • 각 자릿수별로 안정적인 정렬 알고리즘을 적용하므로 기수 정렬도 안정적
• 제자리 정렬 알고리즘이 아님
  • 계수 정렬 적용 → 전체 데이터 개수와 진법 크기만큼의 추가 공간이 필요

20. 버킷 정렬

• 방법
  • 주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든 뒤,
  • 각 데이터를 해당하는 버킷에 넣고,
  • 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후,
  • 버킷 순서대로 각 데이터를 나열하는 정렬 방식
• 입력값의 범위 내에서 값이 확률적으로 균등하게 분포될 때 선형 시간에 동작

21. 버킷 정렬 알고리즘

BucketSort (A[ ], n){

	MIN = MAX = A[0];
	
	for (i=1; i < n; i++) { // 입력값의 범위 MIN~MAX 계산
		if (A[i] < MIN) MIN = A[i];
		if (A[i] > MAX) MAX = A[i];
	}
	
	INTERVAL = |(MAX – MIN + 1) / n| ; // 버킷 구간의 크기 계산

	for (i=0; i < n; i++) { // 각 데이터를 해당 버킷에 넣기
		A[i]를 BUCKET[ |(A[i] - MIN)/ INTERVAL | ]에 삽입;
	}
	
	for (i=0; i < n; i++) { // 버킷별로 정렬
		삽입 정렬에 의해 BUCKET[i]를 정렬;
		BUCKET[0], BUCKET[1], …의 순서대로 데이터를 배열 B[ ]에 삽입; 
	}
	return (B);
}

22. 버킷 정렬 성능과 특징

• 입력 데이터의 값이 확률적으로 균등하게 분포할 때 유용
  • 버킷별 정렬 → 데이터들이 각 버킷에 균등하게 들어갈 때 효율적인 정렬이 가능
• 버킷의 개수가 입력 데이터의 개수에 비례해야 유용
  • 버킷의 개수를 | n / k |개로 정하면 각 버킷에는 상수( k ) 개의 데이터가 존재
  • 각 버킷을 상수 시간에 정렬 가능 → 선형 시간의 동작이 가능
• 안정적인 정렬 알고리즘
  • 데이터를 버킷에 넣을 때 그리고 각 버킷의 정렬 과정에서 상대적인 순서를 유지
• 제자리 정렬 알고리즘이 아님
  • 추가적인 저장 공간( BUCKET[ ]과 크기 n의 배열 B[ ] )이 필요