열혈 자료구조 - 10.2 복잡하지만 효율적인 알고리즘(1)

힙 정렬

- 힙의 특성을 이용해서 데이터를 힙에 넣고 그대로 꺼내서 정렬을 시키는 방법

- 힙에 데이터를 넣을 때 우선순위를 기반으로 데이터를 넣기 때문에 그대로 이용하면 됨

int PriComp(int n1, int n2)
{
	return n2-n1;
//	return n1-n2;
} // 우선순위를 비교할 함수

void HeapSort(int arr[], int n, PriorityComp pc)
{
	Heap heap;
	int i;

	HeapInit(&heap, pc);	// 힙 초기화
	
	for(i=0; i<n; i++)
		HInsert(&heap, arr[i]);		// 힙에 데이터 삽입

	for(i=0; i<n; i++)
		arr[i] = HDelete(&heap);	// 데이터를 꺼내면 우선순위가 가장 높은것이 나옴
}

- 힙 정렬의 시간 복잡도

    -> 데이터 저장, 삭제의 시간 복잡도

    -> 데이터 n개를 넣고 빼는데 걸리는 시간 복잡도

    -> n앞의 상수는 생략하므로 결국

 

병합 정렬

- Divide and Conquer(분할 정복) 알고리즘을 기반으로 하는 정렬

- 데이터를 한번에 정렬하지 않고 분할하여 정렬하고 다시 합치는 방법

- 데이터를 정렬하기 쉬운 단계까지 분할하는 것이 효율적

    -> 데이터가 1개가 될 때까지 분할

- 다시 합칠 때 정렬을 위한 연산을 수행

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if(left < right)		// left가 작으면 나눌 수 있음 = 데이터가 1개가 될때까지(출조건)
	{
		// 중간 지점을 계산한다.
		mid = (left+right) / 2;

		// 데이터를 두 부분으로 쪼개는 과정
		MergeSort(arr, left, mid);		// 좌측 부분을 분할
		MergeSort(arr, mid+1, right);	// 우측 부분을 분할

		// 쪼개진 두 부분을 병합
		MergeTwoArea(arr, left, mid, right);
	}
}

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid+1;
	int i;

	int * sortArr = (int*)malloc(sizeof(int)*(right+1));	// 병합한 결과를 담을 배열
	int sIdx = left;

	while(fIdx<=mid && rIdx<=right)
	{
		if(arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	} // 1단계 : 두 영역에서 한쪽 영역이 빌 때까지 sortArr에 옮김

	if(fIdx > mid)
	{
		for(i=rIdx; i<=right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for(i=fIdx; i<=mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	} // 2단계 : 두 영역 중 남은 영역의 데이터를 sortArr로 옮김

	for(i=left; i<=right; i++)
		arr[i] = sortArr[i];	// 3단계 : sortArr의 데이터를 arr로 옮김
	
	free(sortArr);
}

- 1단계 : fIdx가 mid를 넘거나 rIdx가 right의 값을 넘을때까지 진행

- 2단계 : 남아있는 영역의 데이터를 옮김

- 병합 정렬의 시간 복잡도

     -> 병합 정렬은 분할의 과정보다는 병합의 과정의 연산이 더 중요

     -> 데이터가 8개일 경우 3단계를 거쳐 병합을 완료함

     -> 하나의 단계에서 최대 병합하고자 하는 데이터만큼 비교 연산을 진행

     -> 데이터를 sortArr로 이동시키고 다시 arr로 이동